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 $p$ and a generator $a$ of $(\mathbb{Z}/p\mathbb{Z})^\times$, $2\leq a\leq p-2$. Publish them.

• Exchange data as follows:
  • Amelia picks a random secret $x$, $2\leq x\leq p-2$, sends Ben, $a^x\, ({\rm mod}\, p)$.

  • Ben picks a random secret $y$, $2\leq y\leq p-2$, sends Amelia , $a^y\, ({\rm mod}\, p)$.

• Compute keys as follows:
  • Amelia receives $a^y\, ({\rm mod}\, p)$ and computes $K=(a^y)^x \, ({\rm mod}\, p)$.

  • Ben receives $a^x\, ({\rm mod}\, p)$ and computes $K=(a^x)^y \, ({\rm mod}\, p)$.

• $K$ is the shared secret key.

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

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

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