The reference to Lim Lee is in section 4 of this paper on discrete og
attacks (and how to generate primes immune to them):
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5296
They recommend that the p_i values are bigger than q. Ie in a 1024 bit p,
160 bit q, then all of the p_i values making up n should be > 160-bits,
where p = 2qn+1 where n = p_1 * ... * p_k and in this case you need
(1024-160)/k > 160 so k = 5 and |p_i| = 172.
For sub-group based crypto systems q is distinct from and not a p_i because
the crypto system uses the subgroup q (eg DSA etc), and there q has to be of
a specific size ie relating to a hash output size for security reasons,
where q < 2^out where out size of the hash output in bits.
Crypto++ is expecting a strong-prime where p=2q+1, p & q primes. btw for
some attacks it is also necessary for q' = (p-1)/2 to be prime.
Adam
On Tue, Dec 18, 2012 at 01:15:05AM +0100, Adam Back wrote:
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
