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.

Example 1.8.14   Pick $ p=541$, $ a=2$. Amelia chooses $ x=137$ and sends $ a^x=2^{137}\equiv 208\, ({\rm mod}\, 541)$ to Ben. Ben picks $ y=193$ and sends $ a^y=2^{193}\equiv 195\, ({\rm mod}\, 541)$ to Amelia. They compute the secret shared key

$\displaystyle K=(a^x)^y \equiv (2^{137})^{193} \equiv (208)^{193}\equiv 486\, ({\rm mod}\, 541). $

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

David Joyner 2007-09-03