Most of the privacy technology used on the Internet, and in many other places, is under-pinned by public-key cryptography; most notably, public-key key agreement protocols and public-key encryption algorithms. Almost all of this technology is based on two incredibly important mathematical algorithms: the Diffie-Hellman key agreement protocol (publicly discovered in 1976) and the RSA encryption algorithm (publicly discovered in 1978). If we hadn’t had these two algorithms, then the security world would have been a very different place. And we almost didn’t have them…

It’s relatively well known now that, before the whole concept of public-key cryptography was publicly discovered by Whitfield Diffie and Marty Hellman in 1976, it was discovered several years before by the UK Government’s military cryptography group at GCHQ.

The notion of public-key cryptography was first invented by James Ellis in 1969 — seven years before the idea would be re-discovered in the public domain. However, Ellis couldn’t come up with a practical system — just a proof of concept system that would never be useable in practice. A practical system was not discovered until 1973, when Clifford Cocks invented the algorithm that we now call the RSA algorithm. The idea, he says, came to him overnight. A few months later, another researcher at GCHQ, Martin Williamson, invented the algorithm that we now call Diffie-Hellman, also overnight.

What is less well-known, and I only recently discovered, is that the UK government also considered patenting the ideas.

This revelation was announced during an invited talk by the cryptography pioneer Clifford Cocks at the Eurocrypt 2008 research conference — the largest and most highly regarded European conference in cryptographic research — which was held this year in Istanbul, Turkey. Geography buffs will be pleased to hear that it was held on the Western bank of the Bospherus river — if it had been held on the Eastern bank, then it would technically have had to be the Asiacrypt conference.

And so it was to a packed house of cryptographers, that Clifford Cocks announced that the UK Government had considered filing a patent on the Diffie-Hellman protocol and the RSA algorithm — the two algorithms which underpin privacy almost everywhere on the Internet. There was a collective gasp, from myself included, but I don’t think that I fully understood the implication of the revelation at that time. Naively, I only thought of the revenue that could have been created.

It’s not clear whether the UK Government would have actively sought to repress public-key cryptography during the 1980s. I think it’s fair to say that most major powers were worried about the proliferation about strong cryptography. Early attempts by the ISO standardisation committee to standardise the RSA algorithm in that decade were blocked for political reasons. However, it’s not really fair to say that this implies that the UK Government would have sought to control the technology, but if they had wanted to repress it, then a patent would have been the perfect weapon in their arsenal.

Regardless of the political controversy, it is fair to say that it is unlikely that RSA Labs are unlikely to have been formed if someone else had held the patent to the RSA algorithm, and this would have profound effects on the development of security technology. After the ISO standardisation committee failed to standardise public-key cryptography, it was RSA Labs that stepped in to help, by producing the RSA PKCS series of standards. These standards underpin the use of public-key key agreement and public-key encryption everywhere.

No public-key cryptography standards means there wouldn’t have been any secure commercial implementations, which means there wouldn’t have been a secure and private Internet.

So, even if the UK Government hadn’t inhibited the use of public-key technology, the patent would have probably had meant that we didn’t develop standards for public-key cryptography for many, many years. We might, at this stage, be as much as ten years behind on the development of practical privacy systems on the Internet.

So who should we thank for the development of useable public-key cryptography? Well, clearly we should thank the scientists involved in the discovery, both the governmental inventors of public-key cryptography (Ellis, Cocks, and Williamson) and their commercial counterparts (Merkle, Diffie, Hellman, Rivest, Shamir, and Adleman). However, in a weird way, we also need to thank the GCHQ lawyers who claimed that a patent on these ideas was unobtainable: if not for these lawyers, then we wouldn’t have the security sector that we have today.

Dr. Alex Dent