-----BEGIN PGP SIGNED MESSAGE----- nelson@sgi.com describes some of the precautions required to use DH exchange safely: ** begin quoted text *** The prime p wants to be chosen with a little care, and the "random" numbers a and b may want to be "selected" to eliminate certain undesirable values. I'll explain below. Within the field Z_p (the set of integers 0..p-1) where p is prime, there are elements whose successive powers make up all the elements of the field Z_p. These numbers are called "primitive" elements or "generators" of the field Z_p. That is, if g is a generator of the field Z_p, then the successive powers g, g^2, g^3, ... g^(p-2), g^(p-1) mod p include all the p-1 non-zero elements of Z_p. The set of unique numbers produced by taking succesive powers mod p of an element m of Z_p is a group, the "multiplicative span" of m, which is a subgroup of Z_p. The number of elements in the group generated by m is called the "order" of m. Primitive elements of Z_p have order p-1. Not all of the elements of Z_p are primitive. Some elements of Z_p have very small orders. At least one element will have order 2. Given that p is prime, the orders of the elements of Z_p will all have values that are products of some or all of the prime factors of p-1. Since p is prime (and p=2 is not interesting ;-), p-1 will contain the factor 2. An small example may make this point clear. Let p == 11. The prime factors of p-1 are 2 and 5. Hence we expect the orders of the elements of Z_11 to be 2, 5, or 10. By enumerating the groups of the elements of Z_11 we see this is so (for Z_11). E.g. Element Ring Order - ------ ----------------------------- ----- 1 1 1 2 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 10 3 3, 9, 5, 4, 1 5 4 4, 5, 9, 3, 1 5 5 5, 3, 4, 9, 1 5 6 6, 3, 7, 9, 10, 5, 8, 4, 2, 1 10 7 7, 5, 2, 3, 10, 4, 6, 9, 8, 1 10 8 8, 9, 6, 4, 10, 3, 2, 5, 7, 1 10 9 9, 4, 3, 5, 1 5 10 10, 1 2 There are 4 primitive elements in Z_11, 2, 6, 7, & 8. The orders of all the elements are as predicted by Euler. Now, let us imagine that Alice and Bob have chosen 11 as their prime and 7 as "g", their generator. Following the steps outlined above:
Alice generates a random number a. say 3 Bob generates a random number b. say 5. Bob tells alice g^b, Alice tells Bob g^a. 10 2 Alice knows a and g^b, and thus generates g^(ab) trivially. 10 Similarly, Bob knows g^a and b, and trivially generates g^(ab). also 10. An interceptor only knows g^a and g^b, and because the discrete log problem is hard cannot get a or b easily, and thus cannot generate g^(ab).
Except that the interceptor, evil Eve, took g^a and g^b and tested them for short order, and found that one of them, g^b, had a very short order indeed. So, without knowing a or b, Eve knows that g^(ab) is one of a very few numbers, the elements of the group of g^b. She can now try the elements of that group until, by exhaustion, she finds the value that reveals the key g^(ab).
g^(ab) is now a shared secret of Alice and Bob.
And Eve, too. Some primes produce lots and lots of elements with small orders. For example, Z_37 has 12 primitives, 6 elements of order 18, and all the rest have order 9 or less. So, is DH all wet (insecure)? No. There are some simple steps to prevent this problem. First, pick p to minimize the number of elements with small order. This means that we need to know the factorization of p-1. Of course, factoring large numbers is a hard problem, but there are several ways to pick p with known factorization of p-1. The simplest seems to be to pick p such that (p-1)/2 is prime; that is, such that p-1 has two factors, 2 and (p-1)/2. Now, all the elements of Z_p will have orders of either 2, or (p-1)/2, or p-1. There are other methods, that permit other small orders, but we won't explore them here. Second, after "randomly" choosing a, and computing g^a, Alice takes the additional step of making sure that the order of g^a is not small (i.e. is more than 2). If g^a is of small order, she picks another random a, and repeats the process. This is trivial indeed. Bob does likewise for his numbers b and g^b. Since Alice and Bob have eliminated the small groups, Eve will never encounter a g^a or g^b number whose order is less than (p-1)/2, and given that (p-1)/2 is a _very_ large prime number, Eve won't live long enough to try all of the elements of groups of that order. I haven't checked to see if the RSAREF code takes these precautions. *** end quoted text *** I wrote a Diffie-Hellman exchange program as an extension to PGP Tools. It uses the PGP MPILIB and does up to 1024-bit key exchange, then MD5's the shared secret to get an IDEA key. I took most of the precautions above. - From the DHEX10A manual (csn.org):
To use DH, we need a modulus n and a generator g. Unlike an RSA modulus, which is a product of two primes, a DH modulus must be prime. (n-1)/2 must also be prime. This makes the moduli slightly painful to find, but they can be reused indefinitely. DHEX tests a modulus by first testing both n and (n-1)/2 with fastsieve. Only if both pass is slowtest used. It still took me a whole day to find the 1024-bit modulus in the demo. There is also a 512-bit modulus there.
To find the generator, we need the factors of n-1. They are 2 and (n-1)/2. For each factor f, we compute ((g^((n-1)/f)) mod n). If this is 1 for either factor, the number is NOT a generator. Generators are easy to find, usually in one to three tries.
The one precaution I did not take is: (from discussion above)
Second, after "randomly" choosing a, and computing g^a, Alice takes the additional step of making sure that the order of g^a is not small (i.e. is more than 2). If g^a is of small order, she picks another random a, and repeats the process. This is trivial indeed. Bob does likewise for his numbers b and g^b.
Does the careful choosing of n and g eliminate this problem, or do I need to modify my Diffie-Hellman code to check g^a for short order? How do you check a number for short order? Pr0duct Cypher -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLd1CL8GoFIWXVYodAQGnhAP+KI+w8ihQCrwKorBpkshwxBOLStIsC1uo 0e/weUyl6SqIaPCvPbYdhoKXfwpMkLxTJLvwb0wCZPtrfUDWJiCao4H7dV8VCh/q ksWDYdVBpxupdMni+vkbuewQz105FaSTz1tHXiy1hgWYO+/OrHXy2r3WEEx8+zcF ZqDMDbdvToU= =sZT1 -----END PGP SIGNATURE-----