The problem, which looks impossible

Until 1976, everyone who thought about secret messages agreed on one thing: before two people can exchange secrets, they must first share a key, and sharing the key is the hard part. Armies used couriers with locked briefcases. Banks sent officers on aeroplanes. Embassies used diplomatic bags. The message could travel over anything; the key had to travel over something trustworthy.

That works when the two parties can plan ahead. It does not work at all for what we now do constantly: your browser has never met the shop's web server, no courier is available, and you want to buy something in the next four seconds.

So here is the problem in its pure form. You and a stranger are in a room full of people. Everyone can hear everything either of you says. When you stop talking, you and the stranger must both know the same number, and nobody else in the room may know it. You have never met and you share nothing in advance.

Most people's first reaction is that this is obviously impossible. It is not, and the reason is worth an afternoon of anyone's time.

Paint

The standard illustration is mixing paint, and it is good enough to carry the whole idea.

Suppose mixing two colours is easy but un-mixing them is impossible - given a bucket of muddy green, no one can tell you which two colours went in or in what proportion. That single asymmetry is all we need.

  1. You and the stranger agree, out loud in front of everybody, on a starting colour. Say yellow. Everyone in the room now knows: yellow.
  2. You privately choose a secret colour - red - and never tell anyone. You mix your red into a pot of the public yellow, producing orange, and hand the orange pot to the stranger. Everyone sees the orange.
  3. The stranger privately chooses their own secret - blue - mixes it into their own pot of yellow, producing green, and hands you the green. Everyone sees the green.
  4. You add your secret red to the green you were given. The stranger adds their secret blue to the orange they were given.

You have both ended up with yellow plus red plus blue. The same colour. And the room has seen yellow, orange and green - and to get your shared colour from those, they would have to un-mix one of them, which we said is impossible.

That is . Everything else is arithmetic that behaves like paint.

The arithmetic that behaves like paint

The trick is to find numbers that mix easily and un-mix impossibly. The operation used is exponentiation with a remainder, and if the phrase means nothing to you, think of a clock.

On a twelve-hour clock, nine o'clock plus six hours is three o'clock. The number went past twelve and wrapped around, and here is the point: once it has wrapped, you cannot look at the answer and tell how many times it went round. Three o'clock might mean three, or fifteen, or twenty-seven. Information has been destroyed, cheaply and irreversibly.

Now do it with multiplication instead of addition, on a clock with an enormous prime number of hours instead of twelve. Take a public number, multiply it by itself a secret number of times, and keep only the remainder. Multiplying is fast. Working backwards from the remainder to how many times you multiplied - the discrete logarithm - is, as far as anybody has published in fifty years, hopeless for numbers of the size we use.

That is the whole of it. Here is the only equation in this article, and you can read it as a sentence:

shared secret = (their public value) ^ (my secret) mod p

Both sides compute that, each using their own secret and the other's public value, and both get the same answer - for the same reason yellow-plus-red-plus-blue equals yellow-plus-blue-plus-red. The order of mixing does not matter. The eavesdropper has the two public values and the starting number, and needs a secret to combine them, and cannot get one without solving the problem nobody can solve.

The part that most explanations leave out

Everything above is true and it is also, on its own, not enough - and this is the part a practitioner needs and a general reader deserves.

At the end of the exchange you share a secret with somebody. Diffie-Hellman gives you no way whatever to know who. If a third party sits between you and the stranger and runs the whole procedure twice - once with you, pretending to be the stranger, once with the stranger, pretending to be you - then they hold two shared secrets, decrypt everything from one side, read it, and re-encrypt it to the other. Both of you see a perfectly working secure connection. This is the problem, and it is not a flaw in Diffie-Hellman; it is a question Diffie-Hellman does not answer.

The answer comes from somewhere else: certificates, which are the subject of their own article and which exist to let one side prove it is who it claims. Every browser padlock is the two halves together - Diffie-Hellman to agree a secret nobody else knows, and a certificate to establish that the somebody at the other end is the shop and not a stranger in the middle.

Why this is also why old traffic stays secret

There is a second consequence worth having, because it explains a phrase that appears in every security discussion.

Because the secrets in the exchange can be thrown away the moment the conversation ends, an attacker who records your encrypted traffic today and steals the shop's long-term key in five years still cannot read it: the key that encrypted that conversation was never stored anywhere and no longer exists. That property is called forward secrecy, and it is why the modern protocol uses this exchange for every connection rather than encrypting a key with the server's permanent one.

Where it came from

and published New Directions in Cryptography in November 1976, and its first line is not the usual academic throat-clearing: we stand today on the brink of a revolution in cryptography. They were right. had been working on a related idea independently at Berkeley, and Hellman's own account of the collaboration is generous and worth repeating - each had a key part of the puzzle, and it was the back-and-forth between them that produced the discovery. Hellman argued afterwards that the scheme should carry Merkle's name too. All three are on the 1977 patent.

Two footnotes belong with it, and they are the reason this article sits in a security catalogue rather than a maths one.

They were not first, but they were first to tell anyone. At GCHQ, the British signals intelligence agency, had conceptualised the possibility around 1969-70 and had produced an algorithm for it in 1973. A former director of the American agency later said that two-key cryptography had been found there roughly a decade before 1976, without giving details. None of that reached the public, and so none of it protected anybody. The comparison is the argument for open research in a single data point: the classified work existed and changed nothing; the published work changed everything.

And publishing it was a fight. Diffie and Hellman also published a paper arguing that the American agency had pressured IBM into weakening the DES standard by limiting its key to 56 bits - the same 56 bits that the Electronic Frontier Foundation later demonstrated could be broken for a quarter of a million dollars. The response was a concerted effort to restrict the distribution of their research, which is the opening chapter of the crypto wars and one of the reasons this site has an article about them.

They received the Turing Award for the work in 2015, thirty-nine years later.

The one thing to remember

If you take nothing else: two people who have never met can agree on a secret in public, because some operations are easy to do and impossible to undo. Everything else in modern security is built on top of that sentence, and the people who first said it out loud were nearly prevented from doing so.

Sources