Diffie–Hellman key exchange

Example

The Diffie–Hellman key exchange is an example of public-key cryptography. Two parties, Alice and Bob, use it to agree on a secret key over a public channel. They agree in public on a prime $p$ and an integer $g$, often a primitive root modulo $p$. Alice chooses a secret integer $a$ and sends $A = g^a \bmod p$. Bob chooses a secret integer $b$ and sends $B = g^b \bmod p$. Alice computes $B^a \bmod p$, and Bob computes $A^b \bmod p$. Both are equal to $g^{ab} \bmod p$, the shared secret. A small case: $p = 11$, $g = 2$, $a = 3$ and $b = 4$. Then $A = 8$, $B = 16 \bmod 11 = 5$, and $5^3 \equiv 8^4 \equiv 4 \pmod{11}$.

Remarks

An eavesdropper sees $p$, $g$, $A$ and $B$. To find $g^{ab}$, a natural method is to compute a discrete logarithm, which is believed to be hard for large $p$. The same method works in any finite cyclic group, for example the group of points of an elliptic curve. Whitfield Diffie and Martin Hellman published the method in 1976.

Explanations

L1 human

Each party mixes a public number with a private number, and they swap the results. Each then mixes in their own private number again, and both get the same final number. An eavesdropper sees only the swapped numbers, and cannot easily undo the mixing.