The Academic History

During the 1960s the cost of computers decreased dramatically. In 1965¹ computer speed jumped as integrated circuits were introduced into the computing world. This allowed businesses to buy computers, fast enough to perform a level of encryption which could ensure security from rivals. These technological advanced also allowed the military to increase their own computing capabilities. This amplified an existing problem of how to securely distribute the encryption key.

Ever since the birth of encryption the key had always had to be exchanged between the sender and the intended recipient. The most secure way for this to happen was for the two parties to meet and for one to tell the other. This was obviously not feasible for government agencies, the military and large corporations who were, by the 1960's sending hundreds if not thousands of electronic messages over potentially insecure mediums. Thus the method used by almost all large information distributors was to employ couriers to exchange the new keys on a monthly, weekly or even daily basis. This was costing a large amount of money and was threatening to impede any increase in size of communication networks for governments and corporations in the future. This third party was also a weak link in the communications chain. No matter how secure the encryption protocol used if a rival gained a copy of the key then no message was secure until the key was next changed.

In the mid 1970s a group of academics formed to try to solve what had been dismissed by many as an unsolvable problem. Whitfield Diffie, Martin Hellman and Ralph Merkle worked on this problem at Stanford University, California, US. Hellman eventually solved this problem after two years of research and the trio created the Diffe-Hellman-Merkle key exchange. This key exchange, whilst secure was not perfect as it relied upon a number of exchanges between the sender and recipient and as such could take a long time if the two parties were not available at the same time.

Around this time Whitfield Diffie, who had been working on an entirely different approach, had a breakthrough. He outlined the idea of Public Key Cryptography. The basic premise for this was that a different (asymmetric) key could be used for Encryption and Decryption. This would allow the recipient to give out an encryption (public) key to anyone in the world without need for secrecy and keep a decryption (private) key to decrypt any messages these sources may send them.

The idea was published in summer 1975, but with no example of a formula which could achieve such an encryption the idea was not implementable and, as such not yet useful. At this time many scientists joined in the hunt for an algorithm which could be used to implement this system. Three of these were: Ron Rivest, a computer scientist; Adi Shamir, another computer scientist and Leonard Adleman a mathematician who worked in the Computer Science building at Massachusetts Institute of Technology (MIT).

In April 1977 Rivest, whilst unable to sleep finally realised a way to create such a key using a one way function. He spent most of the night writing up his idea and the next day presented it to Adleman and Shamir. They agreed that this was indeed a workable solution to the problem. The first report of this was in the Scientific American² magazine with a challenge to crack the cipher. Once patents were secured the full details were disclosed. The challenge was finally completed seventeen years later when a group of 600 volunteers using excess CPU time broke the cipher and discovered the answer. RSA revolutionised the world in ways which will be discussed later in this report but this is not a complete history of public key encryption. There is a secret history which only came to light in the late 1990s.

The Secret History

In the late 1960s the problem of key distribution was also being examined by the Government Communication Headquarters) (GCHQ) in Chelmsford UK. The British, like many other countries round the world were having the problems with key distribution discussed earlier in this section. The responsibility for finding a solution to the ever increasing cost of key distribution was given to a physicist named James Ellis. Ellis was reported to be genius who would attack every assumption previously made of a problem. The first thing he looked at was whether the key must be kept from potential interceptors. This was an assumption with no proof and as such it could be tested. It was at this point he formed the theory of public key encryption (or Non-secret encryption as Ellis called it). This was in 1969, six years before Whitfield Diffie reinvented the idea in the academic community. However having reached this point the problem of implementation was just as hard to solve in the security community as it was in the academic one, if not harder as there were less people privy to the problem. After three years of work by GCHQ mathematicians no progress had been achieved. In September 1973 a recent graduate of Cambridge university, Clifford Cox joined GCHQ and was after a couple of week told about the problem. The same afternoon, whilst waiting for a project to be assigned to him Cox started to work on the public key encryption problem. Having studied number theorem at university he swiftly identified prime numbers and factoring as a reasonable starting point and solved the problem the same afternoon. In one day Cox solved a problem which had been an impasse at GCHQ for three years and would cause the same problems in the academic community two years later.

Whilst it is not technically part of public key encryption, and as such not strictly on the topic of this report; it is an interesting note to mention that the Diffe-Hellman-Merkle key exchange was discovered at GCHQ at just before Martin Hellman by Malcolm Williamson another newly recruited Cambridge graduate. Williamson, whilst trying to disprove Cox's method for PKE accidentally stumbled upon the method for exchanging keys securely.