I went to presentation yesterday where a speaker told the audience the tale of how the three guys from MIT invented public-key cryptography. You know, the RSA trio. I mentioned that they were not the sole inventors (hey, Diffie sits on the crypto panel at RSA for a reason) but was soundly shut-down.
After the presentation I did a little research to double-check and while I thought Diffie-Hellman and Merkle were important, I didn’t realize that another group actually pre-dated even their publication. It turns out that there is a paper from 1987 called The Story of Non-Secret Encryption written by James Ellis. This paper not only describes ground-breaking work done prior to Diffie-Hellman and Merkle, but it gives credit to Bell Labs in 1944 for helping instigate the modern public key cryptography concepts.
Source is available here: http://www.cesg.gov.uk/site/publications/media/ellis.pdf
A paper written by Clifford Cocks (November 20, 1973) called “A Note on Non-Secret Encryption” is also relevant.
Here’s a nice review of the actual history, as told by the Living Internet:
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.
It just goes to show, don’t always believe what you hear in presentations…