[cryptography] ElGamal Encryption and Signature: Key Generation Requirements?

Jeffrey Walton noloader at gmail.com
Mon Dec 17 18:43:15 EST 2012

Hi All,

This has been bugging me for some time....

When Crypto++ and GnuPG interop using ElGamal, Crypto++ often throws a
bad element exception when validating the GnuPG keys. It appears GnuPG
does not choose a q such that q - 1 is prime (in the general form of p
= qr + 1). That causes a failure in Crypto++'s Jakobi test.

I could not find a paper stating q - 1 non-prime was OK (on Google and
Google Scholar). I would think that q - 1 prime would be a
requirement, since some algorithms run in time proportional to q - 1
(for example, Pollard's Rho).

What are the key generation requirements for ElGamal Encryption and
Signature schemes?


More information about the cryptography mailing list