D-H key exchange - how does it work?

-----BEGIN PGP SIGNED MESSAGE-----

I browsed through the (SCANT!) documentation that comes with rsaref-2.0. I
didn't find any decent programming examples, just a list of function
calls, which is next to useless without sample code, but that's beside the
point. 

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? 
- --
Ed Carp, N7EKG/VE3		ecarp@netcom.com		519/824-3307
Finger ecarp@netcom.com for PGP 2.3a public key		an88744@anon.penet.fi
If you want magic, let go of your armor.  Magic is so much stronger than
steel!        -- Richard Bach, "The Bridge Across Forever"


-----BEGIN PGP SIGNATURE-----
Version: 2.5

iQCVAgUBLdkNCyS9AwzY9LDxAQFW9AP/YeQR0rrX6kfonzLPI5/5U6MB8Q8Uu01a
C9y5y/U2rkYU5gYsAKiw9d4i0yFAiI3KyNWOamdr7aQMWMCOa8y6RPdfKQzuzREg
h4KTjcflcZoffWP7JamboQUPAsOrNwHlumTVnI3cf30U0Zi5QxNHj9PlVupOOvQ4
dSO4Nv6LiG4=
=icYy
-----END PGP SIGNATURE-----

Ed Carp says:
> 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? 

Yes. Thats not the algorithm at all. D-H is based on the difficulty of
the discrete log problem, that is, the problem of inverting an
exponentiation modulo a large prime. 

Its been a while, so I might be forgetting something here or
misstating -- someone correct me if I am wrong.

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.

Perry