On Sat, Mar 27, 1999 at 04:03:00AM +0100, Bodo Moeller wrote:
> "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
Sorry, I was temporarily confused. While the above is a _necessary_
property of good Diffie-Hellman parameters, it is not sufficient.
A sufficient condition can be formulated as follows:
Let p be a prime of N bits, and let M be a threshold for the
base-2 logarithm of the order of groups in which generic algorithms
for discrete logs are less efficient than special algorithms are for
(Z/pZ)*. (All this means that if we choose N = 1024, M should be
165, as stated in my previous message.) Let g be a candidate
generator of some subgroup of (Z/pZ)* (we don't exclude the case that
g generates the whole group (Z/pZ)*). We write ord(g) for the
order of element g, which is also the order (= number of elements)
of the subgroup that g generates.
It is safe to use g if the following conditions are met:
- There is a number O (which must satisfy M < O < N) such
that ord(g) has a prime factor of O bits; and
- if P denotes the bit length of that factor of ord(g) which
consists only of prime factors of _less_ than O bits (in
other words: the bit length of the 2^(O-1)-smooth part of
ord(g)), then O - P > M.
For example, PGP's Diffie-Hellman parameters have, e.g., N = 1024
and O = 1014 (p - 1 has a prime factor about 10 bits smaller
than p). Since ord(g) divides p - 1, the smooth part of ord(g)
can have at most 10 bits, i.e. P <= 10. So, O - P is at least
1004, which is well greater than 165.
But, on the other hand, Diffie-Hellman parameters are not good if
ord(g) is the product of a 200-bit prime and ten 20-bit primes.
While 200 bits would be enough, the small primes destroy everything.
The reason is that an attacker can first compute logarithms in the
small subgroups, which is really easy, and then knows about everything
about the logarithms in the one large subgroup. In the above
condition, P stands for the bit-lenght of the size of a subgroup in
which discrete logarithms are assumed to be easy; O - P stands for
that part of the group generated by g which remains to be attacked
after using those easy logarithms.
As another example, if ord(g) is the product of a 200-bit prime, a
160-bit prime, a 120-bit prime, a 80-bit prime and a 40-bit prime,
logarithms are also quite easy (an attacker can succesively compute
logarithms in larger groups, starting with the 40-bit prime). In the
above conditions, this shows in the impossibility to find an O that
fulfils them.
> (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.)
As discussed above, it is actually a disadvantage if g generates
"too much" of (Z/pZ)*, unless special care is taken. "Safe primes"
(p = 2*q + 1 with q prime) are an easy way to avoid this problem:
With only two elements, the small subgroup is so small that it cannot
hurt.
> In any case,
> either we need to know all factors of p - 1, or we can't use a small
> generator.
I hope this statement became more clear by now. -- If we know only one
large prime factor q of p - 1, but not the factorization of p - 1,
it is safe to choose some g with ord(g) = q. Such a g is easily
found, but it is highly impropable that it will be a small number,
as we want it for efficiency reason. Because parameter generation
doesn't have the timing constraints that occur in the actual _use_ of
the Diffie-Hellman parameters, it makes sense to invest more effort in
parameter creation so that g = 2 or something similarly small can be
used. (Note, however, that for ElGamal _signatures_ [as opposed to
ElGamal _encryption_] additional conditions must be met!)
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
