Public Key Cryptography (PKC) History

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 ca 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. At the same time, theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science. -Whitfield Diffie and Martin Hellman; "New Directions in Cryptography"; IEEE Transactions on Information Theory; Nov. 1976.

Public Key Cryptography (PKC) uses two keys, a "public key" and a "private key", to implement an encryption algorithm that doesn't require two parties to first exchange a secret key in order to conduct secure communications. In a nice mathematical twist, this conceptual breakthrough also enables an elegant implementation of digital signatures.

For thousands of years, it was unanimously agreed in the cryptography community that the only way for two parties to establish secure communications was to first exchange a secret key of some kind. This seemed to be simple common sense: if the recipient didn't have a secret to give them some leverage, how could they be in a better position to decrypt the message than an eavesdropper? Practically speaking, this meant that one of the parties first had to send a trusted person to the second party with a secret key (which typically took a fair amount of time), or send the key through an existing encryption channel that couldn't be completely trusted (if it was broken, all of the keys transmitted over that channel were also broken).

Nevertheless, there was increasing motivation to examine the problem for both military and commercial use. The task of military encryption key management had greatly expanded with the growth in electronic communications networks, and the number of parties that needed to communicate to organize a large-scale military operation such as World War II had numbered in the thousands. Practical experience with military communications showed that much of the conversations had ended up unencrypted, simply because there wasn't time to establish a secure connection. In the commercial domain the problem was quickly growing to become even more challenging, with increasing use of electronic networks to conduct sensitive business communications and financial transactions, often between parties from different organizations that had not previously communicated or had the chance to exchange encryption keys beforehand.

The subsections below describe the history of the development of the seemingly magical solution to these problems, just in time for use on the Internet -- Public Key Cryptography (PKC):

• Merkle, Diffie, Hellman
• Rivest, Shamir, Adleman (RSA)
• Ellis, Cocks, Williamson

Diffie, Hellman, Merkle. The first researchers to discover and publish the concepts of PKC were Whitfield Diffie and Martin Hellman from Stanford University, and Ralph Merkle from the University of California at Berkeley. As so often happens in the scientific world, the two groups were working independently on the same problem -- Diffie and Hellman on public key cryptography and Merkle on public key distribution -- when they became aware of each other's work and realized there was synergy in their approaches. In Hellman's words: "We each had a key part of the puzzle and while it's true one of us first said X, and another of us first said Y, and so on, it was the combination and the back and forth between us that allowed the discovery."

The first published work on PKC was in a groundbreaking paper by Whitfield Diffie and Martin Hellman titled "New Directions in Cryptography" in the November, 1976 edition of IEEE Transactions on Information Theory, and which also referenced Merkle's work. The paper described the key concepts of PKC, including the production of digital signatures, and gave some example algorithms for implementation. This paper revolutionized the world of cryptography research, which had been somewhat restrained up to that point by real and perceived Government restrictions, and galvanized dozens of researchers around the world to work on practical implementations of a public key cryptography algorithm.

Diffie, Hellman, and Merkle later obtained patent number 4200770 on their method for secure public key exchange.

Rivest, Shamir, Adleman (RSA). The Diffie-Hellman-Merkle key exchange algorithm provided an implementation for secure public key distribution, but didn't implement digital signatures. After reading the Diffie-Hellman paper, three researchers at MIT named Ronald Rivest, Adi Shamir, and Leonard Adleman (RSA) began searching for a practical mathematical function to implement a complete PKC approach. After working on more than 40 candidates, they finally discovered an elegant algorithm based on the product of two prime numbers that exactly fit the requirement for a practical public key cryptography implementation.

RSA's breakthrough was first publicized by Martin Gardner in August, 1977, in his widely read column Mathematical Games in the magazine Scientific American, and included an offer from RSA to mail a complete report on the PKC method to anyone that requested it. Recognizing the power of the idea and fearing its use by non-government elements, the US National Security Agency (NSA) requested that RSA stop distributing the report. However, when queried, they were unable to provide a legal basis for their request, so the university bravely decided to continue distribution. In February, 1978, RSA published a more detailed paper on their work in the journal Communications of the ACM, and the PKC cat was out of the bag for good.

In a foreshadowing of the struggle over PGP, the legal battle with the US Government over the RSA algorithm went on for several years. In one of the most comical incidents, RSA was written up by Adam Back as a 5 line PERL program, for which Peter Junger requested and received written instructions from the US Government prohibiting export outside of the country. Many people subsequently put the program in their email signatures or printed it on t-shirts to protest the Government restrictions.

In 1982, RSA formed the company RSA to market their PKC algorithm in electronic security products. They obtained patent number 4405829 on the RSA algorithm in the US, but could not obtain a patent internationally because they had already published the idea and most other countries bar retroactive patenting of open source concepts.

Whether as a licensed product, as part of PGP, or implemented by others, the RSA algorithm has become the foundation of an entire generation of public key cryptography security products. Because it provides secure communications over distances between parties that have not previously met, RSA provides the ideal mechanism required for private communications over electronic networks, and forms the basis of almost all of the security products now in use on the Internet for financial and other private communications, including most organizational level Public Key Infrastructure (PKI) systems.

In September 2000, the US patent for the RSA algorithm expired, for the first time enabling software developers everywhere to freely include this PKC standard in their products.

Ellis, Cocks, Williamson. In December, 1997, it was revealed that researchers at the GCHQ organization did some work in the early 1970's in the field of "non-secret encryption", which is related to public key cryptography, but without inclusion of the concept of digital signatures. However, these claims are not verifiable since the work was not published, and there are no evidentiary artifacts available such as original copies of the papers (although modern transcriptions are linked below). Therefore, in keeping with a long tradition, credit for the development and publication of PKC must remain with the researchers who first published their work in the open scientific literature, as described above. The work of the GCHQ researchers is described below as related by James Ellis in his paper The History of Non-Secret Encryption.

Ellis began thinking about the shared secret key problem in the late 1960's when he discovered an old Bell Labs paper from October, 1944 titled "Final Report on Project C43", describing a clever method of secure telephone conversation between two parties without any prearrangement. If John calls Mary, then Mary can add a random amount of noise to the phone line to drown out John's message in case any eavesdroppers are listening. However, at the same time Mary can also record the telephone call, then later play it back and subtract the noise she had added, thereby leaving John's original message for only her to hear. While there were practical disadvantages to this method, it suggested the intriguing logical possibility: there might be methods of establishing secure communications without first exchanging a shared secret key.

Ellis thought about this seemingly paradoxical idea for awhile, and while lying in bed one night developed an existence proof that the concept was possible with mathematical encryption, which he recorded in a secret CESG report titled The Possibility of Non-Secret Encryption in January, 1970. This showed logically that there could be an encryption method that could work without prior prearrangement, and the quest in GCHQ then turned to find a practical example.

The first workable mathematical formula for non-secret encryption was discovered by Clifford Cocks, which he recorded in 1973 in a secret CESG report titled A Note on Non-Secret Encryption. This work describes a special case of the RSA algorithm, differing in that the encryption and decryption algorithms are not equivalent, and without mention of the application to digital signatures. A few months later in 1974, Malcolm Williamson discovered a mathematical expression based on the commutativity of exponentiation that he recorded in a secret report titled Non-Secret Encryption Using A Finite Field, and which describes a key exchange method similar to that discovered by Diffie, Hellman, and Merkle. It is not known to what uses, if any, the GCHQ work was applied.