Well-VersedLibraryCoverageAbout
2026-08-03 · Technology
Technology · Cryptography

Public-Key Cryptography

Every secret you have sent over the internet was arranged with a stranger, out loud, in front of anyone who cared to listen.

Studio portrait of Whitfield Diffie, an older man with long grey hair and a full white beard, in a dark pinstriped suit and patterned tie, smiling against a pale grey background.
Whitfield Diffie, photographed at the Royal Society, London, in 2017. He had neither a doctorate nor a university post when he took up the problem below, and the people who had both held it to be unsolvable. Photograph by Duncan Hull, CC BY-SA 4.0. Source: Wikimedia Commons, where the author and licence terms for this file are recorded.

For most of the history of secret writing the key gave more trouble than the cipher. Two people who wanted to speak privately had first to agree, privately, on the setting they would both use, which meant meeting in a room, or trusting a courier, or weighting a codebook so that it would sink with the boat before anyone could fish it out. Diffie and Hellman put the commercial version of this plainly in 1976, observing that keys travelled by private courier or registered mail and that nobody opening a relationship with a stranger was going to wait for the briefcase. Cryptographers called it the key distribution problem and mostly treated it as a fact of nature, because it reads as a contradiction. To share a secret you need a private channel. To open a private channel you need to have already shared a secret.

Whitfield Diffie refused to accept that, and he eventually found his way to the one other person taking the question as seriously as he did: Martin Hellman, a young professor of electrical engineering at Stanford. With Ralph Merkle, who had been circling the same idea, they broke it open in November 1976 in a paper for the IEEE Transactions on Information Theory. Forty years later the ACM gave Diffie and Hellman the Turing Award for it, and the IEEE had already put Merkle's name beside theirs on the 2010 Hamming Medal. The paper wastes no time getting to its claim.

ReadDiffie and Hellman, 1976

We stand today on the brink of a revolution in cryptography. The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote cash dispensers and computer terminals. In turn, such applications create a need for new types of cryptographic systems which minimize the necessity of secure key distribution channels and supply the equivalent of a written signature.

Whitfield Diffie and Martin E. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory IT-22, no. 6 (November 1976), opening lines.

Their first idea is easier to follow in paint than in numbers. Two strangers announce a common colour in the open, and each privately stirs in a secret colour of their own. They then swap the resulting mixtures across a channel everyone can watch. Each adds their own secret colour a second time, and both end up holding the identical muddy result, which nobody else can reproduce, because separating paint back into its ingredients is much harder than mixing it. The real version has the same shape. Both sides agree in public on a large prime and a base; each picks a private number and publishes the base raised to that power, reduced modulo the prime; each then raises whatever the other published to their own private number, and the two land on the same value. Anyone listening holds the prime, the base and both published results, and to get further has to run an exponent backwards, the discrete logarithm problem, for which nobody has a fast method.

Diagram showing Alice and Bob each starting with the same yellow common paint, adding different secret colours, exchanging the resulting mixtures over a public channel, adding their own secret colour again, and both arriving at the same dark green common secret.
The Diffie–Hellman exchange in paint. The two mixtures cross in the open and an eavesdropper sees both; the shared colour at the bottom is never transmitted at all. Diagram after A. J. Han Vinck, University of Duisburg-Essen; public domain. Source: Wikimedia Commons, where the author and licence terms for this file are recorded.
Watch Computerphile, “Secret Key Exchange (Diffie–Hellman)”

Nine minutes with Mike Pound of Nottingham, working the exchange through on paper. Watch for the moment he points out that the shared key is never sent, which is the whole trick and the part that sounds impossible until you have seen it done once.

The paper's second idea was still only a promise. Diffie and Hellman described a cipher with two keys, one published to the world for locking and one kept back for unlocking, each uniquely determining the other while the private one stayed out of computational reach; run the same machine backwards, they noticed, and you get a signature that only the holder could have produced. They could not build it. A year later three researchers at MIT did. Ron Rivest, Adi Shamir and Leonard Adleman had been at it for the better part of a year, the first two proposing schemes and the third breaking them. Then on the night of Passover in April 1977, after a seder and a good deal of wine, Rivest lay awake on a couch with a mathematics textbook and had most of the paper drafted by morning. Their system, RSA, hides the private key behind the product of two enormous primes and invites the world to factor it back. Martin Gardner announced it that August in Scientific American under the headline “A new kind of cipher that would take millions of years to break,” printed a 129-digit number with a hundred-dollar prize on it, and hedged the title with Poe's line that human ingenuity cannot concoct a cipher which human ingenuity cannot resolve. It took until April 1994.

· · ·

None of which was first. Reading a wartime Bell Labs paper on the protection of voice communications, a GCHQ mathematician named James Ellis had worked out by 1970 that private conversation without a shared secret ought to be possible. He called it non-secret encryption and spent three years failing to find a method. In 1973 Clifford Cocks, weeks out of Cambridge, had the problem described to him in conversation and, by his own account, wrote out what the world would later call RSA that same evening in about half an hour, without notes. The following year Malcolm Williamson, who had been at school with Cocks and had taken a gold medal at the 1968 International Mathematical Olympiad, produced the key exchange. All of it was classified, none of them could say a word, and GCHQ did not release the story until December 1997. Ellis had died that 25 November, a month short of it.

Aerial photograph of the circular GCHQ headquarters building at Cheltenham, a vast ring of glass and steel around a central garden courtyard, surrounded by concentric car parks.
GCHQ, Cheltenham, from the air in 2004. The ring building, universally known as the Doughnut, opened only in 2003, long after Ellis, Cocks and Williamson did the work; their offices were in the older huts and blocks it replaced. Ministry of Defence, Open Government Licence. Source: Wikimedia Commons, where the author and licence terms for this file are recorded.

You use both halves dozens of times a day. The padlock beside a web address means the browser and the server have run a handshake in which public-key methods let them settle on a session key over an open wire, after which they switch to ordinary shared-key encryption for the traffic itself, because the two-key operations are much too slow to carry a video. The same mathematics run in reverse is what certifies that the site is who it claims to be, and what proves a software update came from its author rather than from someone on the network. All of it stands on two problems being hard: factoring a large number, and running an exponent backwards. Peter Shor showed in 1994 that a sufficiently large quantum computer would dissolve both, which is why encrypted traffic is being recorded today by people content to read it in fifteen years, and why in August 2024 NIST published the first three federal standards built to survive that machine. The migration off Diffie, Hellman and Rivest's arithmetic has already begun.

Up next
The Map and Compass
The needle lies, and the map tells you by exactly how much.
Read →

Images on this page are reused from Wikimedia Commons. Each is linked to its file page, where the author and the licence terms for that file are recorded. Thumbnails in “Up next” are credited on the lesson they link to.