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.
http://www.gnupg.org/documentation/manuals/gcrypt/Prime_002dNumber_002dGenerator-Subsystem-Architecture.html 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. Adam 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? Jeff _______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
