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

Adam Back adam at cypherspace.org
Mon Dec 17 19:15:05 EST 2012

Those are Lim-Lee primes where p=2n+1 where a B-smooth composite (meaning n
= p0*p1*...*pk where each p0 is f size < B bits.


So if Crypto++ is testing if the q from p=2q+1 is prime, its right -- its
not!  But its not broken so long as B is large enough.  If B is too small
its very broken.


On Mon, Dec 17, 2012 at 06:43:15PM -0500, Jeffrey Walton wrote:
>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?
>cryptography mailing list
>cryptography at randombit.net

More information about the cryptography mailing list