Application: Diffie-Hellman key exchange

How do two people, Amelia and Ben, share a secret over an open channel of communications? It may seem incredible at first, but it is possible and is the remarkable discovery of Whitfield Diffie, now at Sun Microsystems, and Martin Hellman, an electrical engineering professor at Stanford University, in 1976.

The idea is to first determine a shared secret key, which one could use (for example) to encrypt the messages between them. Its security depends on the difficulty of the discrete log problem, discussed in the previous section.

- Pick a ``large'' prime number and a generator
of
,
.
Publish them.
- Exchange data as follows:
- Amelia picks a random secret ,
,
sends Ben,
.
- Ben picks a random secret ,
,
sends Amelia ,
.

- Amelia picks a random secret ,
,
sends Ben,
.
- Compute keys as follows:
- Amelia receives
and computes
.
- Ben receives
and computes
.

- Amelia receives
and computes
.
- is the shared secret key.

More details are given in [MOV], §12.6.

David Joyner 2007-09-03