Milestones:Invention of Public-key Cryptography, 1969 - 1975

Invention of Public-key Cryptography, 1969-1975

At Great Britain's Government Communications Headquarters (GCHQ), by 1975 James Ellis had proved that a symmetric secret-key system is unnecessary and Clifford Cocks with Malcolm Williamson showed how such 'public-key cryptography' could be achieved. Until then it was believed that secure communication was impossible without exchange of a secret key, with key distribution a major impediment. With these discoveries the essential principles were known but were kept secret until 1997.

The plaque may be viewed at Government Communications Headquarters (GCHQ) Cheltenham, England. Themore publicly-accessible plaque is in the Cheltenham Art Gallery and Museum. Clarence St, Cheltenham, 51.901226 -2.077916.

Except for very simple cryptographic codes (such as substitution ciphers which can be easily broken by a letter-frequency analysis), the security of all methods of encryption was dependent upon the exchange of a secret key (or code-book) between the sender and the intended recipient.

The basic assumption was that a secure code would be such that an exhaustive analysis (e.g. trying all possible keys) would take so much computer power and so much time as to be non-feasible. Even if the eavesdropper knew the encoding algorithm, the decoding process would be too difficult without having access to additional data, of which the acquisition of some or all of the secret key would be most helpful.

Secure codes were therefore generally regarded as incapable of being ‘broken’ unless the eavesdropper could acquire information about the secret key.

The vulnerability of such codes to knowledge of the key was therefore their ‘Achilles heel’ and secure distribution of keys was a major operational problem.

It was taken for granted by the ‘experts’ in cryptography that maintaining the secrecy of the key was a necessary aspect of all secure communications, and indeed this was an assumed ‘axiom’ of cryptography. Therefore secure communications using a public key was considered impossible, and so not deserving of investigation.

It was within this framework that James Ellis, a physics graduate of Imperial College, University of London, who moved to GCHQ from Dollis Hill in April 1965, was asked in 1969 to investigate methods of key distribution, which was seen as a most expensive and serious limitation to the increased use of secure communications in military contexts.

By the end of 1969, it seems that he had demonstrated that public-key cryptography was possible, and had convinced his superiors at GCHQ of this. However, James Ellis was not a mathematician and he had no ideas for successful implementation of the concept. It is likely that many GCHQ experts tried to find a solution, but without success. In 1973, Clifford Cocks, a mathematics graduate from Cambridge, England, with expertise in number theory, joined GCHQ. He was asked to find a basis for implementing public-key cryptography (Ellis’s concept) and it is claimed that he found a solution within half an hour.

The method did not find immediate use because the computing facilities of the time were not adequate, and so the concept continued to be regarded as ‘impractical’.

In 1974, Malcolm Williamson, who was another mathematician who had graduated from Cambridge, joined GCHQ, and while trying to find a ‘flaw’ in Cocks’ idea, he instead found another method, which was essentially the Diffie, Hellman and Merkle public-key exchange.

All the essentials of public-key cryptography had been discovered by Ellis, Cocks and Williamson by 1975. However, because of the context of the discoveries (e.g. a government research environment where all were obliged to maintain perpetual secrecy about their work) it was not until a conference of the Institute of Mathematics and its Applications held at Cirencester, England in December 1997 that Cocks was given permission to speak publicly about their work. The audience included experts on cryptography who were able to recognise the significance of what had been done. By that time, the public recognition of the invention of public key cryptography had been allocated to the researchers at Stanford and MIT [3], and even now, it is not unusual for publications describing the origins of public-key cryptography to completely ignore or overlook the prior discovery at GCHQ, Cheltenham [4]. Unfortunately, James Ellis died (aged 73) just before public credit for his work could be given.

Cryptography was at one time of serious interest only to governments (wishing to secretly intercept the communications of both friendly and enemy nations) and to military commanders during warfare. It was also of interest as a mathematical pastime for school-children, amateur mathematicians and puzzle-solvers.

Immediately prior to the availability of public-key cryptography, the primary method used for commercial applications was the Data Encryption Standard (DES), developed with US Government sponsorship from an IBM product called ‘Lucifer’. The DES used a 56-bit key, which was small enough that messages could be deciphered within a reasonable time by organisations (such as the US government) with access to huge computing resources, but was large enough that commercial organisations, with the computers available at the time, could not in practice decipher the messages without the key. It was therefore considered ‘sufficient’ for commercial needs at the time. However the problem of ‘key distribution’ remained and this was a severely limiting factor to the application of secure communications outside government and military contexts.

Overcoming the need for key-distribution removed a barrier of such significance that the invention of public-key cryptography could be regarded as one of the greatest achievements of cryptography.

The availability of public-key cryptography has led to many commercial applications which are at the heart of the ‘digital revolution’ of the present time. Secure electronic funds transfer, e-commerce (including electronic credit-card payments via web-sites), secure communications over wireless local area networks and so on are all dependent upon this concept and upon efficient and easy implementations. It has thus become an essential part of ‘modern life’.

The difficulties of decryption of modern ciphers enables individuals to retain their privacy, which has both positive and negative connotations, Honest and dishonest individuals can keep their communications private, so this is helpful in protecting individuals from unwarranted government intrusion and interference in their private lives, but also protects criminals from detection. Whether this will lead ultimately to anarchy or freedom remains to be seen.

References and Further Reading

1. S. Singh, ‘The Code Book’, Fourth Estate Ltd., London, 1999 (ISPB 1-85702-889-9)

2. M.E. Hellman, ‘The Mathematics of Public Key Cryptography’, Scientific American, August 1979, 241, 130-139

3. W. Diffie and M. Hellman, ‘New Directions in Cryptography’, IEEE Trans on Information Theory, IT-22, November 1976, 644-654

4. M.E. Hellman, ‘An overview of Public-key Cryptography’, IEEE Communications Magazine, May 2002, 42-29 (reprinted from IEEE Communications Magazine, 1978, vol 6, with an added introduction which makes no references to the GCHQ work)

Letter from the site owner giving permission to place IEEE milestone plaque on the property

PKC Milestone Support Letter

Proposal and Nomination

Milestone-Proposal:Invention of Public-key Cryptography

Map

Loading map...