Re: D-H key exchange - how does it work?

[nelson@bolyard.wpd.sgi.com (Nelson Bolyard)]

Perry E. Metzger wrote, describing Diffie_Hellman key exchange:
> Suppose we have a field Z_p, where p is a prime.  
> Suppose g is a generator of the field.  
> Alice generates a random number a.  
> Bob generates a random number b.  
> Bob tells alice g^b, Alice tells Bob g^a.
> Alice knows a and g^b, and thus generates g^(ab) trivially.  
> Similarly, Bob knows g^a and b, and trivially generates g^(ab).  
> 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).
> 
> g^(ab) is now a shared secret of Alice and Bob.


Some of us may not have seen an explanation of DH before.
Perry's explanation was good.  For the sake of completeness 
for those who're new to DH, I'd like to offer some additional
information and considerations, here.

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.

> Ed Carp asked:
> > If I understand D-H right, both sides generate public keys from their
> > private keys, then just exchange public keys.  Is that right?  Or is there
> > something I'm missing? 

Well, there are published descriptions of D-H that refer to the publicly
exchanged values, g^a and g^b, as "public keys", and by that definition,
yes, both sides exchange "public keys."  But as you can see, these aren't
public keys in the same sense that RSA public keys are.


--
Nelson Bolyard       Multimedia Server Division      Silicon Graphics, Inc.
nelson@sgi.COM       Phone: 415-390-1919             Fax: 415-967-8496
Disclaimer: I do not speak for Silicon Graphics.
--