[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

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.