Every cipher so far needs a shared secret key. But how do two people who have never met agree on a key, over a line that anyone can listen to? In 1976 Diffie and Hellman found a way, built on discrete logarithms: easy to go forward, hard to go back.
- Public: a large prime $p$ and a primitive root $g$ mod $p$.
- Alice picks a secret $a$ and sends $A = g^{a} \bmod p$. Bob picks a secret $b$ and sends $B = g^{b} \bmod p$.
- Alice computes $B^{a}$, Bob computes $A^{b}$. Both get the shared key $K = g^{ab} \bmod p$.
Why it works
$B^{a} = (g^{b})^{a} = g^{ab} = (g^{a})^{b} = A^{b}$, so they agree. An eavesdropper, Eve, sees $p$, $g$, $A$ and $B$. To get $K$ she seems to need $a$ or $b$, that is, a discrete logarithm of $A$ or $B$. For a prime of a few hundred digits, no one knows how to do that in any reasonable time, while Alice and Bob each need only one fast power.
Worked example: A small exchange
Public: $p = 29$, $g = 2$. Alice's secret is $a = 9$ and Bob's is $b = 13$. Find $A$, $B$ and the shared key.
- $A = 2^{9} = 512 = 17 \cdot 29 + 19$, so $A = 19$.
- $B = 2^{13} = 8192 = 282 \cdot 29 + 14$, so $B = 14$.
- Alice: $K = 14^{9} \bmod 29 = 3$. Bob: $K = 19^{13} \bmod 29 = 3$.
- Check: $K = 2^{9 \cdot 13} = 2^{117}$, and $117 \equiv 5 \pmod{28}$, so $K \equiv 2^{5} = 32 \equiv 3$.
Answer: $A = 19$, $B = 14$, $K = 3$.
Worked example: Eve with a tiny prime
Why is $p = 29$ unsafe?
- Eve lists $2^{1}, 2^{2}, \dots \bmod 29$ until she sees $19$: $2^{9} \equiv 19$, so $a = 9$.
- Then she computes $B^{a} = 14^{9} \equiv 3$, the key. With $p$ near $10^{600}$ the list would be far too long to search.
Answer: A small prime makes the discrete logarithm easy.
Common mistake
Computing the shared key as $A \cdot B$. That is $g^{a} g^{b} = g^{a + b}$, not $g^{ab}$, and it is no secret at all: Eve sees $A$ and $B$ and can multiply them. Here $A \cdot B = 19 \cdot 14 = 266 \equiv 5$, not the key $3$. The key comes from raising the other person's number to your own secret exponent.
Why a primitive root? Then $g^{a}$ runs through every nonzero residue as $a$ varies, so the shared key can be any of $p - 1$ values and Eve gains nothing from guessing. If $g$ had a small order, say 4, there would be only 4 possible keys.
Diffie–Hellman protects against listening, not against impersonation: an attacker who can change messages could run one exchange with Alice and another with Bob. Real systems add signatures to prove who is talking.
Key idea
Diffie–Hellman: exchange $A = g^{a}$ and $B = g^{b}$ in public; each side raises the other's number to its own secret, and both get $g^{ab} \bmod p$.