Public-key cryptography was invented twice

Public-key cryptography was invented twice. Three mathematicians at Britain's signals intelligence agency GCHQ found it first, between 1969 and 1974, and weren't allowed to tell anyone. Researchers at Stanford, Berkeley and MIT found it again, independently and in public, between 1974 and 1977, and published at once. The second group changed the world, while the first group's work stayed classified until 1997. Here are both stories with their dates, and the reason a secret invention does almost nothing until someone shares it.

The problem: how do you share a key?

Until the 1970s every cipher in this encyclopedia needed the sender and the recipient to share a secret key before they could talk. That works for an army, which can send couriers with codebooks, and for two people who can meet. It breaks down for a bank talking to a million customers, or two strangers on a network. The key has to travel to the other side over some channel, and if anyone can watch that channel, the key is lost. This is the key distribution problem. The question of the 1970s was whether two people could agree on a secret in public, in front of an eavesdropper, with no earlier secret between them. It sounds impossible, and it's what you do every time you open a secure web page. The treasure-chest puzzle and the three-pass protocol show how the idea feels at a small scale: with padlocks, you lock a box, send it, have the other side add a lock, and so on, and no key ever travels.

The first discovery: GCHQ, 1969 to 1974

James Ellis was a GCHQ engineer who'd joined the agency in 1952. By his own account the seed was a wartime Bell Labs report on Project C43, a voice-privacy scheme in which the receiving party adds random noise to a call the sender has masked, and later subtracts it. The line never carries the message in the clear, and nobody has to deliver a key by hand. From this Ellis reasoned that "non-secret encryption" might exist: a lock that anyone can close but only the intended recipient can open. In January 1970 he wrote an internal report, The Possibility of Secure Non-Secret Digital Encryption. It argued the idea was possible in principle, and it didn't yet say how.

A mathematician, Clifford Cocks, found the way. On November 20, 1973 he wrote an internal document describing a system that is in essence RSA: the public key is the product of two large primes and an exponent, and the private key needs the primes. A colleague, Malcolm Williamson, wrote a report on January 21, 1974, Non-secret encryption using a finite field, which does what the Diffie-Hellman key exchange does. So by 1974 Ellis, Cocks and Williamson had found the main ideas of public-key cryptography. The work was classified. They couldn't publish it, discuss it with academics or patent it. And because it stayed classified until 1997, it missed the mainstream research that grew up around the public discoveries below.

The second discovery: three groups in public

• Ralph Merkle, 1974. A student at Berkeley, Merkle devised Merkle's puzzles. Bob sends Alice a great many small puzzles, each hiding a key and an identifier, and each solvable with modest effort. Alice solves one at random and sends back its identifier in the clear. Now the two share a key, and an eavesdropper has to solve many puzzles to find which one Alice chose, so she needs about the square of the work Alice and Bob did. He conceived it in 1974 and published it in 1978. It's only a quadratic gap, which isn't enough for real security (in 2008 Boaz Barak and Mohammad Mahmoody-Ghidary showed the gap can't be improved), but it proved the thing could be done at all.
• Whitfield Diffie and Martin Hellman, 1976. At Stanford they published New Directions in Cryptography in IEEE Transactions on Information Theory in November 1976. It described public-key cryptography in full: public and private keys, key exchange, and digital signatures. It also gave a practical key exchange, based on the difficulty of the discrete logarithm (the Diffie-Hellman page). They proposed a public-key encryption scheme but couldn't yet build one. In 2006 Hellman suggested calling the exchange Diffie-Hellman-Merkle, to recognize Merkle's part.
• Ron Rivest, Adi Shamir and Leonard Adleman, 1977. At MIT, they took up Diffie and Hellman's challenge to find the encryption scheme. By the usual account, Rivest worked out the key idea in April 1977, during a night after a Passover dinner at a student's house. A description appeared in Martin Gardner's Scientific American column in August 1977, a patent application followed in December 1977, and the paper itself came out in Communications of the ACM in February 1978. MIT was granted US patent 4,405,829 on September 20, 1983, and RSA Security released the algorithm into the public domain on September 6, 2000, two weeks before the patent expired.

The two inventions side by side

Read down the first three rows and the GCHQ date comes first every time, by anywhere from two to nearly seven years. The last row flips the order, and it's the row that decided who shaped the field. The people who published in 1976 got the papers, the students, the standards and the patents. The people who got there first got a footnote, twenty years late.

The reveal

Ellis died on November 25, 1997. A few weeks later, on December 18, 1997, Cocks gave a public talk on GCHQ's contribution, and the world learned that the three had been there first. In March 2016 GCHQ's director spoke at MIT about the work of Ellis, Cocks and Williamson. The fair judgment isn't that the public inventors lacked originality. They had no knowledge of the GCHQ work and found the ideas independently. They published, and they built the field of public cryptography on them: papers, attacks, patents, products, standards. The secret inventors' work, however brilliant, didn't propagate. Nobody could build on it, check it, break it, or put it into a browser. An invention that isn't shared doesn't change the world until someone shares it.

What came next

The public discoveries opened the door to everything in the public-key section of the cipher encyclopedia: ElGamal (1985), elliptic-curve cryptography (1985), the PGP and SSL era, and today's X25519 exchange in nearly every secure connection. The quantum age brings the story full circle. The same factoring and discrete-logarithm problems that RSA and Diffie-Hellman rest on are the ones post-quantum cryptography is being built to replace, using problems of a different kind.

How cipher.ink uses this

cipher.ink uses a shared secret, not a public-key scheme: a passphrase, or a random key carried in the link after the #, and you deliver the key over a channel you choose (why the part after # never reaches the server). That's the symmetric world the 1970s inventions set out to improve on. The key distribution problem hasn't gone away, and it's the reason the passphrase and the link should travel by different routes. Public-key cryptography is what lets your browser trust the connection to this site, through TLS, before any of it starts.