history of non-secret encryption, The

ABSTRACT: Two of the most important techniques in public-key cryptography are the Diffie-Hellman key exchange protocol and the RSA encryption system. These were discovered in the academic community in 1976 and 1978 respectively. It was widely rumoured that these techniques were known by UK government cryptographers prior to these dates, although this was not officially confirmed until December 1997. In fact these techniques were first discovered in the early 1970s at the United Kingdom's Communication-Electronics Security Group (CESG), the United Kingdom communications security group. Official confirmation came with the release of a technical paper by detailing the history of the discoveries.

KEYWORDS: Public-key cryptography, Non-secret encryption, RSA, Diffie-Hellman.

NOTE FROM THE EDITOR

This paper was written by James Ellis in 1987. The preface was written by Cliff Cocks in January 1999 The copyright for the paper and preface remains with the Crown (Her Majesty's Government). This paper is available on the web site http://www.cesg .gov.uk. Other significant works for cryptology history which may be found there include:

"The Possibility of Non-Secret Encryption," J. H. Ellis (1970).

"A Note on Non-Secret Encryption," C. Cocks (1973).

"Non-Secret Encryption Using a Finite Field," M. Williamson (1974).

"Thoughts on Cheaper Non-Secret Encryption," M. Williamson (1976).

PREFACE

The following article was originally written by James Ellis for an internal (CESG) readership in the late 1980's. James was the central figure in the discovery of public key cryptography (then called non-secret encryption) in the 1970's, a number of years before the same ideas were rediscovered in the public domain.

James Ellis was a most original thinker who, when given a problem, would always challenge the fundamental assumptions. Nowadays public key cryptography is so well established that it is hard to realise how improbable the concept originally seemed. The idea that in order for two parties to communicate securely, they had to have previously established a shared secret had been regarded as obvious - right back to the Caesar cipher of the Roman Empire. James shattered this long held assumption in 1969 with the notion that the recipient could play a part in the encipherment process - a revolutionary idea. He then persevered, despite some initial wariness which followed his proof of concept, to work with others to try to find a realisation of his idea, and later continued to work on the practical issues of implementing a public key system. Although James' article stops at the time of the public discoveries by Diffie and Hellman, CESG's interest in the subject, and its involvement in public key research and development continue to the present day.

Sadly James died in December 1997, shortly before this contribution to cryptography was made public.

Cliff Cocks, January 1999

Public-key cryptography (PKC) has been the subject of much discussion in the open literature since Diffie and Hellman suggested the possibility in their paper of April 1976 [1]. It has captured public imagination, and has been analysed and developed for practical use. Over the past decade there has been considerable academic activity in this field with many different schemes being proposed and, sometimes, analysed.

Cryptography is a most unusual science. Most professional scientists aim to be the first to publish their work, because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography is realised by minimising the information available to potential adversaries. Thus professional cryptographers normally work in closed communities to provide sufficient professional interaction to ensure quality while maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests of historical accuracy after it has been demonstrated clearly that no further benefit can be obtained from continued secrecy.

In keeping with this tradition, it is now appropriate to tell the story of the invention and development within CESG of non-secret encryption (NSE), which was our original name for what is now called PKC. The task of writing this paper has devolved on me because NSE was my idea and I can therefore describe these early developments from personal experience. No techniques not already public knowledge, or specific applications of NSE will be mentioned. Neither shall I venture into evaluation. This is a simple, personal account of the salient features, with only the absolute minimum of mathematics.

** The story begins in the 1960's. The management of vast quantities of key material needed for secure communication was a headache for the armed forces. It was obvious to everyone, including me, that no secure communication was possible without secret key, some other secret knowledge, or at least some way in which the recipient was in a different position from an interceptor. After all, if they were in identical situations how could one possibly be able to receive what the other could not? Thus there was no incentive to look for something so clearly impossible.