How can two strangers agree on a secret in public?

To keep a conversation private, two machines scramble it with a key: a long secret number that both of them know and nobody else does. With a shared key, encryption is a solved problem. The hard part is getting the key there in the first place.

The obvious answer is to send it. But on the internet every message passes through routers, Wi-Fi access points and cables owned by other people. Assume someone, traditionally called Eve (the eavesdropper), sees every word that Alice and Bob exchange. If Alice sends the key, Eve has it too. If Alice encrypts the key first, she needs another key to do it, and we are back where we started.

It seems that a secret can never be created out of public messages alone. That intuition is wrong, and the way it fails is one of the great ideas of the twentieth century.

Mixing paint

Here is the trick with paint instead of numbers. Alice and Bob agree, in public, on a starting colour: yellow. Each then picks a secret colour and tells no one. Alice stirs her secret into a pot of yellow and posts the pot to Bob; Bob does the same and posts his to Alice. Eve sees both pots go by.

Now each adds their own secret colour again, to the pot they received. Alice's pot now holds yellow + Bob's secret + Alice's secret. Bob's holds yellow + Alice's secret + Bob's secret. Same ingredients, same amounts, so the same colour, and that colour is their shared secret.

The analogy captures the one property that matters: mixing is easy, and unmixing is, for practical purposes, impossible. Eve holds a pot containing yellow and Alice's secret, but she cannot pull the secret back out.

It also breaks, in two places. First, a determined Eve with a colour meter could try to work out what was added to the yellow; real paint is not as one-way as we need. Second, paint cannot be copied exactly or sent down a wire. For the real thing we need an operation on numbers that is just as easy to do and just as hard to undo.

Arithmetic on a clock

That operation lives on a clock. On an ordinary clock, 9 o'clock plus 5 hours is 2 o'clock: you wrap around after 12. Mathematicians call this arithmetic modulo 12, and they do it on clocks of any size. We will use a clock with a prime number of hours, p (a prime has no divisors except 1 and itself), labelled 0 to p − 1.

Pick a starting number g, the base. Multiply it by itself again and again, and after each multiplication wrap around the clock. After x multiplications you have

g^x mod p

read “g to the power x, modulo p”: the remainder when g^x is divided by p. For example, with g = 5 and p = 23: 5, then 25 → 2, then 2 × 5 = 10, then 50 → 4, and so on.

Two things to notice. Going forwards is easy: each step is one multiplication and one remainder. And some bases are better than others. On the 23-hour clock, g = 5 visits every one of the 22 non-zero hours before repeating; such a base is called a generator. Try g = 2 instead: it visits only 11 hours, so there are only half as many places to hide.

Going backwards — given the hour, find x — is called the discrete logarithm problem. On a 23-hour clock you can solve it by trying all 22 exponents. On a clock whose number of hours has 600 digits, nobody knows how to solve it in any reasonable time. That gap is the one-way street we need.

The exchange, and Eve

Now replace the paint with numbers. Alice and Bob agree in public on a prime p and a generator g (the “yellow”). Alice picks a secret exponent a, and Bob a secret b. Then:

• Alice sends A = g^a mod p. Bob sends B = g^b mod p. These are the pots in the post.
• Alice computes B^a mod p. Bob computes A^b mod p.

Both get g^ab mod p, because raising g to the power a and then b is the same as doing it the other way round, and wrapping around the clock along the way doesn't change that. This is Diffie–Hellman key exchange.

With these tiny primes Eve always wins in a blink. The whole defence is in the size of p. Each extra binary digit (bit) doubles the number of hours on the clock, and so doubles the number of exponents Eve might have to try. Alice's work grows far more slowly: by squaring repeatedly (g, g², g⁴, g⁸, …) she can reach any power with about two multiplications per bit.

Real attackers are cleverer than Eve. The best known method for this problem, the number field sieve, is enormously faster than trying every exponent, which is why real primes have 2,048 bits or more rather than 128. Measured against that attack, a 2,048-bit prime gives roughly the security of a 112-bit key (NIST's figure), about 5 × 10³³ tries, not the 10⁶¹⁶ that Figure 4 shows for brute force. In 2015 the “Logjam” researchers estimated that special-purpose hardware costing hundreds of millions of dollars could break a commonly shared 1,024-bit prime, a sum within reach of a national intelligence agency. But even the best known attack still grows faster than any fixed power of the number of bits, while Alice's effort stays modest. The gap widens as the primes grow.

What it doesn't do: tell you who is on the line

There is a hole in everything above. Alice assumed the number B came from Bob. Suppose Eve does more than listen: she sits in the middle, intercepts A, sends Bob her own number instead, and does the same in the other direction. Alice ends up sharing a key with Eve, Bob shares a different key with Eve, and Eve decrypts, reads and re-encrypts everything that passes. Neither notices. This is a man-in-the-middle attack.

Key exchange on its own gives you a secret shared with whoever answered. To know who that is, real protocols add authentication: in TLS, the protocol behind https, the server signs its half of the exchange with a key vouched for by a certificate, which your browser checks.

Who thought of it, and what runs today

Whitfield Diffie and Martin Hellman published the method in November 1976, in a paper called “New Directions in Cryptography”. Ralph Merkle had independently found a way to agree on a key in public (his “puzzles”, proposed as a student project in 1974 and published in 1978), and Hellman later suggested calling it Diffie–Hellman–Merkle key exchange. Unknown to all of them, three mathematicians at GCHQ, the British signals intelligence agency, had got there first: James Ellis showed in 1970 that such a thing was possible in principle, Clifford Cocks found a practical method in 1973 (essentially what became RSA), and Malcolm Williamson described the same exchange as Diffie and Hellman in a secret report in January 1974. It all stayed classified until December 1997.

Your browser today usually does the exchange not on a clock of numbers but on an elliptic curve, a different mathematical setting where the backwards problem is harder still, so keys can be much shorter. A very common choice, X25519 (RFC 7748, 2016), uses 32-byte keys. A large enough quantum computer, running Shor's algorithm, could solve both kinds of discrete logarithm; no such machine exists yet, but recorded traffic could be decrypted later. So since late 2024, Chrome and Firefox also run ML-KEM, a post-quantum method standardised by NIST as FIPS 203 in August 2024, side by side with X25519, and combine the two secrets.