The Diffie*–Hellman Key Exchange

We are extremely lucky that we live in a universe where we can communicate securely over untrusted channels.

This problem of having a shared secret was solved by Whitfield Diffie and Martin Hellman. Let’s say Alice and Bob want to share a secret. Working through this scheme using numbers, Alice and Bob choose two prime numbers, say $p = 23$ and $g = 5$. Alice then chooses a secret number $a = 6$ and calculates $$\begin{aligned} A &= g^a \text{ mod } p \\ &= 5^6 \text{ mod } 23 \\ &= 15625 \text{ mod } 23 \\ &= 8. \end{aligned}$$ Bob chooses his secret to be $b = 15$ and calculates $$\begin{aligned} B &= g^b \text{ mod } p \\ &= 5^{15} \text{ mod } 23 \\ &= 30517578125 \text{ mod } 23 \\ &= 19. \end{aligned}$$ They share the numbers $A$ and $B$ and do the same thing again, so Alice calculates $$\begin{aligned} s &= B^a \text{ mod } p \\ &= 19^6 \text{ mod } 23 \\ &= 47045881 \text{ mod } 23 \\ &= 2 \end{aligned}$$ and Bob calculates $$\begin{aligned} s &= A^b \text{ mod } p \\ &= 8^{15} \text{ mod } 23 \\ &= 30517578125 \text{ mod } 23 \\ &= 2. \end{aligned}$$

Amazingly, they now both have the same secret number $s = 2$.

This works because $$ A^b \text{ mod } p = g^{ab} \text{ mod } p = g^{ba} \text{ mod } p = B^a \text{ mod } p $$ since the order of exponentiation does not matter.

In this example, the secret is not very safe since there are only 23 possible results of any number mod 23. However, when $p$ is a large prime the problem is intractable even by very fast computers. The problem of finding $a$ given $g$, $p$ and $g^a$ mod $p$ is called the discrete logarithm problem. Here, we are relying on this problem being difficult to solve. (In fact, there are also some restrictions on $g$ in order to guarantee the difficulty of this problem.)

Now, Alice and Bob are free to use their shared secret to encrypt messages using their Cæsar cypher — or, in practice, a much harder cypher to break. An eavesdropper listening to everything on the channel will not be able to identify their shared secret, even though they know $p$, $g$, $g^a$ mod $p$ and $g^b$ mod $p$.

In practice, the values used for the prime $p$ are chosen from a relatively small list of “safe” primes. However, if an adversary is attempting to solve the discrete-logarithm problem it turns out that the first three (of four) steps depend only on this prime $p$. Thus it is possible for an adversary to precompute these stages and save vast computer resources, rather than compute each four stages every time they wished to solve for the shared secret. This is the basis for the recent Logjam attack, which has now been mitigated by disallowing smaller primes. Another potential problem is the advent of quantum computers, which can solve the discrete logarithm problem efficiently.

*If the title renders as “Difffie”, this is a bug in the typeface.