New Directions in CryptographyInvited PaperWhitfield Diffie and Martin E. HellmanAbstract Two 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 problems.private conversation between two people with no prior acquain-It also discusses how the theories of communicationandcompu-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 standing.long enough for keys to be transmitted by some physical means.The cost and delay imposed by this key distribution problemis a major barrier to the transfer of business communications1 INTRODUCTIONto large teleprocessing networks.Section III proposes two approaches to transmitting keyingWe stand today on the brink of a revolution in cryptography.information overpublic(i.e., insecure) channel without compro-The development of cheap digital hardware has freed it frommising the security of the system. In public 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 whereand D, such that computing D from E is computationally infeasi-they can be used in such commercial applications as remoteble (e.g., requiring 10100instructions). The enciphering keycash dispensers and computer terminals. In turn, such applica-E can thus be publicly disclosed without compromising thetions create a need for new types of cryptographic systemsdeciphering key D. Each user of the network can, therefore,which minimize the necessity of secure key distribution chan-place his enciphering key in a public directory. 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 science.multiple 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. 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. At deciphering key.present, however, the solution of security problems lags wellWepropose some techniques for developing public key crypt-behind other areas of communications technology. Contempo-osystems, but the problem is still largely open.rary cryptography is unable to meet the requirements, in thatPublic key distribution systems offer 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 teleprocessing.such 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. 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 form.MA, June 23–25, 1975 and the IEEE International Symposium on InformationTheory in Ronneby, Sweden, June 21–24, 1976.A 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. In currentCA 94305.business, the validity of contracts guaranteed by signatures. AM. E. Hellman is with the Department of Electrical Engineering, StanfordUniversity, Stanford, CA 94305.signed contract serves as gal evidence of an agreement which2930DIFFIE 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 sender.tures, however, requires the transmission and storage of writtencontracts. In order to have a purely digital replacement for his A 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 could may therefore be considered private by some users and publicby others. Any channel may be threatened with eavesdroppingnot have been produced by anyone else, even the recipient.Since only one person can originate messages but many people or 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 cipher.Current electronic authentication techniques cannot meet this party cannot determine which phone is calling. Eavesdropping,which
View Full Document
Unlocking...