"Chad C. Mulligan" <[EMAIL PROTECTED]>:
> Hmmm... I don't know how _efficient_ it is, but in the tests I did
> on it, the average time to create a 1024 bit strong prime (and one
> _guaranteed_ strong, by construction) was 1014 seconds, as opposed
> to 2301 seconds for BN_generate_prime() with "strong" set to 1.
What exactly do you mean by "strong" primes? BN_generate_prime() uses
the word "strong" for what is more commonly called a "safe" prime,
namely one where (p - 1)/2 is also prime. The word "strong" is
traditionally (and I would like to be able to say "historically") used
for RSA factors satisfying certain properties; namely: A prime p is
called "strong" if p - 1 has a large prime factor p', p' - 1
again has a large prime factor, and p + 1 has a large prime factor.
These requirements, together with p - 1 and q - 1 having a small
GCD, make an RSA modulus resistant against certain attacks, which
however are now superseded by more efficient methods (such as elliptic
curve factoring), rendering this property worthless. (See Bob
Silverman's papers on this topic, e.g. an article in some issue of
CryptoBytes -- <URL:http://www.rsa.com> -- and some paper referenced
from there, which should also be available at the RSA Labs web-site.)
This kind of "strong" primes is mainly nostalgia.
"Safe" primes, where q := (p - 1)/2 is prime, imply that there is
one very large (order q) subgroup of (Z/pZ)*. More generally,
we want a large prime q to be some divisor of p - 1. The order of
the generator selected must be q or a multiple of q (it is
absolutely not necessary that it generate all of (Z/pZ)*, which is
how the cryptographic schemes are described in the original
Diffie-Hellman and ElGamal papers.)
q selected like that and an appropriate generator offer optimal
resistance against "generic" algorithms for discrete logarithms, whose
runtime is the root of the size of this subgroup. (Subgroups whose
order has only small prime factors don't add any security against this
kind of attacks.) It's really (generally believed to be) enough to
have q so large that other known attacks become more efficient than
the generic ones. For example, for a 1024 bit prime p, a 165 bit q
should be enough. (And even if q is larger, you can select secret
DH/ElGamal exponents with smaller sizes.)
PGP uses for ElGamal encryption primes p where q is only about 10
bits smaller than p. While such large q's are not really needed
for security reasons, they make it easy to make sure that 2 or
some other small number is a generator of a subgroup the order of
which is divided by q. That's very convenient, because the
exponentiation x^k is much easier to compute for x = 2 than for
large x. (Note that while PGP chooses a quite large q, the
secret exponents are chosen rather small.) Alternatively, one could
construct p - 1 to be the product of primes none of which, except
for the inevitable 2, is smaller than what we want for q -- then
we can also guarantee that 2 is okay as a generator. In any case,
either we need to know all factors of p - 1, or we can't use a small
generator.
> [...] because of the way the algorithm works, the size is somewhat
> variable, though this can be made better with empirical adjustments to the
> seed-data. For example, after asking for 1024 bit primes, I tended
> to end up with 1032 bit ones. I don't know if this is a problem or
> not. Is it?
It is: Export cipher suites need Diffie-Hellman parameters of no more
than 512 bits.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
