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 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 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 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