The early history of public-key cryptography

Tracing the roots of particular genres of fiction can be interesting. Ghost stories, for example, were told at least as far back as ancient Greece and Rome, and have just evolved slightly to keep up with the times. Other genres may not have histories this long, but you can usually trace their roots and influences back quite a ways. Knowing the historical context of works of fiction isn’t necessary to appreciate them, but it seems to add an extra level of understanding that might be good for more than impressing people in after-dinner conversation.

Tracing the roots of public-key cryptography can be just as interesting. And just like you don’t need to understand their historical context to appreciate works of fiction, you certainly don’t need to understand the history of public-key cryptography to appreciate how it lets you do all sorts of useful things.

It’s probably the case that far fewer people are interested in the history of public-key cryptography than in the history of ghost stories, so it doesn’t work as well as after-dinner conversation. You’ll probably have to be satisfied with the sense of satisfaction that knowing the history of public-key cryptography for its own sake can give you. This might end up being a bit like the meaningless sense of moral superiority that drivers of standard-transmission cars feel compared to drivers of automatics, but let’s hope that it’s slightly more useful than that.

The first two ideas in public-key cryptography that were both secure and practical were what we now call the Diffie-Hellman and the RSA schemes. In a bit of convoluted history, researchers at the UK’s Government Communications Headquarters (GCHQ) actually invented these schemes first, but the UK government kept their inventions classified for many years.

As early as 1970, John Ellis proposed the idea of public-key cryptography in a paper entitled "The Possibility of Secure Non-Secret Digital Encryption." In 1973, Clifford Cocks showed that Ellis' idea was practical when he invented the RSA scheme. Shortly thereafter, Malcolm Williamson invented the Diffie-Hellman scheme. Cocks' paper is actually dated November 1973 and Williamson's paper is dated January 1974, so only two months passed between the two. Because their inventions were kept classified, the schemes invented by Cocks and Williamson aren’t known today as the Cocks scheme and the Williamson scheme. Instead, they're known by names of the people who independently discovered them a few years later.

A few years after they were invented at GCHQ, academic researchers independently reinvented the Diffie-Hellman and RSA schemes. But when they did this, they did so in the reverse order. In 1977, Whitfield Diffie and Martin Hellman invented the Diffie-Hellman scheme and in 1978, Ron Rivest, Adi Shamir and Ken Adelman invented the RSA scheme. Much like the situation inside GCHQ, the two inventions were separated by only a few months.

Curiously, while the RSA scheme came first in the classified world, the Diffie-Hellman scheme came first outside it.

Later in 1978, Loren Kohnfelder invented the idea of a digital certificate and described it in his undergraduate thesis at MIT. This was enough to allow the creation of public-key infrastructure (PKI) to create and manage digital certificates. There has been lots of innovation in the field of public-key cryptography since the late ‘70s, but the roots of everything that’s followed can be traced back to the first ideas of a few cryptographers at GCHQ over 30 years ago.