New Directions in Cryptography Invited Paper Whitfield Diffie and Martin E.Hellman Abstract 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 the ing have given rise to a need for new types of cryptographic communicating parties to share a key which is known to no systems,which minimize the need for secure key distribution one else.This is done by sending the key in advance over some channels and supply the equivalent of a written signature.This secure channel such a private courier or registered mail.A paper suggests ways to solve these currently open problems. private 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 is tation are beginning to provide the tools to solve cryptographic unrealistic to expect initial business contacts to be postponed problems of long standing. long enough for keys to be transmitted by some physical means. The cost and delay imposed by this key distribution problem is a major barrier to the transfer of business communications 1 INTRODUCTION to large teleprocessing networks. Section III proposes two approaches to transmitting keying We stand today on the brink of a revolution in cryptography. information over public(i.e.,insecure)channel without compro- The development of cheap digital hardware has freed it from mising the security of the system.In public key cryptosystem the design limitations of mechanical computing and brought enciphering and deciphering are governed by distinct keys,E the cost of high grade cryptographic devices down to where and D,such that computing D from E is computationally infeasi- they can be used in such commercial applications as remote cash dispensers and computer terminals.In turn,such applica- ble (e.g.,requiring 10100 instructions).The enciphering key tions create a need for new types of cryptographic systems E can thus be publicly disclosed without compromising the which minimize the necessity of secure key distribution chan- deciphering key D.Each user of the network can,therefore, nels and supply the equivalent of a written signature.At the place his enciphering key in a public directory.This enables same time,theoretical developments in information theory and any user of the system to send a message to any other user computer science show promise of providing provably secure enciphered in such a way that only the intended receiver is cryptosystems,changing this ancient art into a science. able to decipher it.As such,a public key cryptosystem is The development of computer controlled communication net- multiple access cipher.A private conversation can therefore be works promises effortless and inexpensive contact between peo- held between any two individuals regardless of whether they ple or computers on opposite sides of the world,replacing most have ever communicated before.Each one sends messages to mail and many excursions with telecommunications.For many the other enciphered in the receiver public enciphering key applications these contacts must be made secure against both and deciphers the messages he receives using his own secret eavesdropping and the injection of illegitimate messages.At deciphering key. present,however,the solution of security problems lags well We propose 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 that Public key distribution systems offer a different approach to its use would impose such severe inconveniences on the system eliminating the need for a secure key distribution channel.In users,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 third preventing the unauthorized extraction of information from party 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 by heard.A possible solution to the public key distribution problem the National Science Foundation under NSF Grant ENG 10173.Portions of this work were presented at the IEEE Information Theory Workshop,Lenox, is given in Section III,and Merkle [1]has a partial solution of MA,June 23-25,1975 and the IEEE International Symposium on Information a different form. Theory in Ronneby,Sweden,June 21-24,1976. A second problem,amenable to cryptographic solution which W.Diffie is with the Department of Electrical Engineering,Stanford Univer- stands in the way ofreplacing contemporary business communi- sity,Stanford,CA,and the Stanford Artificial Intelligence Laboratory,Stanford, CA94305. cations by teleprocessing systems is authentication.In current M.E.Hellman is with the Department of Electrical Engineering,Stanford business,the validity of contracts guaranteed by signatures.A University,Stanford,CA 94305. signed contract serves as gal evidence of an agreement which 29
New Directions in Cryptography Invited Paper Whitfield Diffie and Martin E. Hellman Abstract Two kinds of contemporary developments in cryp- communications over an insecure channel order to use cryptogtography are examined. Widening applications of teleprocess- raphy to insure privacy, however, it currently necessary for the ing have given rise to a need for new types of cryptographic communicating parties to share a key which is known to no systems, which minimize the need for secure key distribution one else. This is done by sending the key in advance over some channels and supply the equivalent of a written signature. This secure channel such a private courier or registered mail. A paper suggests ways to solve these currently open problems. private conversation between two people with no prior acquainIt also discusses how the theories of communication and compu- tance is a common occurrence in business, however, and it is tation are beginning to provide the tools to solve cryptographic unrealistic to expect initial business contacts to be postponed problems of long standing. long enough for keys to be transmitted by some physical means. The cost and delay imposed by this key distribution problem is a major barrier to the transfer of business communications 1 INTRODUCTION to large teleprocessing networks. Section III proposes two approaches to transmitting keying We stand today on the brink of a revolution in cryptography. information over public (i.e., insecure) channel without compro- The development of cheap digital hardware has freed it from mising the security of the system. In public key cryptosystem the design limitations of mechanical computing and brought enciphering and deciphering are governed by distinct keys, E the cost of high grade cryptographic devices down to where and D,such that computing D from E is computationally infeasi- they can be used in such commercial applications as remote ble (e.g., requiring 10100 instructions). The enciphering key cash dispensers and computer terminals. In turn, such applica- E can thus be publicly disclosed without compromising the tions create a need for new types of cryptographic systems deciphering 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 enables nels and supply the equivalent of a written signature. At the any user of the system to send a message to any other user same time, theoretical developments in information theory and enciphered in such a way that only the intended receiver is computer science show promise of providing provably secure able to decipher it. As such, a public key cryptosystem is cryptosystems, changing this ancient art into a science. The development of computer controlled communication net- multiple access cipher. A private conversation can therefore be works promises effortless and inexpensive contact between peo- held between any two individuals regardless of whether they ple or computers on opposite sides of the world, replacing most have ever communicated before. Each one sends messages to mail and many excursions with telecommunications. For many the other enciphered in the receiver public enciphering key applications these contacts must be made secure against both and deciphers the messages he receives using his own secret eavesdropping and the injection of illegitimate messages. At deciphering key. present, however, the solution of security problems lags well We propose some techniques for developing public key cryptbehind other areas of communications technology. Contempo- osystems, but the problem is still largely open. rary cryptography is unable to meet the requirements, in that Public key distribution systems offer a different approach to its use would impose such severe inconveniences on the system eliminating the need for a secure key distribution channel. In users, as to eliminate many of the benefits of teleprocessing. such a system, two users who wish to exchange a key communiThe best known cryptographic problem is that of privacy: cate back and forth until they arrive a key in common. A third preventing the unauthorized extraction of information from party eavesdropping on this exchange must find it computationally infeasible to compute the key from the information overManuscript received June 3, 1976. This work was partially supported by heard. A possible solution to the public key distribution problem the National Science Foundation under NSF Grant ENG 10173. Portions of is given in Section III, and Merkle [1] has a partial solution of this work were presented at the IEEE Information Theory Workshop, Lenox, MA, June 23–25, 1975 and the IEEE International Symposium on Information a different form. Theory in Ronneby, Sweden, June 21–24, 1976. A second problem, amenable to cryptographic solution which W. 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 current CA 94305. M. E. Hellman is with the Department of Electrical Engineering, Stanford business, the validity of contracts guaranteed by signatures. A University, Stanford, CA 94305. signed contract serves as gal evidence of an agreement which 29
30 DIFFIE AND HELLMAN the holder can present in court if necessary.The use of signa-the unauthorized injection of messages into a public channel, tures,however,requires the transmission and storage of written assuring the receiver of a message of the legitimacy of its sender. contracts.In order to have a purely digital replacement for his A channel is considered public if its security is inadequate paper instrument,each user must be able to produce message for the needs of its users.A channel such as a telephone line whose authenticity can be checked by anyone,but which could may therefore be considered private by some users and public not have been produced by anyone else,even the recipient.by others.Any channel may be threatened with eavesdropping Since only one person can originate messages but many people or injection or both,depending on its use.In telephone commu- can receive messages,this can be viewed as a broadcast cipher. nication,the threat of injection is paramount,since the called Current electronic authentication techniques cannot meet this party cannot determine which phone is calling.Eavesdropping, need. which requires the use of a wiretap,is technically more difficult Section IV discusses the problem of providing a true,digtal,and legally hazardous.In radio,by comparison,the situation message dependent signature.For reasons brought but there,is reversed.Eavesdropping is passive and involves no legal we refer to this as the one-way authentication problem.Some hazard,while injection exposes the illegitimate transmitter to partial solutions are given,and it is shown how any public key discovery and prosecution. cryptosystem can be transformed into a one-way authentica- Having divided our problems into those of privacy and tion system. authentication we will sometimes further subdivide authentica- Section V will consider the interrelation of various crypto-tion into message authentication,which is the problem defined graphic problems and introduce the even more difficult problem above,and user authentication,in which the only task of the of trap doors. system is to verify that an individual is who he claims to be. At the same time that communications and computation have For example,the identity of an individual who presents a credit given rise to new cryptographic problems,their off-ring,infor-card must be verified,but there is no message which he wishes mation theory,and the theory of computation have begun to to transmit.In spite of this apparent absence of a message in supply tools for the solution of important problems in classi- user authentication,the two problems are largely equivalent. cal cryptography. In user authentication,there is an implicit message."I AM The search for unbreakable codes is one of the oldest themes USER X,"while message authentication is just verification of of cryptographic research,but until this century proposed sys-the identity of the party sending the message.Differences in tems 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 be blems,however,sometimes make it convenient to distinguish unbreakable [2,pp.398-400].The theoretical basis underlying between them. this and related systems was on a firm foundation a quarter Figure 1 illustrates the flow of information in a conventional century later by information theory [3].One time pads require cryptographic system used for privacy of communications. extremely long days and are therefore prohibitively expensive There are three parties:a transmitter,a receiver,and an eaves- in most applications. dropper.The transmitter generates a plaintext or unenciphered In contrast,the security of most cryptographic systems message p to be communicated over an insecure channel to besides in the computational difficulty to the cryptanalyst dis-the legitimate receiver.In order to prevent the eavesdropper covering the plaintext without knowledge of the key.This prob- from learning P the transmitter perates on P with an invertible lem falls within the domains of computational complexity and transformation Sk to produce the ciphertext or cryptogram C analysis of algorithms,two recent disciples which study the =Sx(P).The key K is transmitted only to the legitimate receiver difficulty of solving computational problems.Using the results via a secure channel,indicated by a shielded path in Figure 1. of these theories,it may be possible to extend proofs of security Since the legitimate receiver knows K.he can decipher C by to more useful classes systems in the foreseeable future.Section operating with Sx-to obtain Sk(C)=Sk(SK(P))=P.the VI explores this possibility. original plaintext message.The secure channel cannot be used Before proceeding to newer developments,we introduce ter- to transmit P itself for reasons of capacity or delay.For example. minology and define threat environments in the next section. 2 CONVENTIONAL CRYPTOGRAPHY Cryptography is the study of"mathematical"systems involving two kinds of security problems:privacy and authentication.A privacy system prevents the extraction information by unautho- rized parties from messages transmitted over a public channel, thus assuring the sender of a message that it is being read only Figure 1:Flow of informatrion in conventional cryptographic by the intended recipient.An authentication system prevents system
30 DIFFIE AND HELLMAN the holder can present in court if necessary. The use of signa- the unauthorized injection of messages into a public channel, tures, however, requires the transmission and storage of written assuring the receiver of a message of the legitimacy of its sender. contracts. In order to have a purely digital replacement for his A channel is considered public if its security is inadequate paper instrument, each user must be able to produce message for the needs of its users. A channel such as a telephone line whose authenticity can be checked by anyone, but which could may therefore be considered private by some users and public not have been produced by anyone else, even the recipient. by others. Any channel may be threatened with eavesdropping Since only one person can originate messages but many people or injection or both, depending on its use. In telephone commucan receive messages, this can be viewed as a broadcast cipher. nication, the threat of injection is paramount, since the called Current electronic authentication techniques cannot meet this party cannot determine which phone is calling. Eavesdropping, need. which requires the use of a wiretap, is technically more difficult Section IV discusses the problem of providing a true, digtal, and legally hazardous. In radio, by comparison, the situation message dependent signature. For reasons brought but there, is reversed. Eavesdropping is passive and involves no legal we refer to this as the one-way authentication problem. Some hazard, while injection exposes the illegitimate transmitter to partial solutions are given, and it is shown how any public key discovery and prosecution. cryptosystem can be transformed into a one-way authentica- Having divided our problems into those of privacy and tion system. authentication we will sometimes further subdivide authenticaSection V will consider the interrelation of various crypto- tion into message authentication, which is the problem defined graphic problems and introduce the even more difficult problem above, and user authentication, in which the only task of the of trap doors. system is to verify that an individual is who he claims to be. At the same time that communications and computation have For example, the identity of an individual who presents a credit given rise to new cryptographic problems, their off-ring, infor- card must be verified, but there is no message which he wishes mation theory, and the theory of computation have begun to to transmit. In spite of this apparent absence of a message in supply tools for the solution of important problems in classi- user authentication, the two problems are largely equivalent. cal cryptography. In user authentication, there is an implicit message. “I AM The search for unbreakable codes is one of the oldest themes USER X,” while message authentication is just verification of of cryptographic research, but until this century proposed sys- the identity of the party sending the message. Differences in tems have ultimately been broken. In the nineteen twenties, the threat environments and other aspects of these two subprohowever, the “one time pad” was inated, and shown to be blems, however, sometimes make it convenient to distinguish unbreakable [2, pp. 398–400]. The theoretical basis underlying between them. this and related systems was on a firm foundation a quarter Figure 1 illustrates the flow of information in a conventional century later by information theory [3]. One time pads require cryptographic system used for privacy of communications. extremely long days and are therefore prohibitively expensive There are three parties: a transmitter, a receiver, and an eavesin most applications. dropper. The transmitter generates a plaintext or unenciphered In contrast, the security of most cryptographic systems message P to be communicated over an insecure channel to besides in the computational difficulty to the cryptanalyst dis- the legitimate receiver. In order to prevent the eavesdropper covering the plaintext without knowledge of the key. This prob- from learning P, the transmitter perates on P with an invertible lem falls within the domains of computational complexity and transformation SK to produce the ciphertext or cryptogram C analysis of algorithms, two recent disciples which study the 5 SK(P). The key K is transmitted only to the legitimate receiver difficulty of solving computational problems. Using the results via a secure channel, indicated by a shielded path in Figure 1. of these theories, it may be possible to extend proofs of security Since the legitimate receiver knows K, he can decipher C by to more useful classes systems in the foreseeable future. Section operating with SK 21 to obtain SK 21 (C) 5 SK 21 (SK(P)) 5 P, the VI explores this possibility. original plaintext message. The secure channel cannot be used Before proceeding to newer developments, we introduce ter- to transmit P itself for reasons of capacity or delay. For example, minology and define threat environments in the next section. 2 CONVENTIONAL CRYPTOGRAPHY Cryptography is the study of “mathematical” systems involving two kinds of security problems: privacy and authentication. A privacy system prevents the extraction information by unauthorized parties from messages transmitted over a public channel, thus assuring the sender of a message that it is being read only Figure 1: Flow of informatrion in conventional cryptographic by the intended recipient. An authentication system prevents system
NEW DIRECTIONS IN CRYPTOGRAPHY 31 the secure channel might be a weekly courier and the insecure added modulo 2 to the bits of the plaintext.Block ciphers act channel a telephone line. in a purely combinatorial fashion on large blocks of text,in A cryptographic system is a single parameter family such a way that a small change in the input block produces a (Sk);ZkEKz)of invertible transformations major change in the resulting output.This paper deals primarily with block ciphers,because this error propagation property is Sx:{P}→{C} (1) valuable in many authentication applications. In an authentication system,cryptography is used to guaran- from a space p)of plaintext messages to a space C of tee the authenticity of the message to the receiver.Not only ciphertext messages.The parameter K is called the key and is must a meddler be prevented from injecting totally new,authen- selected from a finite set (K)called the keyspace.Ifthe message tic looking messages into a channel,but he must be prevented spaces(P)and (C)are equal,we will denote them both by (M).from creating apparently authentic messages by combining,or When discussing individual cryptographic transformations Sk,merely repeating,old messages which he has copied in the we will sometimes omit mention of the system and merely past.A cryptographic system intended to guarantee privacy refer to the transformation K. will not,in general,prevent this latter form of mischief. The goal in designing the cryptosystem {Sk)is to make To guarantee the authenticity of a message,information is the enciphering and deciphering operations inexpensive,but to added which is a function not only of the message and a secret ensure that any successful cryptanalytic operation is too com-key,but of the date and time as well,for example,by attaching plex to be economical.There are two approaches to this prob-the date and time to each message and encrypting the entire lem.A system which is secure due to the computational cost sequence.This assures that only someone who possesses the of cryptanalysis,but which would succumb to an attack with key can generate a message which,when decrypted,will contain unlimited computation,is called computationally secure:while the proper date and time.Care must be taken,however,to use a system which can resist any cryptanalytic attack,no matter a system in which small changes in the ciphertext result in how much computation is allowed,is called unconditionally large changes in the deciphered plaintext.This intentional error secure.Unconditionally secure systems are discussed in [3]and propagation ensures that if the deliberate injection of noise on 4]and belong to that portion of information theory,called the the channel changes a message such as "erase file 7"into a Shannon theory.which is concerned with optimal performance different message such as "erase file 8,"it will also corrupt the obtainable with unlimited computation. authentication information.The message will then be rejected Unconditional security results from the existence of multiple as inauthentic. meaningful solutions to a cryptogram.For example,the simple The first step in assessing the adequacy of cryptographic substitution cryptogram XMD resulting from English text can systems is to classify the threats to which they are to be sub- represent the plaintext messages:now,and,the,etc.A computa-jected.The following threats may occur to cryptographic sys- tionally secure cryptogram,in contrast,contains sufficient tems employed for either privacy or authentication. information to uniquely determine the plaintext and the key. A ciphertext only attack is a cryptanalytic attack in which Its security resides solely in the cost of computing them. the cryptanalyst possesses only ciphertext. The only unconditionally secure system in common use is A known plaintext attack is a cryptanalytic attack in which the the one time pad,in which the plaintext is combined with a cryptanalyst possesses a substantial quantity of corresponding randomly chosen key of the same length.While such a system plaintext and ciphertext. is provably secure,the large amount of key required makes it A chosen plaintext attack is a cryptanalytic attack in which impractical for most applications.Except as otherwise noted, the cryptanalyst can submit an unlimited number of plaintext this paper deals with computationally secure systems since messages of his own choosing and examine the resulting these are more generally applicable.When we talk about the cryptograms. need to develop provably secure cryptosystems we exclude In all cases it is assumed that the opponent knows the general those,such as the one time pad,which are unwieldly to use. system {Sk)in use since this information can be obtained by Rather,we have in mind systems using only a few hundred studying a cryptographic device.While many users of cryptog- bits of key and implementable in either a small amount of raphy attempt to keep their equipment secret,many commercial digital hardware or a few hundred lines of software. applications require not only that the general system be public We will call a task computationally infeasible if its cost as but that it be standard. measured by either the amount of memory used or the runtime A ciphertext only attack occurs frequently in practice.The is finite but impossibly large. cryptanalyst uses only knowledge of the statistical properties Much as error correcting codes are divided into convolutional of the language in use (e.g.,in English,the letter e occurs 13 and block codes,cryptographic systems can be divided into percent of the time)and knowledge of certain"probable"words two broad classes:stream ciphers and block ciphers.Stream (e.g.,a letter probably begins "Dear Sir:").It is the weakest ciphers process the plaintext in small chunks(bits or characters),threat to which a system can be subjected,and any system usually producing a pseudorandom sequence of bits which is which succumbs to it is considered totally insecure
NEW DIRECTIONS IN CRYPTOGRAPHY 31 the secure channel might be a weekly courier and the insecure added modulo 2 to the bits of the plaintext. Block ciphers act channel a telephone line. in a purely combinatorial fashion on large blocks of text, in A cryptographic system is a single parameter family such a way that a small change in the input block produces a {SK};zKP{K;z} of invertible transformations major change in the resulting output. This paper deals primarily with block ciphers, because this error propagation property is SK:{P} → {C} (1) valuable in many authentication applications. In an authentication system, cryptography is used to guaranfrom a space {P} of plaintext messages to a space {C} of tee the authenticity of the message to the receiver. Not only ciphertext messages. The parameter K is called the key and is must a meddler be prevented from injecting totally new, authenselected from a finite set {K} called the keyspace. If the message tic looking messages into a channel, but he must be prevented spaces {P} and {C} are equal, we will denote them both by {M}. from creating apparently authentic messages by combining, or When discussing individual cryptographic transformations SK, merely repeating, old messages which he has copied in the we will sometimes omit mention of the system and merely past. A cryptographic system intended to guarantee privacy refer to the transformation K. will not, in general, prevent this latter form of mischief. The goal in designing the cryptosystem {SK} is to make To guarantee the authenticity of a message, information is the enciphering and deciphering operations inexpensive, but to added which is a function not only of the message and a secret ensure that any successful cryptanalytic operation is too com- key, but of the date and time as well, for example, by attaching plex to be economical. There are two approaches to this prob- the date and time to each message and encrypting the entire lem. A system which is secure due to the computational cost sequence. This assures that only someone who possesses the of cryptanalysis, but which would succumb to an attack with key can generate a message which, when decrypted, will contain unlimited computation, is called computationally secure; while the proper date and time. Care must be taken, however, to use a system which can resist any cryptanalytic attack, no matter a system in which small changes in the ciphertext result in how much computation is allowed, is called unconditionally large changes in the deciphered plaintext. This intentional error secure. Unconditionally secure systems are discussed in [3] and propagation ensures that if the deliberate injection of noise on [4] and belong to that portion of information theory, called the the channel changes a message such as “erase file 7” into a Shannon theory, which is concerned with optimal performance different message such as “erase file 8,” it will also corrupt the obtainable with unlimited computation. authentication information. The message will then be rejected Unconditional security results from the existence of multiple as inauthentic. meaningful solutions to a cryptogram. For example, the simple The first step in assessing the adequacy of cryptographic substitution cryptogram XMD resulting from English text can systems is to classify the threats to which they are to be subrepresent the plaintext messages: now, and, the, etc. A computa- jected. The following threats may occur to cryptographic systionally secure cryptogram, in contrast, contains sufficient tems employed for either privacy or authentication. information to uniquely determine the plaintext and the key. A ciphertext only attack is a cryptanalytic attack in which Its security resides solely in the cost of computing them. the cryptanalyst possesses only ciphertext. The only unconditionally secure system in common use is A known plaintext attack is a cryptanalytic attack in which the the one time pad, in which the plaintext is combined with a cryptanalyst possesses a substantial quantity of corresponding randomly chosen key of the same length. While such a system plaintext and ciphertext. is provably secure, the large amount of key required makes it A chosen plaintext attack is a cryptanalytic attack in which impractical for most applications. Except as otherwise noted, the cryptanalyst can submit an unlimited number of plaintext this paper deals with computationally secure systems since messages of his own choosing and examine the resulting these are more generally applicable. When we talk about the cryptograms. need to develop provably secure cryptosystems we exclude In all cases it is assumed that the opponent knows the general those, such as the one time pad, which are unwieldly to use. system {SK} in use since this information can be obtained by Rather, we have in mind systems using only a few hundred studying a cryptographic device. While many users of cryptogbits of key and implementable in either a small amount of raphy attempt to keep their equipment secret, many commercial digital hardware or a few hundred lines of software. applications require not only that the general system be public We will call a task computationally infeasible if its cost as but that it be standard. measured by either the amount of memory used or the runtime A ciphertext only attack occurs frequently in practice. The is finite but impossibly large. cryptanalyst uses only knowledge of the statistical properties Much as error correcting codes are divided into convolutional of the language in use (e.g., in English, the letter e occurs 13 and block codes, cryptographic systems can be divided into percent of the time) and knowledge of certain “probable” words two broad classes: stream ciphers and block ciphers. Stream (e.g., a letter probably begins “Dear Sir:”). It is the weakest ciphers process the plaintext in small chunks (bits or characters), threat to which a system can be subjected, and any system usually producing a pseudorandom sequence of bits which is which succumbs to it is considered totally insecure
32 DIFFIE AND HELLMAN The system which is secure against a known plaintext attends also protect against the threat of dispute.That is,a message frees its users from the need to keep their past messages secret, may be sent but later repudiated by either the transmitter or or to paraphrase them prior to classification.This is an unreason- the receiver.Or,it may be alleged by either party that a message able burden to place on the systems users,particularly in com- was sent when in fact none was.Unforgeable digital signatures mercial situations where luct announcements or press releases and receipts are needed.For example,a dishonest stockbroker may be sent in typted form for later public disclosure.Similar might try to cover up unauthorized buying and selling for situations in diplomatic correspondence have led to the cracking personal gain by forging orders from clients,or a client might many supposedly secure systems.While a known text attack disclaim an order actually authorized by him but which he later is not always possible,its occurrence is uent enough that a sees will cause a loss.We will introduce concepts which allow system which cannot resist it is not considered secure the receiver to verify the authenticity of a message,but prevent The chosen plaintext attack is difficult to achieve in justice, him from generating apparently authentic messages,thereby but can be approximated.For example,submitted to a proposal protecting against both the threat of compromise of the receiv- to a competitor may result in his enciphering it for transmission er's authentication data and the threat of dispute to his headquarters.A cipher which is secure against a chosen plaintext attack thus frees users from concern over whether their opponents can t messages in their system. 3 PUBLIC KEY CRYPTOGRAPHY For the purpose of certifying systems as secure,it is appro- priate to consider the more formidable cryptanalytic as these As shown in Figure 1,cryptography has been a derivative not only give more realistic models of the caring environment security measure.Once a secure channel exists along which of a cryptographic system,but make assessment of the system's keys can be transmitted,the security can be extended to other strength easier.Many systems which are difficult to analyze channels of higher bandwidth or smaller delay by encrypting using a ciphertext only check can be ruled out immediately the messages sent on them.The effect has been to limit the under known plaining or chosen plaintext attacks. use of cryptography to communications among people who It is clear from these definitions,cryptanalysis is a identifica- have made prior preparation for cryptographic security. tion problem.The known plaintext and even plaintext attacks In order to develop large,secure,telecommunications sys- correspond to passive and active identification problems, tems,this must be changed.A large number of users n results respectively.Unlike many effects in which system identification in an even larger number,(n2-n)/2 potential pairs who may is considered,such automatic fault diagnosis,the goal in cryp- wish to communicate privately from all others.It is unrealistic tography is build systems which are difficult,rather than easy, to assume either that a pair of users with no prior acquaintance to identify. will be able to wait for a key to be sent by some secure physical The chosen plaintext attack is often called an IFF attack means,or that keys for all (n-n)/2 pairs can be arranged in terminology which descends from its origin in the development advance.In another paper [5],the authors have considered a of cryptographic"identification friend or systems after World conservative approach requiring no new development in cryp- War II.An IFF system enables ary radars to distinguish between tography itself,but this involves diminished security,inconve- friendly and enemy es automatically.The radar sends a time- nience,and restriction of the network to a starlike configuration varying enge to the airplane which receives the challenge,pts with respect to initial connection protocol. it under the appropriate key,and sends it back to radar.By We propose that it is possible to develop systems of the type comparing this response with a correctly pted version of the shown in Figure 2,in which two parties communicating solely challenge,the radar can recognize kindly aircraft.While the over a public channel and using only publicly known techniques aircraft are over enemy territory,enemy cryptanalysts can send can create a secure connection.We examine two approaches challenges and expect the encrypted responses in an attempt to this problem,called public key cryptosystems and public key to determine authentication key in use,thus mounting a chosen distribution systems,respectively.The first are more powerful, text attack on the system.In practice,this threat is entered lending themselves to the solution of the authentication prob- by restricting the form of the challenges,which are not be lems treated in the next section.while the second are much unpredictable,but only nonrepeating. closer to realization. There are other threats to authentication systems which can- not be treated by conventional cryptography,and with require recourse to the new ideas and techniques reduced in this paper. The threat of compromise of the ver's authentication data is motivated by the situation multiuser networks where the receiver is often the system itself.The receiver's password tables and other authentication data are then more vulnerable to theft than those of the transmitter(an individual user).As shown later,some techniques for protecting against this threat Figure 2:Flow of information in public key system
32 DIFFIE AND HELLMAN The system which is secure against a known plaintext attends also protect against the threat of dispute. That is, a message frees its users from the need to keep their past messages secret, may be sent but later repudiated by either the transmitter or or to paraphrase them prior to classification. This is an unreason- the receiver. Or, it may be alleged by either party that a message able burden to place on the systems users, particularly in com- was sent when in fact none was. Unforgeable digital signatures mercial situations where luct announcements or press releases and receipts are needed. For example, a dishonest stockbroker may be sent in typted form for later public disclosure. Similar might try to cover up unauthorized buying and selling for situations in diplomatic correspondence have led to the cracking personal gain by forging orders from clients, or a client might many supposedly secure systems. While a known text attack disclaim an order actually authorized by him but which he later is not always possible, its occurrence is uent enough that a sees will cause a loss. We will introduce concepts which allow system which cannot resist it is not considered secure. the receiver to verify the authenticity of a message, but prevent The chosen plaintext attack is difficult to achieve in justice, him from generating apparently authentic messages, thereby but can be approximated. For example, submitted to a proposal protecting against both the threat of compromise of the receivto a competitor may result in his enciphering it for transmission er’s authentication data and the threat of dispute. to his headquarters. A cipher which is secure against a chosen plaintext attack thus frees users from concern over whether their opponents can t messages in their system. 3 PUBLIC KEY CRYPTOGRAPHY For the purpose of certifying systems as secure, it is appro- As shown in Figure 1, cryptography has been a derivative priate to consider the more formidable cryptanalytic as these security measure. Once a secure channel exists along which not only give more realistic models of the caring environment keys can be transmitted, the security can be extended to other of a cryptographic system, but make assessment of the system’s channels of higher bandwidth or smaller delay by encrypting strength easier. Many systems which are difficult to analyze the messages sent on them. The effect has been to limit the using a ciphertext only check can be ruled out immediately use of cryptography to communications among people who under known plaining or chosen plaintext attacks. have made prior preparation for cryptographic security. It is clear from these definitions, cryptanalysis is a identifica- In order to develop large, secure, telecommunications sys- tion problem. The known plaintext and even plaintext attacks tems, this must be changed. A large number of users n results correspond to passive and active identification problems, in an even larger number, (n2 2 n)/2 potential pairs who may respectively. Unlike many effects in which system identification wish to communicate privately from all others. It is unrealistic is considered, such automatic fault diagnosis, the goal in cryp- to assume either that a pair of users with no prior acquaintance tography is build systems which are difficult, rather than easy, will be able to wait for a key to be sent by some secure physical to identify. means, or that keys for all (n The chosen plaintext attack is often called an IFF attack 2 2 n)/2 pairs can be arranged in advance. In another paper [5], the authors have considered a terminology which descends from its origin in the development conservative approach requiring no new development in cryp- of cryptographic “identification friend or systems after World War II. An IFF system enables ary radars to distinguish between tography itself, but this involves diminished security, inconvenience, and restriction of the network to a starlike configuration friendly and enemy es automatically. The radar sends a time- with respect to initial connection protocol. varying enge to the airplane which receives the challenge, pts We propose that it is possible to develop systems of the type it under the appropriate key, and sends it back to radar. By shown in Figure 2, in which two parties communicating solely comparing this response with a correctly pted version of the over a public channel and using only publicly known techniques challenge, the radar can recognize kindly aircraft. While the can create a secure connection. We examine two approaches aircraft are over enemy territory, enemy cryptanalysts can send to this problem, called public key cryptosystems and public key challenges and expect the encrypted responses in an attempt distribution systems, respectively. The first are more powerful, to determine authentication key in use, thus mounting a chosen lending themselves to the solution of the authentication prob- text attack on the system. In practice, this threat is entered lems treated in the next section, while the second are much by restricting the form of the challenges, which are not be closer to realization. unpredictable, but only nonrepeating. There are other threats to authentication systems which cannot be treated by conventional cryptography, and with require recourse to the new ideas and techniques reduced in this paper. The threat of compromise of the ver’s authentication data is motivated by the situation multiuser networks where the receiver is often the system itself. The receiver’s password tables and other authentication data are then more vulnerable to theft than those of the transmitter (an individual user). As shown later, some techniques for protecting against this threat Figure 2: Flow of information in public key system
NEW DIRECTIONS IN CRYPTOGRAPHY 33 A public key cryptosystem is a pair of families (EkKEK)involves a matrix in version which is a harder problem.And and (Dx'kek of algorithms representing invertible it is at least conceptually simpler to obtain an arbitrary pair of transformations. inverse matrices than it is to invert a given matrix.Start with the identity matrix and do elementary row and column opera- Es:{M→{G (2)tions to obtain an arbitrary invertible matrix E.Then starting with do the inverses of these same elementary operations in reverse order to obtain D=E-1.The sequence of elementary Dk:{M0→{M0 (3) operations could be easily determined from a random bit string. Unfortunately,matrix inversion takes only about n opera- on a finite message space {M,such that tions.The ratio of"cryptanalytic"time(i.e.,computing D from E)to enciphering or deciphering time is thus at most n.and 1)for every K (K),Ek is the inverse of DK, 2)for every K {K)and M (M,the algorithms Ex and enormous block sizes would be required to obtain ratios of 106 Dk are easy to compute, or greater.Also,it does not appear that knowledge of the 3)for almost every K (K),each easily computed algo- elementary operations used to obtain E from I greatly reduces the time for computing D.And,since there is no round-off rithm equivalent to D&is computationally infeasible to derive from Ek, error in binary arithmetic,numerical stability is unimportant in 4)for every K (K),it is feasible to compute inverse pairs the matrix inversion.In spite of its lack of practical utility,this Ex and Dk from K. matrix example is still useful for clarifying the relationships necessary in a public key cryptosystem. Because of the third property,a user's enciphering key Ek can A more practical approach to finding a pair of easily com- be made public without compromising the security of his secret puted inverse algorithms E and D:such that D is hard to infer deciphering key D&.The cryptographic system is therefore split from E,makes use of the difficulty of analyzing programs in into two parts,a family of enciphering transformations and a low level languages.Anyone who has tried to determine what family of deciphering transformations in such a way that,given operation is accomplished by someone else's machine language a member ofone family,it is infeasible to find the corresponding program knows that E itself(i.e.,what E does)can be hard to member of the other. infer from an algorithm for E.If the program were to be made The fourth property guarantees that there is a feasible way purposefully confusing through addition of unneeded variables of computing corresponding pairs of inverse transformations and statements,then determining an inverse algorithm could be when no constraint is placed on what either the enciphering or made very difficult.Ofcourse,Emust be complicated enough to deciphering transformation is to be.In practice,the cryptoequip-prevent its identification from input-output pairs. ment must contain a true random number generator (e.g.,a Essentially what is required is a one-way compiler:one which noisy diode)for generating K,together with an algorithm for takes an easily understood program written in a high level generating the Ex-D&pair from its outputs. language and translates it into an incomprehensible program Given a system of this kind,the problem of key distribution in some machine language.The compiler is one-way because is vastly simplified.Each user generates a pair of inverse trans-it must be feasible to do the compilation,but infeasible to formations,E and D,at his terminal.The deciphering transfor- reverse the process.Since efficiency in size of program and mation D must be kept secret,but need never be communicated run time are not crucial in this application,such as compilers on any channel.The enciphering key E can be made public by may be possible if the structure of the machine language can placing it in a public directory along with the user's name and be optimized to assist in the confusion. address.Anyone can then encrypt messages and send them to Merkle [1]has independently studied the problem of distrib- the user,but no one else can decipher messages intended for uting keys over an insecure channel.His approach is different him.Public key cryptosystems can thus be regarded as multiple from that of the public key cryptosystems suggested above, access ciphers. and will be termed a public key distribution system.The goal It is crucial that the public file of enciphering keys be pro- is for two users,4 and B,to securely exchange a key over an tected from unauthorized modification.This task is made easier insecure channel.This key is then used by both users in a by the public nature of the file.Read protection is unnecessary normal cryptosystem for both enciphering and deciphering. and,since the file is modified infrequently,elaborate write Merkle has a solution whose cryptanalytic cost grows as n2 protection mechanisms can be economically employed. where n is the cost to the legitimate users.Unfortunately the A suggestive,although unfortunately useless,example of a cost to the legitimate users of the system is as much in transmis- public key cryptosystem is to encipher the plaintext,represented sion time as in computation,because Merkle's protocol requires as a binary n-vector m.by multiplying it by an invertible binary n potential keys to be transmitted before one key can be decided n X n matrix E.The cryptogram thus equals Em.Letting D= on.Merkle notes that this high transmission overhead prevents E-we have m=Dc.Thus,both enciphering and deciphering the system from being very useful in practice.If a one megabit require about n operations.Calculation of D from E,however,limit is placed on the setup protocol's overhead,his technique
NEW DIRECTIONS IN CRYPTOGRAPHY 33 A public key cryptosystem is a pair of families {EK}KP{K} involves a matrix in version which is a harder problem. And and {DK}KP it is at least conceptually simpler to obtain an arbitrary pair of {K} of algorithms representing invertible transformations, inverse matrices than it is to invert a given matrix. Start with the identity matrix I and do elementary row and column operaEK:{M} → {M} (2) tions to obtain an arbitrary invertible matrix E. Then starting with I do the inverses of these same elementary operations in reverse order to obtain D 5 E21. The sequence of elementary DK:{M} → {M} (3) operations could be easily determined from a random bit string. Unfortunately, matrix inversion takes only about n3 operaon a finite message space {M}, such that tions. The ratio of “cryptanalytic” time (i.e., computing D from E) to enciphering or deciphering time is thus at most n, and 1) for every K P {K}, EK is the inverse of DK, enormous block sizes would be required to obtain ratios of 106 2) for every K P {K} and M P {M}, the algorithms EK and or greater. Also, it does not appear that knowledge of the DK are easy to compute, elementary operations used to obtain E from I greatly reduces 3) for almost every K P {K}, each easily computed algo- the time for computing D. And, since there is no round-off rithm equivalent to DK is computationally infeasible to error in binary arithmetic, numerical stability is unimportant in derive from EK, the matrix inversion. In spite of its lack of practical utility, this 4) for every K P {K}, it is feasible to compute inverse pairs matrix example is still useful for clarifying the relationships EK and DK from K. necessary in a public key cryptosystem. Because of the third property, a user’s enciphering key EK can A more practical approach to finding a pair of easily combe made public without compromising the security of his secret puted inverse algorithms E and D; such that D is hard to infer deciphering key DK. The cryptographic system is therefore split from E, makes use of the difficulty of analyzing programs in into two parts, a family of enciphering transformations and a low level languages. Anyone who has tried to determine what family of deciphering transformations in such a way that, given operation is accomplished by someone else’s machine language a member of one family, it is infeasible to find the corresponding program knows that E itself (i.e., what E does) can be hard to member of the other. infer from an algorithm for E. If the program were to be made The fourth property guarantees that there is a feasible way purposefully confusing through addition of unneeded variables of computing corresponding pairs of inverse transformations and statements, then determining an inverse algorithm could be when no constraint is placed on what either the enciphering or made very difficult. Of course, E must be complicated enough to deciphering transformation is to be. In practice, the cryptoequip- prevent its identification from input—output pairs. ment must contain a true random number generator (e.g., a Essentially what is required is a one-way compiler: one which noisy diode) for generating K, together with an algorithm for takes an easily understood program written in a high level generating the EK 2 DK pair from its outputs. language and translates it into an incomprehensible program Given a system of this kind, the problem of key distribution in some machine language. The compiler is one-way because is vastly simplified. Each user generates a pair of inverse trans- it must be feasible to do the compilation, but infeasible to formations, E and D, at his terminal. The deciphering transfor- reverse the process. Since efficiency in size of program and mation D must be kept secret, but need never be communicated run time are not crucial in this application, such as compilers on any channel. The enciphering key E can be made public by may be possible if the structure of the machine language can placing it in a public directory along with the user’s name and be optimized to assist in the confusion. address. Anyone can then encrypt messages and send them to Merkle [1] has independently studied the problem of distribthe user, but no one else can decipher messages intended for uting keys over an insecure channel. His approach is different him. Public key cryptosystems can thus be regarded as multiple from that of the public key cryptosystems suggested above, access ciphers. and will be termed a public key distribution system. The goal It is crucial that the public file of enciphering keys be pro- is for two users, A and B, to securely exchange a key over an tected from unauthorized modification. This task is made easier insecure channel. This key is then used by both users in a by the public nature of the file. Read protection is unnecessary normal cryptosystem for both enciphering and deciphering. and, since the file is modified infrequently, elaborate write Merkle has a solution whose cryptanalytic cost grows as n2 protection mechanisms can be economically employed. where n is the cost to the legitimate users. Unfortunately the A suggestive, although unfortunately useless, example of a cost to the legitimate users of the system is as much in transmispublic key cryptosystem is to encipher the plaintext, represented sion time as in computation, because Merkle’s protocol requires as a binary n-vector m, by multiplying it by an invertible binary n potential keys to be transmitted before one key can be decided n 3 n matrix E. The cryptogram thus equals Em. Letting D 5 on. Merkle notes that this high transmission overhead prevents E21 we have m 5 Dc. Thus, both enciphering and deciphering the system from being very useful in practice. If a one megabit require about n limit is placed on the setup protocol’s overhead, his technique 2 operations. Calculation of D from E, however
34 DIFFIE AND HELLMAN can achieve cost ratios approximately 10 000 to 1,which are as their key.User i obtains Ky by obtaining Y,from the public too small for most applications.If inexpensive,high bandwidth file and letting data links come available,ratios of a million to one or greater could achieved and the system would be of substantial practi- Ky=Y mod g (9) cal value. We now suggest a new public key distribution system which has several advantages.First,it requires only one "key"to =(a)mod g (10) be exchanged.Second,the cryptanalytic effort bears to grow exponentially in the effort of the legitimate users.And,third, its use can be tied to a public file of user information which (11) serves to authenticate user 4 to user B vice versa.By making the =o=mod q. public file essentially a read memory,one personal appearance allows a user to authenticate his identity many times to many User j obtains Ki in the similar fashion users.rkle's technique requires 4 and B to verify each other's activities through other means. Kg=乎modq. (12) The new technique makes use of the apparent difficulty computing logarithms over a finite field GF(g)with a one Another user must compute Ky from Y and Y,for example, number g of elements.Let by computing Y=a mod g, for1≤X≤g-1, (4) Ku=YdogeY))mod g. (13) Here a is a fixed primitive element of GF(g),then X is arranged We thus see that if logs mod g are easily computed the system to as the logarithm of y to the base o,mod g: can be broken.While we do not currently have a proof of the converse (i.e.,that the system is secure if logs mod g are X=loga Y mod g,for1≤Y≤q-1. (5) difficult to compute),neither do we see any way to compute Ky from Y,and Y without first obtaining either X,or X. Calculation of y from X is easy,taking at most 2 X log2 g If g is a prime slightly less than 25,then all quantities are multiplications [6,pp.398-422].For example,for X= representable as b bit numbers.Exponentiation then takes at most 2b multiplications mod g,while by hypothesis taking logs Y=a18=((a2)222×a2. (6) requires=operations.The cryptanalytic effort therefore grows exponentially relative to legitimate efforts.If b=200, Computing X from Y,on the other hand can be much more cult then at most 400 multiplications are required to compute Y and,for certain carefully chosen values of g.requires on the from Xi,or Ky from Y,and X,yet taking logs mod q requires order of operations,using the best known ithm 7,pp.9,2100 or approximately 103 operations. 575-576],[81. The security ofour technique depends crucially on the seculty of computing logarithms mod g.and if an algorithm whose 4 ONE-WAY AUTHENTICATION complexity grew as logag were to be found,our m would be broken.While the simplicity of the problem statement might The problem of authentication is perhaps an even more serious allow such simple algorithms,right instead allow a proof of barrier to the universal adoption of telecommunications for the problem's difficulty.How we assume that the best known business transactions than the problem of key distribution. algorithm for uting logs mod g is in fact close to optimal and Authentication is at the heart of any system involving contracts hence g is a good measure of the problem's complexity,and billing.Without it,business cannot function.Current elec- properly chosen g. tronic authentication systems cannot meet the need for a purely Such user generates an independent random number chosen digital,unforgeable,message dependent signature.They pro- uniformly from the set of integers (1,2,...,q-such keeps vide protection against third party forgeries,but do not protect X,secret,but places against disputes between transmitter and receiver. In order to develop a system capable of replacing the current Y=a mod q (7) written contract with some purely electronic form of communi- cation,we must discover a digital phenomenon with the same Public file with his name and address.When users i wish to properties as a written signature.It must be easy for anyone to communicate privately,they use recognize the signature as authentic,but impossible for anyone other than the legitimate signer to produce it.We will call any Ky=a mod g (8) such technique one-way authentication.Since any digital signal
34 DIFFIE AND HELLMAN can achieve cost ratios approximately 10 000 to 1, which are as their key. User i obtains Kij by obtaining Yj from the public too small for most applications. If inexpensive, high bandwidth file and letting data links come available, ratios of a million to one or greater could achieved and the system would be of substantial practi- Kij 5 Yj Xi mod q (9) cal value. We now suggest a new public key distribution system which has several advantages. First, it requires only one ‘‘key’’ to 5 (aXj ) Xi mod q (10) be exchanged. Second, the cryptanalytic effort bears to grow exponentially in the effort of the legitimate users. And, third, its use can be tied to a public file of user information which 5 aXjXi 5 aXjXi mod q. (11) serves to authenticate user A to user B vice versa. By making the public file essentially a read memory, one personal appearance User j obtains Kij in the similar fashion allows a user to authenticate his identity many times to many users. rkle’s technique requires A and B to verify each other’s Kij 5 Yi Xj mod q. (12) activities through other means. The new technique makes use of the apparent difficulty Another user must compute Kij from Yi and Yj computing logarithms over a finite field GF , for example, (q) with a one number q of elements. Let by computing Kij 5 Yi Y 5 a (logaYj) mod q. (13) x mod q, for 1 # X # q 2 1, (4) Here a is a fixed primitive element of GF(q), then X is arranged We thus see that if logs mod q are easily computed the system to as the logarithm of Y to the base a, mod q: can be broken. While we do not currently have a proof of the converse (i.e., that the system is secure if logs mod q are X 5 loga Y mod q, for 1 # Y # q 2 1. (5) difficult to compute), neither do we see any way to compute Kij from Yi and Yj without first obtaining either Xi or Xj. Calculation of Y from X is easy, taking at most 2 3 log2 q If q is a prime slightly less than 2b , then all quantities are multiplications [6, pp. 398–422]. For example, for X 5 representable as b bit numbers. Exponentiation then takes at most 2b multiplications mod q, while by hypothesis taking logs Y 5 a18 5 (((a2 ) 2 ) 2 ) 2 3 a2 . (6) requires q1/2 5 21/2 operations. The cryptanalytic effort therefore grows exponentially relative to legitimate efforts. If b 5 200, Computing X from Y, on the other hand can be much more cult then at most 400 multiplications are required to compute Yi and, for certain carefully chosen values of q, requires on the from Xi, or Kij from Yi and Xj, yet taking logs mod q requires order of q1/2 operations, using the best known ithm [7, pp. 9, 2100 or approximately 1030 operations. 575–576], [8]. The security of our technique depends crucially on the seculty of computing logarithms mod q, and if an algorithm whose 4 ONE-WAY AUTHENTICATION complexity grew as log2q were to be found, our m would be broken. While the simplicity of the problem statement might The problem of authentication is perhaps an even more serious allow such simple algorithms, right instead allow a proof of barrier to the universal adoption of telecommunications for the problem’s difficulty. How we assume that the best known business transactions than the problem of key distribution. algorithm for uting logs mod q is in fact close to optimal and Authentication is at the heart of any system involving contracts hence q1/2 is a good measure of the problem’s complexity, and billing. Without it, business cannot function. Current elecproperly chosen q. tronic authentication systems cannot meet the need for a purely Such user generates an independent random number chosen digital, unforgeable, message dependent signature. They prouniformly from the set of integers {1,2, ???, q—such keeps vide protection against third party forgeries, but do not protect Xi secret, but places against disputes between transmitter and receiver. In order to develop a system capable of replacing the current Y written contract with some purely electronic form of communi- i 5 aXi mod q (7) cation, we must discover a digital phenomenon with the same Public file with his name and address. When users i wish to properties as a written signature. It must be easy for anyone to communicate privately, they use recognize the signature as authentic, but impossible for anyone other than the legitimate signer to produce it. We will call any K such technique one-way authentication. Since any digital signal ij 5 aXiXj mod q (8)
NEW DIRECTIONS IN CRYPTOGRAPHY 35 can be copied precisely,a true digital signature must be recog-a value y and knowledge of f.to calculate any x whatsoever nizable without being known. with the property that fx)=y.Indeed,if fis noninvertible in Consider the "login"problem in a multiuser computer sys- the usual sense,it may make the task of finding an inverse tem.When setting up his account,the user chooses a password image easier.In the extreme,if fx)=yo for all x in the domain, which is entered into the system's password directory.Each then the range off is (vo,and we can take any x as f(vo). time he logs in,the user is again asked to provide his password. It is therefore necessary that fnot be too degenerate.A small By keeping this password secret from all other users,forged degree of degeneracy is tolerable and,as discussed later,is logins are prevented.This,however,makes it vital to preserve probably present in the most promising class of one-way the security of the password directory since the information it functions. contains would allow perfect impersonation of any user.The Polynomials offer an elementary example of one-way func- problem is further compounded if system operators have legiti-tions.It is much harder to find a root xo of the polynomial mate reasons for accessing the directory.Allowing such legiti-equation p(x)=y than it is to evaluate the polynomial p(x)at mate accesses,but preventing all others,is next to impossible.x=xo.Purdy [11]has suggested the use of sparse polynomials This leads to the apparently impossible requirement for a of very high degree over finite fields,which appear to have new login procedure capable of judging the authenticity of very high ratios of solution to evaluation time.The theoretical passwords without actually knowing them.While appearing to basis for one-way functions is discussed at greater length in be a logical impossibility,this proposal is easily satisfied.When Section VI.And,as shown in Section V,one-way functions the user first enters his password PW.the computer automati- are easy to devise in practice. cally and transparently computes a function fPl)and stores The one-way function login protocol solves only some of this,not PW.in the password directory.At each successive the problems arising in a multiuser system.It protects against login,the computer calculates f),where X is the proffered compromise of the system's authentication data when it is not password,and compares f)with the stored value APW).If in use,but still requires the user to send the true password to and only if they are equal,the user is accepted as being authen-the system.Protection against eaves-dropping must be provided tic.Since the function fmust be calculated once per login,its by additional encryption,and protection against the threat of computation time must be small.A million instructions(costing dispute is absent altogether. approximately $0.10 at bicentennial prices)seems to be a rea- A public key cryptosystem can be used to produce a true sonable limit on this computation.If we could ensure,however.one-way authentication system as follows.If user 4 wishes to that calculation off required 1030 or more instructions,some- send a message M to user B.he "deciphers"it in his secret one who had subverted the system to obtain the password deciphering key and sends D(M).When user B receives it,he directory could not in practice obtain PW from APM),and can read it,and be assured of its authenticity by "enciphering" could thus not perform an unauthorized login.Note that APW)it with user 4's public enciphering key E4.B also saves D(M) is not accepted as a password by the login program since it as proof that the message came from A.Anyone can check this will automatically compute AAPW))which will not match the claim by operating on D(M)with the publicly known operation entry APW)in the password directory. E to recover M.Since only A could have generated a message We assume that the function fis public information,so that with this property,the solution to the one-way authentication it is not ignorance of fwhich makes calculation off difficult.problem would follow immediately from the development of Such functions are called one-way functions and were first public key cryptosystems. employed for use in login procedures by R.M.Needham [9,p. One-way message authentication has a partial solution sug- 91].They are also discussed in two recent papers [10],[11]gested to the authors by Leslie Lamport of Massachusetts Com- which suggest interesting approaches to the design of one- puter Associates.This technique employs a one-way function way functions. f mapping k-dimensional binary space into itself for k on the More precisely,a function f is a one-way fimnction if,for order of 100.If the transmitter wishes to send an N bit message any argument x in the domain of f.it is easy to compute the he generates 2N.randomly chosen.k-dimensional binary vec- corresponding value fx),yet,for almost all y in the range of tors x2Y2,.,xN,Yy which he keeps secret.The receiver f.it is computationally infeasible to solve the equationy=fx)is given the corresponding images under f.namely y,Yi2,Y2 for any suitable argument x. ·'yw,Yx.Later,when the message m=(m1,m2,···,mw)isto It is important to note that we are defining a function which be sent,the transmitter sends xi or Xi depending on whether is not invertible from a computational point of view.but whose m =0 or 1.He sends x2 or X2 depending on whether m2 noninvertibility is entirely different from that normally encoun-0 or 1.etc.The receiver operates with f on the first received tered in mathematics.A function f is normally called"nonin-block and sees whether it yields y or Y as its image and thus vertible"when the inverse of a point y is not unique,(i.e.,there learns whether it was x or Xi,and whether m=0 or 1.In a exist distinct pointsx and x2 such thatfx)=y=fx2)).We similar manner the receiver is able to determine m.m....m. emphasize that this is not the sort of inversion difficulty that But the receiver is incapable of forging a change in even one is required.Rather,it must be overwhelmingly difficult,given bit of m
NEW DIRECTIONS IN CRYPTOGRAPHY 35 can be copied precisely, a true digital signature must be recog- a value y and knowledge of f, to calculate any x whatsoever nizable without being known. with the property that f(x) 5 y. Indeed, if f is noninvertible in Consider the “login” problem in a multiuser computer sys- the usual sense, it may make the task of finding an inverse image easier. In the extreme, if f(x) [ y0 tem. When setting up his account, the user chooses a password for all x in the domain, which is entered into the system’s password directory. Each then the range of f is {y0}, and we can take any x as f 21 (y0). time he logs in, the user is again asked to provide his password. It is therefore necessary that f not be too degenerate. A small By keeping this password secret from all other users, forged degree of degeneracy is tolerable and, as discussed later, is logins are prevented. This, however, makes it vital to preserve probably present in the most promising class of one-way the security of the password directory since the information it functions. contains would allow perfect impersonation of any user. The Polynomials offer an elementary example of one-way funcproblem is further compounded if system operators have legiti- tions. It is much harder to find a root x0 of the polynomial mate reasons for accessing the directory. Allowing such legiti- equation p(x) 5 y than it is to evaluate the polynomial p(x) at mate accesses, but preventing all others, is next to impossible. x 5 x0. Purdy [11] has suggested the use of sparse polynomials This leads to the apparently impossible requirement for a of very high degree over finite fields, which appear to have new login procedure capable of judging the authenticity of very high ratios of solution to evaluation time. The theoretical passwords without actually knowing them. While appearing to basis for one-way functions is discussed at greater length in be a logical impossibility, this proposal is easily satisfied. When Section VI. And, as shown in Section V, one-way functions the user first enters his password PW, the computer automati- are easy to devise in practice. cally and transparently computes a function f(PW) and stores The one-way function login protocol solves only some of this, not PW, in the password directory. At each successive the problems arising in a multiuser system. It protects against login, the computer calculates f(X), where X is the proffered compromise of the system’s authentication data when it is not password, and compares f(X) with the stored value f(PW). If in use, but still requires the user to send the true password to and only if they are equal, the user is accepted as being authen- the system. Protection against eaves-dropping must be provided tic. Since the function f must be calculated once per login, its by additional encryption, and protection against the threat of computation time must be small. A million instructions (costing dispute is absent altogether. approximately $0.10 at bicentennial prices) seems to be a rea- A public key cryptosystem can be used to produce a true sonable limit on this computation. If we could ensure, however, one-way authentication system as follows. If user A wishes to that calculation of f send a message M to user B, he “deciphers” it in his secret 21 required 1030 or more instructions, someone who had subverted the system to obtain the password deciphering key and sends DA(M). When user B receives it, he directory could not in practice obtain PW from f(PW), and can read it, and be assured of its authenticity by “enciphering” could thus not perform an unauthorized login. Note that f(PW) it with user A’s public enciphering key EA. B also saves DA(M) is not accepted as a password by the login program since it as proof that the message came from A. Anyone can check this will automatically compute f(f(PW)) which will not match the claim by operating on DA(M) with the publicly known operation entry f(PW) in the password directory. EA to recover M. Since only A could have generated a message We assume that the function f is public information, so that with this property, the solution to the one-way authentication it is not ignorance of f which makes calculation of f problem would follow immediately from the development of 21 difficult. Such functions are called one-way functions and were first public key cryptosystems. employed for use in login procedures by R.M. Needham [9, p. One-way message authentication has a partial solution sug- 91]. They are also discussed in two recent papers [10], [11] gested to the authors by Leslie Lamport of Massachusetts Comwhich suggest interesting approaches to the design of one- puter Associates. This technique employs a one-way function way functions. f mapping k-dimensional binary space into itself for k on the More precisely, a function f is a one-way function if, for order of 100. If the transmitter wishes to send an N bit message any argument x in the domain of f, it is easy to compute the he generates 2N, randomly chosen, k-dimensional binary vectors x1,X1,x2,X2 corresponding value f(x), yet, for almost all y in the range of , ???, xN,XN which he keeps secret. The receiver f, it is computationally infeasible to solve the equation y 5 f(x) is given the corresponding images under f, namely y1,Y1,y2,Y2 ???,yN,YN. Later, when the message m 5 (m1,m2 for any suitable argument x. , ???,mN) is to It is important to note that we are defining a function which be sent, the transmitter sends x1 or X1 depending on whether is not invertible from a computational point of view, but whose m1 5 0 or 1. He sends x2 or X2 depending on whether m2 5 noninvertibility is entirely different from that normally encoun- 0 or 1, etc. The receiver operates with f on the first received tered in mathematics. A function f is normally called “nonin- block and sees whether it yields y1 or Y1 as its image and thus vertible” when the inverse of a point y is not unique, (i.e., there learns whether it was x1 or X1, and whether m1 5 0 or 1. In a similar manner the receiver is able to determine m2,m3 exist distinct points x ,...,mN. 1 and x2 such that f(x1) 5 y 5 f(x2)). We emphasize that this is not the sort of inversion difficulty that But the receiver is incapable of forging a change in even one is required. Rather, it must be overwhelmingly difficult, given bit of m
36 DIFFIE AND HELLMAN This is only a partial solution because of the approximately As indicated in Fig.3,take the cryptosystem (Sk:(P) 100-fold data expansion required.There is,however,a modifi- KE(K)which is secure against a known plaintext attack,P= cation which eliminates the expansion problem when N is Po and consider the map roughly a megabit or more.Let g be a one-way mapping from binary N-space to binary n-space where n is approximately 50. f{K→{C} (14) Take the N bit message m and operate on it with g to obtain the n bit vector m'.Then use the previous scheme to send m'. defined by IfN 105,n=50,and 100,this adds kn 5000 authentication bits to the message.It thus entails only a 5 percent data expan- AX)=Sx(Po) (15) sion during transmission(or 15 percent if the initial exchange y,Yi,..,yN,Yw is included).Even though there are large This function is one-way because solving for x given A)is number of other messages(2"on the average)with the same equivalent to the cryptanalytic problem of finding the key from authentication sequence,the one-wayness makes them compu- a single known plaintext-cryptogram pair.Public knowledge tationally infeasible to find and us to forge.Actually g must of fis now equivalent to public knowledge of (Sk)and Po. be somewhat stronger than normal one-way function,since an While the converse of this result is not necessarily true,it opponent has not only but also one of its inverse images m.It i is possible for a function originally found in the search for must be hard even given m to find a different inverse image one-way functions to yield a good cryptosystem.This actually of m.Finding such functions appears to offer little trouble(see happened with the discrete exponential function discussed in Section V). Section III [8]. There is another partial solution to the one-way user authenti- One-way functions are basic to both block ciphers and key cation problem.The user generates a password which he keeps generators.A key generator is a pseudorandom bit generator secret.He gives the system fT(,where is a one-way function.whose output,the keystream,is added modulo 2 to a message At time t the appropriate authenticator is f(),which can be represented in binary form,in imitation of a one-time pad.The checked by the system by applying f().Because of the one-key is used as a"seed"which determines the pseudorandom wayness of f.responses are of no value in forging a new keystream sequence.A known plaintext attack thus reduces to response.The problem with this solution is that it can require the problem of determining the key from the keystream.For a fair amount of computation for legitimate login (although the system to be secure,computation of the key from the keys- any orders of magnitude less than for forgery).If for example tream must be computationally infeasible.While,for the system t is incremented every second and the system must work for to be usable,calculation of the keystream from the key must one month on each password then T=2.6 million.Both the be computationally simple.Thus a good key generator is,almost user and the system must then iterate faverage of 1.3 million by definition,a one-way function. times per login.While not insurmountable,this problem obvi- Use of either type of cryptosystem as a one way function ously limits use of the technique.The problem could be over- suffers from a minor problem.As noted earlier,if the function come if a simple method of calculating f2t)for n=1.2,... fis not uniquely invertible,it is not necessary (or possible)to could be found,much ofs=((2)2)2.For then binary decom-find the actual value of X used.Rather any X with the same positions of T-and t would allow rapid computation of f- image will suffice.And,while each mapping Sk in a cryptosys- and f.It may be,however,that rapid computation of p pre-tem must be bijective,there is no such restriction on the function cludes from being one-way. ffrom key to cryptogram defined above.Indeed,guaranteeing that a cryptosystem has this property appears quite difficult.In a good cryptosystem the mapping f can be expected to have 5 PROBLEM INTERRELATIONS AND the characteristics of a randomly chosen mapping(i.e.,fX)is chosen uniformly from all possible Y,and successive choices TRAP DOORS are independent).In this case,if Y is chosen uniformly and there are an equal number of keys and messages (Y and Y), In this section,we will show that some of the cryptographic then the probability that the resultant Y has k+1 inverses is problems presented thus far can be reduced to others,thereby defining a loose ordering according to difficulty.We also intro- duce the more difficult problem trap doors. In Section II we showed that a cryptographic system tended for privacy can also be used to provide authentication against third party forgeries.Such a system can used to create other cryptographic objects,as well. A cryptosystem which is secure against a known maintext attack can be used to produce a one-way function. Figure 3:Secure cryptosystem used as one-way function
36 DIFFIE AND HELLMAN This is only a partial solution because of the approximately As indicated in Fig. 3, take the cryptosystem {SK:{P} → 100-fold data expansion required. There is, however, a modifi- KP{K} which is secure against a known plaintext attack, P 5 cation which eliminates the expansion problem when N is P0 and consider the map roughly a megabit or more. Let g be a one-way mapping from binary N-space to binary n-space where n is approximately 50. f:{K} → {C} (14) Take the N bit message m and operate on it with g to obtain the n bit vector m8. Then use the previous scheme to send m8. defined by If N 5 106 , n 5 50, and 100, this adds kn 5 5000 authentication bits to the message. It thus entails only a 5 percent data expan- f(X) 5 SX(P0) (15) sion during transmission (or 15 percent if the initial exchange y1,Y1, ???, yN,YN is included). Even though there are large This function is one-way because solving for X given f(X) is number of other messages (2N2n on the average) with the same equivalent to the cryptanalytic problem of finding the key from authentication sequence, the one-wayness makes them compu- a single known plaintext-cryptogram pair. Public knowledge of f is now equivalent to public knowledge of {SK} and P0 tationally infeasible to find and us to forge. Actually g must . be somewhat stronger than normal one-way function, since an While the converse of this result is not necessarily true, it opponent has not only but also one of its inverse images m. It is possible for a function originally found in the search for must be hard even given m to find a different inverse image one-way functions to yield a good cryptosystem. This actually of m8. Finding such functions appears to offer little trouble (see happened with the discrete exponential function discussed in Section V). Section III [8]. There is another partial solution to the one-way user authenti- One-way functions are basic to both block ciphers and key cation problem. The user generates a password which he keeps generators. A key generator is a pseudorandom bit generator secret. He gives the system f whose output, the keystream, is added modulo 2 to a message T(X), where is a one-way function. At time t the appropriate authenticator is f T2t (X), which can be represented in binary form, in imitation of a one-time pad. The checked by the system by applying ft (X). Because of the one- key is used as a “seed” which determines the pseudorandom wayness of f, responses are of no value in forging a new keystream sequence. A known plaintext attack thus reduces to response. The problem with this solution is that it can require the problem of determining the key from the keystream. For a fair amount of computation for legitimate login (although the system to be secure, computation of the key from the keysany orders of magnitude less than for forgery). If for example tream must be computationally infeasible. While, for the system t is incremented every second and the system must work for to be usable, calculation of the keystream from the key must one month on each password then T 5 2.6 million. Both the be computationally simple. Thus a good key generator is, almost user and the system must then iterate f average of 1.3 million by definition, a one-way function. times per login. While not insurmountable, this problem obvi- Use of either type of cryptosystem as a one way function ously limits use of the technique. The problem could be over- suffers from a minor problem. As noted earlier, if the function come if a simple method of calculating f f is not uniquely invertible, it is not necessary (or possible) to (2Fn), for n 5 1,2, ??? could be found, much of X8 5 ((X2 ) 2 ) 2 . For then binary decom- find the actual value of X used. Rather any X with the same positions of T—and t would allow rapid computation of f image will suffice. And, while each mapping SK in a cryptosys- T2t and ft . It may be, however, that rapid computation of f n pre- tem must be bijective, there is no such restriction on the function cludes from being one-way. f from key to cryptogram defined above. Indeed, guaranteeing that a cryptosystem has this property appears quite difficult. In a good cryptosystem the mapping f can be expected to have the characteristics of a randomly chosen mapping (i.e., f(Xi) is 5 PROBLEM INTERRELATIONS AND chosen uniformly from all possible Y, and successive choices TRAP DOORS are independent). In this case, if X is chosen uniformly and there are an equal number of keys and messages (X and Y), In this section, we will show that some of the cryptographic then the probability that the resultant Y has k 1 1 inverses is problems presented thus far can be reduced to others, thereby defining a loose ordering according to difficulty. We also introduce the more difficult problem trap doors. In Section II we showed that a cryptographic system tended for privacy can also be used to provide authentication against third party forgeries. Such a system can used to create other cryptographic objects, as well. A cryptosystem which is secure against a known maintext attack can be used to produce a one-way function. Figure 3: Secure cryptosystem used as one-way function
NEW DIRECTIONS IN CRYPTOGRAPHY 37 approximately e/k!for k =0,1,2,3,....This is a Poisson be no better off than anyone else.The situation is precisely distribution with mean A=1,shifted by I unit.The expected analogous to a combination lock.Anyone who knows the com- number of inverses is thus only 2.While it is possible for f bination can do in seconds what even a skilled locksmith would to be more degenerate,a good cryptosystem will not be too require hours to accomplish.And yet,ifhe forgets the combina- degenerate since then the key is not being well used.In the tion,he has no advantage worst case,if f)=Yo for some Yo,we have Sk(Po)=Co, and encipherment of Po would not depend on the key at all! A trap-door cryptosystem can be used to produce a public While we are usually interested in functions whose domain key distribution system. and range are of comparable size,there are exceptions.In the For 4 and B to establish a common private key,chooses a previous section we required a one-way function mapping long key at random and sends an arbitrary plaintext-cryptogram pair strings onto much shorter ones.By using a block cipher whose to B.B.who made the trap-door cipher public,but kept the key length is larger than the blocksize,such functions can be trap-door information secret uses the plaintext-cryptogram pair obtained using the above technique. to solve for the key.4 and B now have a key in common. Evans et al.[10]have a different approach to the problem There is currently little evidence for the existence of trap- of constructing a one-way function from a block cipher.Rather door ciphers.However they are a distinct possibility and should than selecting a fixed Po as the input,they use the function be remembered when accepting a cryptosystem from a possible opponent [12]. AX)=S(X) (16) By definition,we will require that a trap-door problem be one in which it is computationally feasible to devise the trap This is an attractive approach because equations of this form door.This leaves room for yet a third type of entity for which are generally difficult to solve,even when the family S is we shall use the prefix "quasi."For example a quasi one-way comparatively simple.This added complexity,however,finction is not one-way in that an easily computed inverse destroys the equivalence between the security of the system S exists.However,it is computationally infeasible even for the under a known plaintext attack and the one-wayness of f. designer,to find the easily computed inverse.Therefore a quasi Another relationship has already been shown in Section IV.one-way function can be used in place of a one-way function A public key cryptosystem can be used to generate a one- with essentially no loss in security. way authentication system. Losing the trap-door information to a trap-door one-way function makes it into a quasi one-way function,but there may The converse does not appear to hold,making the construc- also be one-way functions not obtainable in this manner. tion of a public key cryptosystem a strictly more difficult prob- It is entirely a matter of definition that quasi one-way func- lem than one-way authentication.Similarly,a public key tions are excluded from the class of one-way functions.One cryptosystem can be used as a public key distribution system,could instead talk of one-way functions in the wide sense or but not conversely. in the strict sense. Since in a public key cryptosystem the general system in Similarly,a quasi secure cipher is a cipher which will success- which E and D are used must be public,specifying E specifies fully resist cryptanalysis,even by its designer,and yet for which a complete algorithm for transforming input messages into there exists a computationally efficient cryptanalytic algorithm output cryptograms.As such a public key system is really a (which is of course computationally infeasible to find).Again, set of trap-door one-way fimctions.These are functions which from a practical point of view,there is essentially no difference are not really one-way in that simply computed inverses exist. between a secure cipher and a quasi secure one. But given an algorithm for the forward function it is computa- We have already seen that public key cryptosystems imply tionally infeasible to find a simply computed inverse.Only the existence of trap-door one-way functions.However the through knowledge of certain trap-door information (e.g,the converse is not true.For a trap-door one-way function to be random bit string which produced the E-D pair)can one easily usable as a public key cryptosystem,it must be invertible(i.e., find the easily computed inverse. have a unique inverse. Trap doors have already been seen in the previous paragraph in the form of trap-door one-way functions,but other variations exist.A trap-door cipher is one which strongly resists crypt- 6 COMPUTATIONAL COMPLEXITY analysis by anyone not in possession of trap-door information used in the design of the cipher.This allows the designer to Cryptography differs from all other fields of endeavor in the break the system after he has sold it to a client and yet falsely ease with which its requirements may appear to be satisfied. to maintain his reputation as a builder of secure systems.It is Simple transformations will convert a legible text into an appar- important to note that it is not greater cleverness or knowledge ently meaningless jumble.The critic,who wishes to claim that of cryptography which allows the designer to do what others meaning might yet be recovered by cryptanalysis,is then faced cannot.If he were to lose the trap-door information he would with an arduous demonstration if he is to prove his point of
NEW DIRECTIONS IN CRYPTOGRAPHY 37 approximately e21 /k! for k 5 0,1,2,3,??? . This is a Poisson be no better off than anyone else. The situation is precisely distribution with mean l 5 1, shifted by 1 unit. The expected analogous to a combination lock. Anyone who knows the comnumber of inverses is thus only 2. While it is possible for f bination can do in seconds what even a skilled locksmith would to be more degenerate, a good cryptosystem will not be too require hours to accomplish. And yet, if he forgets the combinadegenerate since then the key is not being well used. In the tion, he has no advantage. worst case, if f(X) [ Y0 for some Y0, we have SK(P0) [ C0, A trap-door cryptosystem can be used to produce a public and encipherment of P0 would not depend on the key at all! key distribution system. While we are usually interested in functions whose domain and range are of comparable size, there are exceptions. In the For A and B to establish a common private key, chooses a previous section we required a one-way function mapping long key at random and sends an arbitrary plaintext-cryptogram pair strings onto much shorter ones. By using a block cipher whose to B. B, who made the trap-door cipher public, but kept the key length is larger than the blocksize, such functions can be trap-door information secret uses the plaintext-cryptogram pair obtained using the above technique. to solve for the key. A and B now have a key in common. Evans et al. [10] have a different approach to the problem There is currently little evidence for the existence of trapof constructing a one-way function from a block cipher. Rather door ciphers. However they are a distinct possibility and should than selecting a fixed P0 as the input, they use the function be remembered when accepting a cryptosystem from a possible opponent [12]. f(X) 5 SX(X) (16) By definition, we will require that a trap-door problem be one in which it is computationally feasible to devise the trap This is an attractive approach because equations of this form door. This leaves room for yet a third type of entity for which are generally difficult to solve, even when the family S is we shall use the prefix “quasi.” For example a quasi one-way comparatively simple. This added complexity, however, function is not one-way in that an easily computed inverse destroys the equivalence between the security of the system S exists. However, it is computationally infeasible even for the under a known plaintext attack and the one-wayness of f. designer, to find the easily computed inverse. Therefore a quasi Another relationship has already been shown in Section IV. one-way function can be used in place of a one-way function with essentially no loss in security. A public key cryptosystem can be used to generate a one- Losing the trap-door information to a trap-door one-way way authentication system. function makes it into a quasi one-way function, but there may The converse does not appear to hold, making the construc- also be one-way functions not obtainable in this manner. tion of a public key cryptosystem a strictly more difficult prob- It is entirely a matter of definition that quasi one-way funclem than one-way authentication. Similarly, a public key tions are excluded from the class of one-way functions. One cryptosystem can be used as a public key distribution system, could instead talk of one-way functions in the wide sense or but not conversely. in the strict sense. Since in a public key cryptosystem the general system in Similarly, a quasi secure cipher is a cipher which will successwhich E and D are used must be public, specifying E specifies fully resist cryptanalysis, even by its designer, and yet for which a complete algorithm for transforming input messages into there exists a computationally efficient cryptanalytic algorithm output cryptograms. As such a public key system is really a (which is of course computationally infeasible to find). Again, set of trap-door one-way functions. These are functions which from a practical point of view, there is essentially no difference are not really one-way in that simply computed inverses exist. between a secure cipher and a quasi secure one. But given an algorithm for the forward function it is computa- We have already seen that public key cryptosystems imply tionally infeasible to find a simply computed inverse. Only the existence of trap-door one-way functions. However the through knowledge of certain trap-door information (e.g., the converse is not true. For a trap-door one-way function to be random bit string which produced the E-D pair) can one easily usable as a public key cryptosystem, it must be invertible (i.e., find the easily computed inverse. have a unique inverse.) Trap doors have already been seen in the previous paragraph in the form of trap-door one-way functions, but other variations exist. A trap-door cipher is one which strongly resists crypt- 6 COMPUTATIONAL COMPLEXITY analysis by anyone not in possession of trap-door information used in the design of the cipher. This allows the designer to Cryptography differs from all other fields of endeavor in the break the system after he has sold it to a client and yet falsely ease with which its requirements may appear to be satisfied. to maintain his reputation as a builder of secure systems. It is Simple transformations will convert a legible text into an apparimportant to note that it is not greater cleverness or knowledge ently meaningless jumble. The critic, who wishes to claim that of cryptography which allows the designer to do what others meaning might yet be recovered by cryptanalysis, is then faced cannot. If he were to lose the trap-door information he would with an arduous demonstration if he is to prove his point of
38 DIFFIE AND HELLMAN view correct.Experience has shown,however,that few systems the NP includes the class p and one of the great open sections can resist the concerted attack of skillful cryptanalysts,and in complexity theory is whether the class NP is directly larger. many supposedly secure systems have subsequently been Among the problems known to be solvable in NP time,not broken. known to be solvable in P time,are versions of the eling In consequence of this,judging the worth of new systems salesman problem,the satisfiability problem for positional cal- has always been a central concern of cryptographers.During culus,the knapsack problem,the graph ring problem,and many the sixteenth and seventeenth centuries,mathematical argu- scheduling and minimization problems [13,pp.363-404],[14]. ments were often invoked to argue the strength of cryptographic We see that it is not lack of interest or effort which has prevented methods,usually relying on counting methods which showed people from finding solutions in P time for these problems.It the astronomical number possible keys.Though the problem is thus strongly believed that at least one of these problems is far too difficult to laid to rest by such simple methods,even must not be in the class p and that therefore the class NP is the noted alraist Cardano fell into this trap [2,p.145].As strictly larger. systems those strength had been so argued were repeatedly Karp has identified a subclass of the NP problems,called broken,the notion of giving mathematical proofs for the secu- NP complete,with the property that if any one of them is in rity of systems fell into disrepute and was replaced by certica- B then all NP problems are in P Karp lists 21 problems which tion via crypanalytic assault. are NP complete,including all of the problems mentioned During this century,however,the pendulum has begun swing above [14]. back in the other direction.In a paper intimately connected While the NP complete problems show promise for crypto- with the birth of information theory,Shannon showed that the graphic use,current understanding of their difficulty includes one time pad system,which had been use since the late twenties only worst case analysis.For cryptographic purposes,typical offered "perfect secrecy(a summ of unconditional security). computational costs must be considered.If,however,we replace The probably secure terms investigated by Shannon rely on the worst case computation time with average or typical computa- use of either they whose length grows linearly with the length tion time as our complexity measure,the current proofs of the of the usage or on perfect source coding and are therefore equivalences among the NP complete problems are no longer too provideldy for most purposes.We note that neither public valid.This suggests several interesting topics for research.The cryptosystems nor one-way authentication systems can uncon- ensemble and typicality concepts familiar to information theo- ditionally secure because the public information always deter- rists have an obvious role to play. mines the secret information uniquely among members of a finite set.With unlimited computation,problem could therefore We can now identify the position of the general cryptanalytic problem among all computational problems. be solved by a straightforward touch. The past decade has seen the rise of two closely related The cryptanalytic difficulty of a system whose encryption and decryption operations can be done in P time cannot be deciplines devoted to the study of the costs of computation computational complexity theory and the analysis of loga- greater than NP rithms.The former has classified known problems in computing To see this,observe that any cryptanalytic problem can be into broad classes by difficulty,while the latter concentrated on solved by finding a key,inverse image,etc.,chosen from a finding better algorithms and lying the resources they consume. finite set.Choose the key nondeterministically and verify in P After a brief discussion into complexity theory,we will examine time that it is the correct one.If there are M possible keys to its application to cryptography,particularly the analysis of one- choose from,an M-fold parallelism must be employed.For way functions. example in a known plaintext attack,the plaintext is encrypted The function is said to belong to the complexity class P(for simultaneously under each of the keys and compared with the polynomial)if it can be computed by a deterministic making cryptogram.Since,by assumption,encryption takes only P Machine in a time which is bounded above by some polynomial time,the cryptanalysis takes only NP time. function of the length of its input.One might think of this as We also observe that the general cryptanalytic problem is the class of easily computed functions,but more accurate to NP complete.This follows from the breadth of our definition say that a function not in this class must be hard to compute of cryptographic problems.A one-way function with an NP for at least some inputs.There problems which are known not complete inverse will be discussed next. to be in the class P [13.405-4251. Cryptography can draw directly from the theory of NP com- There are many problems which arise in engineering which plexity by examining the way in which NP complete problems cannot be solved in polynomial time by any known uniques, can be adapted to cryptographic use.In particular,there is an unless they are run on a computer with an submited degree of NP complete problem known as the knapsack problem which parallelism.These problems may or not belong to the class p lends itself readily to the construction of a one-way function. but belong to the class NP(nondeterministic,polynomial)of LetY=x)=a·.·x where a is a known vector of n problems solvable polynomial time on a "nondeterministic"intergers(a,z,,a)andx is a binary n-vector.Calculation computer(i.e.,with an unlimited degree ofparallelism).Clearly of y is simple,involving a sum of at most n integers.The
38 DIFFIE AND HELLMAN view correct. Experience has shown, however, that few systems the NP includes the class P, and one of the great open sections can resist the concerted attack of skillful cryptanalysts, and in complexity theory is whether the class NP is directly larger. many supposedly secure systems have subsequently been Among the problems known to be solvable in NP time, not broken. known to be solvable in P time, are versions of the eling In consequence of this, judging the worth of new systems salesman problem, the satisfiability problem for positional calhas always been a central concern of cryptographers. During culus, the knapsack problem, the graph ring problem, and many the sixteenth and seventeenth centuries, mathematical argu- scheduling and minimization problems [13, pp. 363–404], [14]. ments were often invoked to argue the strength of cryptographic We see that it is not lack of interest or effort which has prevented methods, usually relying on counting methods which showed people from finding solutions in P time for these problems. It the astronomical number possible keys. Though the problem is thus strongly believed that at least one of these problems is far too difficult to laid to rest by such simple methods, even must not be in the class P, and that therefore the class NP is the noted alraist Cardano fell into this trap [2, p. 145]. As strictly larger. systems those strength had been so argued were repeatedly Karp has identified a subclass of the NP problems, called broken, the notion of giving mathematical proofs for the secu- NP complete, with the property that if any one of them is in rity of systems fell into disrepute and was replaced by certica- P, then all NP problems are in P. Karp lists 21 problems which tion via crypanalytic assault. are NP complete, including all of the problems mentioned During this century, however, the pendulum has begun swing above [14]. back in the other direction. In a paper intimately connected While the NP complete problems show promise for crypto- with the birth of information theory, Shannon showed that the graphic use, current understanding of their difficulty includes one time pad system, which had been use since the late twenties only worst case analysis. For cryptographic purposes, typical offered “perfect secrecy” (a summ of unconditional security). computational costs must be considered. If, however, we replace The probably secure terms investigated by Shannon rely on the worst case computation time with average or typical computa- use of either they whose length grows linearly with the length tion time as our complexity measure, the current proofs of the of the usage or on perfect source coding and are therefore equivalences among the NP complete problems are no longer too provideldy for most purposes. We note that neither public valid. This suggests several interesting topics for research. The cryptosystems nor one-way authentication systems can uncon- ensemble and typicality concepts familiar to information theo- ditionally secure because the public information always deter- rists have an obvious role to play. mines the secret information uniquely among members of a We can now identify the position of the general cryptanalytic finite set. With unlimited computation, problem could therefore problem among all computational problems. be solved by a straightforward touch. The cryptanalytic difficulty of a system whose encryption The past decade has seen the rise of two closely related and decryption operations can be done in P time cannot be deciplines devoted to the study of the costs of computation greater than NP. computational complexity theory and the analysis of loga- To see this, observe that any cryptanalytic problem can be rithms. The former has classified known problems in computing solved by finding a key, inverse image, etc., chosen from a into broad classes by difficulty, while the latter concentrated on finite set. Choose the key nondeterministically and verify in P finding better algorithms and lying the resources they consume. time that it is the correct one. If there are M possible keys to After a brief discussion into complexity theory, we will examine choose from, an M-fold parallelism must be employed. For its application to cryptography, particularly the analysis of one- example in a known plaintext attack, the plaintext is encrypted way functions. simultaneously under each of the keys and compared with the The function is said to belong to the complexity class P (for cryptogram. Since, by assumption, encryption takes only P polynomial) if it can be computed by a deterministic making Machine in a time which is bounded above by some polynomial time, the cryptanalysis takes only NP time. We also observe that the general cryptanalytic problem is function of the length of its input. One might think of this as NP complete. This follows from the breadth of our definition the class of easily computed functions, but more accurate to say that a function not in this class must be hard to compute of cryptographic problems. A one-way function with an NP complete inverse will be discussed next. for at least some inputs. There problems which are known not Cryptography can draw directly from the theory of NP com- to be in the class P [13,405–425]. There are many problems which arise in engineering which plexity by examining the way in which NP complete problems cannot be solved in polynomial time by any known uniques, can be adapted to cryptographic use. In particular, there is an unless they are run on a computer with an submited degree of NP complete problem known as the knapsack problem which parallelism. These problems may or not belong to the class P, lends itself readily to the construction of a one-way function. but belong to the class NP (nondeterministic, polynomial) of Let Y 5 f(x) 5 a ??? x where a is a known vector of n intergers (a1,a2, ???, an problems solvable polynomial time on a “nondeterministic” ) and x is a binary n-vector. Calculation computer (i.e., with an unlimited degree of parallelism). Clearly of y is simple, involving a sum of at most n integers. The