PLATFORM16

Diffie-Hellman

CIPHER

WHEN

FROM

STATUS

Every cipher on the earlier platforms has the same weak spot: before you can send a secret, you and your friend must already share one, the key. For two thousand years that meant couriers, codebooks and sealed bags. In 1976 two researchers at Stanford showed that two people who have never met can build a shared key by talking in public, while an eavesdropper hears every word.

The machine

Paint first, then a clock of numbers

The paint version is the picture most teachers use. Mixing paint is easy and unmixing it is practically impossible, so Alice and Bob can send mixed pots in the open. Pick each person's secret colour and step through it.

The real thing works the same way with arithmetic on a clock. The clock has p hours (p is a prime), and "multiply by g" moves the hand. Turn the two knobs to choose private numbers a and b, then run the exchange: watch each hand walk round, the two public numbers cross the line, and both people arrive at the same hour.

Break it yourself

You are Eve

You tapped the public line and heard everything: the size of the clock, the base, and the two numbers Alice and Bob sent. Then they locked a message with their shared key. Find one of their private numbers by trying powers on the clock, rebuild the key, and type it in to unlock the board.

ARRIVED · CIPHER CRACKED

The story

Whitfield Diffie had spent years travelling around the United States thinking about one question: how could strangers, say two people who meet on a computer network, communicate in secret without first meeting to swap keys? In 1974 he teamed up with Martin Hellman, a young professor of electrical engineering at Stanford. Their paper New Directions in Cryptography appeared in November 1976 and opened with the confident line that cryptography stood on the brink of a revolution.

The idea at its heart was a one-way street. Multiplying a number by itself on a clock of hours is easy; given only where the hand stopped, working out how many times it was done (the "discrete logarithm") seems to be very hard when the clock is huge. Each side keeps its count private and sends only where its hand stopped. Diffie and Hellman also sketched the wider idea of public-key cryptography, a lock with one key to close it and another to open it, though they did not yet have a way to build one. That came a few months later, on the next platform.

A third name belongs here. Ralph Merkle, then a student at Berkeley, had already come up with a way to agree a key in public using a pile of small puzzles, and his work helped shape theirs. Hellman later suggested that the scheme should be called Diffie-Hellman-Merkle.

The secret version

In 1997 the British signals agency GCHQ revealed that its own people had got there first. James Ellis had proposed "non-secret encryption" around 1970; Clifford Cocks found a practical public-key cipher in 1973, and Malcolm Williamson worked out what is essentially the Diffie-Hellman exchange soon afterwards. It all stayed classified for more than twenty years, so the public world found the ideas independently.

Today a version of this exchange runs whenever your browser opens a secure connection. It usually uses elliptic curves rather than a clock of whole numbers, because the curves give the same safety with much shorter numbers. Diffie and Hellman received the Turing Award, computing's highest honour, for the 1976 paper in 2015.

How it was broken

The exchange itself has never been broken. With a prime of 2048 bits (more than 600 decimal digits) nobody knows how to run the clock backwards in any reasonable time. Attacks go round it instead: a man in the middle who pretends to be Bob to Alice and Alice to Bob (which is why the exchange is always combined with some way of checking who you are talking to), or numbers that are too small. In 2015 researchers showed that many servers still accepted old, deliberately weakened 512-bit settings left over from export rules of the 1990s, and broke those connections.

Large quantum computers, if they are ever built, could run the clock backwards quickly. That is why new "post-quantum" key exchanges are being added alongside the old one.