The Diffie–Hellman key exchange.

Step 1 of 6

Mixing paint

In 1976 Whitfield Diffie and Martin Hellman published a way for two people who have never met to agree on a secret key, while everything they say to each other is overheard. Look inside is open at Mixing paint, a picture that explains the idea.

Alice and Bob agree in public on one colour, yellow. Each secretly chooses a colour of their own, and tells it to nobody. Each mixes their secret into the yellow and sends the mixture down the tube. Watch what passes through the tube, and what each side does with what it receives.

Step 2 of 6

From paint to numbers

The paint is only a picture: paint is easy to mix and hard to unmix. In the real exchange, mixing is replaced by a power mod a prime, from the Lesson on clock arithmetic. The public values are the prime $p = 23$⁠ and the generator $g = 5$⁠. Alice chooses a secret $a$⁠ and sends $A = g^a \bmod p$⁠; Bob chooses a secret $b$⁠ and sends $B = g^b \bmod p$⁠.

Look inside is still on the paint, and the numbers are hidden: you will do the arithmetic yourself.

Step 3 of 6

Alice’s key

Alice has received $B$⁠ from Bob. She raises it to the power of her secret, and gets the shared key:

$s = B^a \bmod p$⁠

Step 4 of 6

Bob’s key

Bob does the same with what he received: he works out $A^b \bmod p$⁠. Alice and Bob each used a different secret, and never saw the other’s.

Step 5 of 6

Eve’s search

Eve saw everything: $g$⁠, $p$⁠, $A$⁠ and $B$⁠. To reach the key she needs one of the secrets, that is, to find the exponent $x$⁠ with $g^x \bmod p = B$⁠. That is the discrete logarithm problem. Alice and Bob work out a power in a tiny fraction of a second, even with numbers hundreds of digits long. The other way round, no fast method is known: Eve is left with something like trying exponents one after another.

Step 6 of 6

Public and secret

The Diffie–Hellman exchange opened up public-key cryptography: methods in which part of the key is known to everyone and part is kept secret. In RSA, for example, everyone publishes an open padlock anyone can snap shut, and only they hold the key that opens it; it rests on how hard it is to factor a product of two large primes. Every time a browser connects to a secure website, it runs a key exchange of this kind, with numbers hundreds of digits long.