New Directions in Cryptography

1 New Directions in CryptographyInvited PaperWhitfield Diffie and Martin E. HellmanAbstractTwo kinds of contemporary developments in cryp-communications over an insecure channel order to use cryptog-tography are examined. Widening applications of teleprocess-raphy to insure privacy, however, it currently necessary for theing have given rise to a need for new types of cryptographiccommunicating parties to share a key which is known to nosystems, which minimize the need for secure key distributionone else. This is done by sending the key in advance over somechannels and supply the equivalent of a written signature. Thissecure channel such a private courier or registered mail. Apaper suggests ways to solve these currently open conversation between two people with no prior acquain-It also discusses how the theories of communication and compu-tance is a common occurrence in business, however, and it istation are beginning to provide the tools to solve cryptographicunrealistic to expect initial business contacts to be postponedproblems of long enough for keys to be transmitted by some physical cost and delay imposed by this key distribution problemis a major barrier to the transfer of business communications1 INTRODUCTIONto large teleprocessing III proposes two approaches to transmitting keyingWe stand today on the brink of a revolution in over public ( , insecure)

2 Channel without compro-The development of cheap digital hardware has freed it frommising the security of the system. Inpublic key cryptosystemthe design limitations of mechanical computing and broughtenciphering and deciphering are governed by distinct keys,Ethe cost of high grade cryptographic devices down to whereandD,such that computingDfromEis computationally infeasi-they can be used in such commercial applications as remoteble ( , requiring 10100instructions). The enciphering keycash dispensers and computer terminals. In turn, such applica-Ecan thus be publicly disclosed without compromising thetions create a need for new types of cryptographic systemsdeciphering user of the network can, therefore,which minimize the necessity of secure key distribution chan-place his enciphering key in a public directory.

3 This enablesnels and supply the equivalent of a written signature. At theany user of the system to send a message to any other usersame time, theoretical developments in information theory andenciphered in such a way that only the intended receiver iscomputer science show promise of providing provably secureable to decipher it. As such, a public key cryptosystem iscryptosystems, changing this ancient art into a access cipher. A private conversation can therefore beThe development of computer controlled communication net-held between any two individuals regardless of whether theyworks promises effortless and inexpensive contact between peo-have ever communicated before. Each one sends messages tople or computers on opposite sides of the world, replacing mostthe other enciphered in the receiver public enciphering keymail and many excursions with telecommunications.

4 For manyand deciphers the messages he receives using his own secretapplications these contacts must be made secure against botheavesdropping and the injection of illegitimate messages. Atdeciphering , however, the solution of security problems lags wellWe propose some techniques for developing public key crypt-behind other areas of communications technology. Contempo-osystems, but the problem is still largely Cryptography is unable to meet the requirements, in thatPublic key distribution systemsoffer a different approach toits use would impose such severe inconveniences on the systemeliminating the need for a secure key distribution channel. Inusers, as to eliminate many of the benefits of a system, two users who wish to exchange a key communi-The best known cryptographic problem is that of privacy:cate back and forth until they arrive a key in common.

5 A thirdpreventing the unauthorized extraction of information fromparty eavesdropping on this exchange must find it computation-ally infeasible to compute the key from the information over-Manuscript received June 3, 1976. This work was partially supported byheard. A possible solution to the public key distribution problemthe National Science Foundation under NSF Grant ENG 10173. Portions ofis given in Section III, and Merkle [1] has a partial solution ofthis work were presented at the IEEE Information Theory Workshop, Lenox,a different , June 23 25, 1975 and the IEEE International Symposium on InformationTheory in Ronneby, Sweden, June 21 24, second problem, amenable to cryptographic solution whichW. Diffie is with the Department of Electrical Engineering, Stanford Univer-stands in the way of replacing contemporary business communi-sity, Stanford, CA, and the Stanford Artificial Intelligence Laboratory, Stanford,cations by teleprocessing systems is authentication.

6 In currentCA , the validity of contracts guaranteed by signatures. AM. E. Hellman is with the Department of Electrical Engineering, StanfordUniversity, Stanford, CA contract serves as gal evidence of an agreement which2930 DIFFIE AND HELLMANthe holder can present in court if necessary. The use of signa-the unauthorized injection of messages into a public channel,assuring the receiver of a message of the legitimacy of its , however, requires the transmission and storage of writtencontracts. In order to have a purely digital replacement for hisA channel is considered public if its security is inadequatefor the needs of its users. A channel such as a telephone linepaper instrument, each user must be able to produce messagewhose authenticity can be checked by anyone, but which couldmay therefore be considered private by some users and publicby others.

7 Any channel may be threatened with eavesdroppingnot have been produced by anyone else, even the only one person can originate messages but many peopleor injection or both, depending on its use. In telephone commu-nication, the threat of injection is paramount, since the calledcan receive messages, this can be viewed as a broadcast electronic authentication techniques cannot meet thisparty cannot determine which phone is calling. Eavesdropping,which requires the use of a wiretap, is technically more IV discusses the problem of providing a true, digtal,and legally hazardous. In radio, by comparison, the situationis reversed. Eavesdropping is passive and involves no legalmessage dependent signature. For reasons brought but there,we refer to this as the one-way authentication problem.

8 Somehazard, while injection exposes the illegitimate transmitter todiscovery and solutions are given, and it is shown how any public keycryptosystem can be transformed into a one-way authentica-Having divided our problems into those of privacy andauthentication we will sometimes further subdivide authentica-tion V will consider the interrelation of various crypto-tion into message authentication, which is the problem definedabove, and user authentication, in which the only task of thegraphic problems and introduce the even more difficult problemof trap is to verify that an individual is who he claims to example, the identity of an individual who presents a creditAt the same time that communications and computation havegiven rise to new cryptographic problems, their off-ring, infor-card must be verified, but there is no message which he wishesto transmit.

9 In spite of this apparent absence of a message inmation theory, and the theory of computation have begun tosupply tools for the solution of important problems in classi-user authentication, the two problems are largely user authentication, there is an implicit message. I AMThe search for unbreakable codes is one of the oldest themesUSER X, while message authentication is just verification ofof cryptographic research, but until this century proposed sys-the identity of the party sending the message. Differences intems have ultimately been broken. In the nineteen twenties,the threat environments and other aspects of these two subpro-however, the one time pad was inated, and shown to beblems, however, sometimes make it convenient to distinguishunbreakable [2, pp.]

10 398 400]. The theoretical basis underlyingbetween and related systems was on a firm foundation a quarterFigure 1 illustrates the flow of information in a conventionalcentury later by information theory [3]. One time pads requirecryptographic system used for privacy of long days and are therefore prohibitively expensiveThere are three parties: a transmitter, a receiver, and an eaves-in most The transmitter generates a plaintext or unencipheredIn contrast, the security of most cryptographic systemsmessagePto be communicated over an insecure channel tobesides in the computational difficulty to the cryptanalyst dis-the legitimate receiver. In order to prevent the eavesdroppercovering the plaintext without knowledge of the key.