644

IEEE

TRANSACTIONSONINFORMATIONTHEORY,VOL.

IT-22,

NO.

6, NOVEMBER

1976

New Directions in Cryptography
Invited
WHITFIELD

DIFFIEAND

MARTIN

Abstract-Two
kinds of contemporary
developments
in cryptography are examined. Widening applicationsof teleprocessing
have given rise to a need for new types of cryptographic
systems,
which minimize the need for secure key distribution
channels andsupply the equivalent of a written signature. This paper suggests
ways to solve these currently
open problems. It also discusses how
the theories of communicationand computation
are beginning toprovide the tools to solve cryptographic
problems of long standing.

I. INTRODUCTIONWE STAND TODAY on the brink of a revolution in
cryptography. The development of cheap digital
hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade
cryptographic devices down to where they can be used insuch commercial applications as remote cash dispensers
and computer terminals. In turn, such applications create
a need for new types of cryptographic
systems which
minimize the necessity of secure key distribution channels
and supply the equivalent of a written signature. At thesame time, theoretical developments in information theory
and computer science show promise of providing provably
secure cryptosystems, changing this ancient art into ascience.
The development of computer controlled communication networks pron$ses effortless and inexpensive contact
between people or computers on opposite sides of theworld, replacing most mail and many excursions with
telecommunications. For many applications these contacts
must be made secure against both eavesdropping.and theinjection of illegitimate messages. At present, however, thesolution of security problems lags well behind other areasof communications
technology.
Contemporary
cryptography is unable to meet the requirements, in that its use
would impose such severe inconveniences on the systemusers, as to eliminate many of the benefits of teleprocessing.
Manuscript received June 3,1976. This work was partially supportedby the National Science Foundation under NSF Grant ENG 10173.
Portions of this work were presented at the IEEE Information Theory
Workshop;Lenox, MA, June 23-25, 1975 and the IEEE International
Symposium on Information Theory in Ronneby, Sweden, June 21-24,
1976.
W. Diffie is with the Department of Electrical Engineering, Stanford
Universitv. Stanford. CA. and the St,anford Artificial IntelliPence
LabY
oratory, g&ford,
CIk 94.505.
M. E. Hellman is with the Department of Electrical Engineering,
Stanford University, Stanford, CA 94305.

Paper
E. HELLMAN,

MEMBER,IEEE

The best known cryptographic problem is that of privacy: preventing the unauthorized extraction of information from communications
over an insecure channel. In
order to use cryptography to insure privacy, however, it iscurrently necessary for the communicating parties to sharea key which is known to no one else. This is done by sending the key in advance over some secure channel such asprivate courier or registered mail. A private conversation
between two people with no prior acquaintance-is a common occurrence in business, however, and it is unrealistic
to expect initial business contacts to be postponed longenough 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 to large teleprocessing networks.
Section III proposes two approaches to transmitting
keying information over public (i.e., insecure) channels
without compromising the security of the system. In apublic key cryptosystem enciphering and deciphering aregoverned by distinct keys, E and D, such that computing
D from E is computationallyinfeasible (e.g., requiringlOloo instructions). The enciphering key E can thus be
publicly disclosed without compromising the decipheringkey D. Each user of the network can, therefore, place his
enciphering key in a public directory. This enables any userof the system to send a message to any other user enciphered in such a way that only the intended receiver is able
to decipher it. As such, a public key cryptosystem is amultiple access cipher. A private conversation can therefore be held between any two individuals regardless ofwhether they have ever communicated before. Each one
sends messages to the other enciphered in the receiver’s
public enciphering key and deciphers the messages he receives using his own secret deciphering key.
We propose some techniques for developing public key
cryptosystems, but the problem is still largely open.
Public key distribution
systems offer a different approach to eliminating the need for a secure key distribution
channel. In such a system, two users who wish to exchange
a key communicate back and forth until they arrive at a
key in common. A third party eavesdropping on this exchange must find it computationally infeasible to computethe key from the information overheard, A possible solution to the public key distribution
problem is given in
Section III, and Merkle [l] has a partial solution of a different form.
A second problem, amenable to cryptographic solution,
which stands in the way of replacing contemporary busi.

DIFFIEAND

HELLMAN:NEW

DIRECTIONS

IN

ness communications by teleprocessing systems is authentication. In current business, the validity of contracts
is guaranteed by signatures. A signed contract serves aslegal evidence of an agreement which the holder canpresent in court if necessary. The use of signatures, however, requires the transmission and storage of written
contracts. In order to have a purely digital replacement forthis paper instrument, each user must be able to produce
a message whose authenticity can be checked by anyone,
but which could not have been produced by anyone else,
even the recipient. Since only one person can originate
messages but many people can receive messages, this canbe viewed as a broadcast cipher. Current electronic authentication techniques cannot meet this need.
Section IV discusses the problem of providing a true,
digital, message dependent signature. For reasons brought
out there, we refer to this as the one-way authentication
problem. Some partial solutions are given, and it is shown
how any public key cryptosystem can be transformed intoa one-way authentication system.
Section V will consider the interrelationof various
cryptographic problems and introduce the even moredifficult problem of trap doors.
At the same time that communications and computation
have,given rise to new cryptographic problems, their offspring, information theory, and the theory of computation
have begun to supply tools for the solution of important
problems in classical cryptography.
The search for unbreakable codes is one of the oldest
themes of cryptographic research, but until this century
all proposed systems have ultimately been broken. In thenineteen twenties, however, the “one time pad” was invented, and shown to be unbreakable [2, pp. 398-4001. The
theoretical basis underlying this and related systems was
put on a firm foundation a quarter century later by information theory [3]. One time pads require extremely longkeys and are therefore prohibitively expensive in mostapplications.
In contrast, the security of most cryptographic systems
resides in the computational difficulty to the cryptanalystof discovering the plaintext without knowledge of the key.
This problem falls within the domains of computational
complexity and analysis of algorithms, two recent disciplines which study the difficulty of solving computational
problems. Using the results of these theories, it may bepossible to extend proofs of security to more useful classesof systems in the foreseeable future. Section VI explores
this possibility.
Before proceeding to newer developments, we introduce
terminology and define threat environments in the next
section.
II. CONVENTIONAL

645

CRYPTOGRAPHYCRYPTOGRAPHY

Cryptography is the study of “mathematical” systems
for solving two kinds of security problems: privacy andauthentication. A privacy system prevents the extractionof information by unauthorized parties from messages

KEY
SOURCE

Fig. 1.

Flow of informationin conventional cryptographic

system.

transmitted over a public channel, thus assuring the senderof a message that it is being read only by the intended recipient. An authenticationsystemprevents
the unauthorized injection of messages into a public channel, assuring
the receiver of a message of the legitimacy of its sender.
A channel is considered public if its security is inadequate for the needs of its users. A channel such as a telephone line may therefore be considered private by someusers and public by others. Any channel may be threatenedwith eavesdropping or injection or both, depending on its
use. In telephone communication, the threat of injection
is paramount, since the called party cannot determine
which phone is calling. Eavesdropping, which requires theuse of a wiretap, is technically more difficult and legallyhazardous. In radio, by comparison, the situation is reversed. Eavesdropping is passive and involves no legal
hazard, while injection exposes the illegitimate transmitterto discovery and prosecution.
Having divided our problems into those of privacy andauthentication we will sometimes further subdivide authentication into message authentication,
which is the
problem defined above, and user authentication, in which
the only task of the system is to verify that an individual
is who he claims to be. For example, the identity of an individual who presents a credit card must be verified, butthere is no message which he wishes to transmit. In spiteof this apparent absence of a message in user authentication, the two problems are largely equivalent. In user authentication, there is an implicit message “I AM USER X,”
while message authentication is just verification of theidentity of the party sending the message. Differences inthe threat environments and other aspects of these two
subproblems, however, sometimes make it convenient todistinguish between them.
Fig. 1 illustrates the flow of information in a conventional cryptographic system used for privacy of communications. There are three parties: a transmitter, a receiver,and an eavesdropper. The transmitter generates a plaintext or unenciphered message P to be communicated overan insecure channel to the legitimate receiver. In order toprevent the eavesdropper from learning P, the transmitter
operates on P with an invertible transformation SK toproduce the ciphertext or cryptogram C = SK(P). The key
K is transmitted onlv to the legitimate receiver via a securechannel, indicated by a shielded path in Fig. 1. Since thelegitimate receiver knows K, he can decipher C by operating with SK-~ to obtain SK-~(C) = SK-~(SK(P)) = P,
the original plaintext message. The secure channel cannot

1976

646

IEEE

be used to transmit P itself for reasons of capacity or delay.
For example, the secure channel might be a weekly courier
and the insecure channel a telephone line.
A cryptographic
system is a single parameter family{SKJK~~I(~ of invertible transformations

bits of the plaintext. Block ciphers act in a purely combinatorial fashion on large blocks of text, in such a way thata small change in the input block produces a major change
in the resulting output. This paper deals primarily withblock,ciphers, because this error propagation property isvaluable in many authentication
applications.
In an authentication
system, cryptography is used toguarantee the authenticity of the message to the receiver.
Not only must a meddler be prevented from injecting totally new, authentic looking messages into a channel, but
he must be prevented from creating apparently authentic
messages by combining, or merely repeating, old messages
which he has copied in the past. A cryptographic system
intended to guarantee privacy will not, in general, prevent
this latter form of mischief.
To guarantee the authenticity of a message, informationis added which is a function not only of the message anda secret key, but of the date and time as well; for example,
by attaching the date and time to each message and encrypting the entire sequence. This assures that only
someone who possesses the key can generate a message
which, when decrypted, will contain the proper date andtime. Care must be taken, however, to use a system inwhich small changes in the ciphertext result in largechanges in the deciphered plaintext. This intentional error
propagation ensures that if the deliberate injection of noiseon the channel changes a message such as “erase file 7” intoa different message such as “erase file 8,” it will also corrupt the authentication
information.
The message willthen be rejected as inauthentic.
The first step in assessing the adequacy of cryptographic
systems is to classify the threats to which they are to be
subjected. The following threats may occur to cryptographic systems employed for either privacy or authentication.
A ciphertext only attack is a cryptanalytic
attack inwhich the cryptanalyst possesses only ciphertext.
A known plaintext attack is a cryptanalytic
attack inwhich the cryptanalyst possesses a substantial quantityof corresponding plaintext and ciphertext.
A chosen plaintext attack is a cryptanalytic
attack inwhich the cryptanalyst can submit an unlimited numberof plaintext messages of his own choosing and examine theresulting cryptograms.
In all cases it is assumed that the opponent knows thegeneral system (SK) in use since this information can beobtained by studying a cryptographic device. While manyusers of cryptography attempt to keep their equipment
secret, many commercial applications require not only thatthe general system be public but that it be standard.
A ciphertext only attack occurs frequently in practice.
The cryptanalyst uses only knowledge of the statisticalproperties of the language in use (e.g., in English, the lettere occurs 13 percent of the time) and knowledge of certain“probable” words (e.g., a letter probably begins “DearSir:“). It is the weakest threat to which a system can be
subjected, and any system which succumbs to it is considered totally insecure.

SdPl

-

WI

(1)

from a space (P) of plaintext messages to a space (C) of ciphertext messages. The parameter K is called the key andis selected from a finite set (K) called the keyspace. If themessage spaces (PI and {C) are equal, we will denote themboth by (M). When discussing individual cryptographictransformations
SK, we will sometimes omit mention of
the system and merely refer to the transformationK.
The goal in designing the cryptosystem {SK) is to makethe enciphering and deciphering operations inexpensive,
but to ensure that any successful cryptanalytic operation
is too complex to be economical. There are two approaches
to this problem. A system which is secure due to the computational cost of cryptanalysis, but which would succumb
to an attack with unlimited computation, is called computationallysecure; while a system which can resist any
cryptanalytic
attack, no matter how much computationis allowed, is called unconditionallysecure. Unconditionally secure systems are discussed in [3] and [4] andbelong to that portion of information theory, called the
Shannon theory, which is concerned with optimal performance obtainable with unlimited computation.
Unconditional
security results from the existence ofmultiple meaningful solutions to a cryptogram. For example, the simple substitution cryptogram XMD resulting
from English text can represent the plaintext messages:
now, and, the, etc. A computationallysecure cryptogram,in contrast, contains sufficient information to uniquelydetermine the plaintext and the key. Its security resides
solely in the cost of computing them.
The only unconditionally secure system in common use
is the one time pad, in which the plaintext is combinedwith a randomly chosen key of the same length. While sucha system is provably secure, the large amount of key required makes it impractical for most applications. Except
as otherwise noted, this paper deals with computationallysecure systems since these are more generally applicable.
When we talk about the need to develop provably secure
cryptosystems we exclude those, such as the one time pad,which are unwieldly to use. Rather, we have in mind systems using ‘only’ a few; hundred bits of key and implementable in either a small amount of digital hardware ora few hundred lines of software.
We will call a task computationallyinfeasible if its costas measured by either the amount of memory used or the
runtime is finite but impossibly large.
Much as error correcting codes are divided into convolutional and block codes, cryptographic systems can bedivided into two broad classes: stream ciphers and blockciphers. Stream ciphers process the plaintext in small
chunks (bits or characters), usually producing a pseudorandom sequence of bits which is added modulo 2 to the

TRANSACTIONSONINFORMATIONTHEORY.

NOVEMBER

DIFFIEAND

HELLMAN:NEW

DIRECTIONSINCRYPTOGRAPHY

A system which is secure against a known plaintext attack frees its users from the need to keep their past messages secret, or to paraphrase them prior to declassification. This is an unreasonable burden to place on the system’s users, particularly in commercial situations where
product announcements or press releases may be sent inencrypted form for later public disclosure. Similar situations in diplomatic correspondence have led to the crackingof many supposedly secure systems. While a known
plaintext attack is not always possible, its occurrence isfrequent enough that a system which cannot resist it is notconsidered secure.
A chosen plaintext attack is difficult to achieve inpractice, but can be approximated. For example, submitting a proposal to a competitor may result in his enciphering it for transmission to his headquarters. A cipher
which is secure against a chosen plaintext attack thus frees
its users from concern over whether their opponents canplant messages in their system.
For the purpose of certifying systems as secure, it isappropriate to consider the more formidable cryptanalytic
threats as these not only give more realistic models of theworking environment of a cryptographic system, but makethe assessment of the system’s strength easier. Many systems which are difficult to analyze using a ciphertext onlyattack can be ruled out immediately under known plaintext or chosen plaintext attacks.
As is clear from these definitions, cryptanalysis is asystem identification problem. The known plaintext andchosen plaintext attacks correspond to passive and active
system identification problems, respectively. Unlike many
subjects in which system identification is considered, suchas automatic fault diagnosis, the goal in cryptography is
to build systems which are difficult, rather than easy, toidentify.
The chosen plaintext attack is often called an IFF attack, terminology which descends from its origin in thedevelopment of cryptographic “identification
friend orfoe” systems after World War II. An IFF system enables
military radars to distinguish between friendly and enemy
planes automatically. The radar sends a time-varying
challenge to the airplane which receives the challenge,
encrypts it under the appropriate key,and sends it back to
the radar. By comparing this response with a correctly
encrypted version of the challenge, the radar can recognize
a friendly aircraft. While the aircraft are over enemy territory, enemy cryptanalysts can send challenges and examine the encrypted responses in an attempt to determine
the authentication key in use, thus mounting a chosen
plaintext attack on the system. In practice, this threat iscountered by restricting the form of the challenges, which
need not be unpredictable, but only nonrepeating.
There are other threats to authentication systems whichcannot be treated by conventional cryptography, andwhich require recourse to the new ideas and techniques
introduced in this paper. The threat of compromise of thereceiver’s authentication
data is motivated by the situation in multiuser networks where the receiver is often the647system itself. The receiver’s password tables and otherauthentication data are then more vulnerable to theft thanthose of the transmitter (an individual user). As shown
later, some techniques for protecting against this threatalso protect against the threat of dispute. That is, a message may‘ be sent but later repudiated by either thetransmitter or the receiver. Or, it may be alleged by either
party that a message was sent when in fact none was. Unforgeable digital signatures and receipts are needed. For
example, a dishonest stockbroker might try to cover up
unauthorized buying and selling for personal gain byforging orders from clients, or a client might disclaim anorder actually authorized by him but which he later sees
will cause a loss. W e will introduce concepts which allow
the receiver to verify the authenticity of a message, butprevent him from generating apparently authentic messages, thereby protecting against both the threat of compromise of the receiver’s authentication
data and thethreat of dispute.
III.

PUBLICKEY

CRYPTOGRAPHY

As shown in Fig. 1, cryptography has been a derivative
security measure. Once a secure channel exists along whichkeys can be transmitted, the security can be extended toother channels of higher bandwidth or smaller delay byencrypting the messages sent on them. The effect has been
to limit the use of cryptography to communications amongpeople who have made prior preparation for cryptographic
security.
In order to develop large, secure, telecommunications
systems, this must be changed. A large number of users nresults in an even larger number, (n2 - n)/2 potential pairs
who may wish to communicate privately from all others.
It is unrealistic to assume either that a pair of users withno prior acquaintance will be able to wait for a key to besent by some secure physical means, or that keys for all (n2n)/2 pairs can be arranged in advance. In another paperii the authors have considered a conservative approachrequiring no new development in cryptography itself, but
this involves diminished security, inconvenience, and restriction of the network to a starlike configuration withrespect to initial connection protocol.
W e propose that it is possible to develop systems of thetype shown in Fig. 2, in which two parties communicating
solely over a public channel and using only publicly known
techniques can create a secure connection. W e examine two
approaches to this problem, called public key cryptosys-

Fig. 2.

Flow of informationin public key system.

IEEE

64X

terns and public key distribution
systems, respectively.
The first are more powerful, lending themselves to thesolution of the authentication problems treated in the next
section, while t,he second are much closer to reahzation.
A public key cryptosystem
is a pair of families
K
K
E
JRJ
of
algorithms
representing
PKIK E (KI and ID 1
invertible transformations,
I&:(Mj-+ {M)(2)

D[(:(M) ---*’{M)(3)on a finite message space (MJ, such that

1) for every K E {Kb EK is the inverse of DK,2) for every K E {KJ and M E (MI, the algorithms EK
and DK are easy to compute,3) for almost every K E (KJ, each easily computed algorithm equivalent to Df( is computationallyinfeasible to derive from EK,4) for every K E {K), it is feasible to compute inverse
pairs EK and DK from K.
Because of the third property, a user’s enciphering key
EK can be made public without compromising the securityof his secret deciphering key DK. The cryptographic system is therefore split into two parts, a family of encipheringtransformations
and a family of deciphering transformations in such a way that, given a member of one family, it
is infeasible to find the corresponding member of theother.
The fourth property guarantees that there is a feasible
way of computing corresponding pairs of inverse transformations when no constraint is placed on what either theenciphering or deciphering transformation
is to be. In
practice, the cryptoequipment must contain a true random
number generator (e.g., a noisy diode) for generat,ing K,
together with an algorithm for generating the EK ~- n,pair from its outputs.
Given a system of this kind, the problem of key distribution is vastly simplified. Each user generates a pair of
inverse transformations,
E and D, at his terminal. The
deciphering transforrnation
D must be kept secret, butneed never be communicated on any channel. The enciphering key E can be made public by placing it in a public
directory along with the user’s name and address. Anyone
can then encrypt messages and send them to the user, but
no one else can decipher messages inbended for him. Publickey cryptosystems can thus be regarded as multiple accessciphers.
It is crucial that the public file of enciphering keys beprotected from unauthorized modification.
This task ismade easier by the public nature of the file. Read prot,ection is unnecessary and, since the file is modified infrequently, elaborate write protection mechanisms can be
economically employed.
A suggestive, although unfortunate!.y useless, example
of a public key cryptosystem is to encipher the plaintext,
represented as a binary n-vector m, by multiplying it by
an invertible binary n X n matrix E. The cryptogram thus

TRANSACTJONSONINFORMATIONTHEORY,NOVEMBER

1976

equals Em. Letting B = Em l we have m - DC. Thus, both
enciphering and deciphering require about n2 operations.
Calculation of D from E, however, involves a matrix inversion which is a harder problem. And it is at least conceptually simpler to obtain an arbitrary pair of inverse
matrices than it is to invert a given mabrix, St.art with theidentity matrix I and do elementary row and column operations to obtain an arbitrary invertible matrix E. Then
starting with I do the inverses of these same elementary
operations in reverse order to obtain 61 - E--l. The sequence of elementary operations could be easi1.y determined from a random bit string.
Unfortunately,
matrix inversion takes only a.bout n3
operations.
The ratio of “cryptanalytic”
time (i.e., computing D from E) to enciphering or deciphering t,ime isthus at most n, and enormous block sizes would be required to obtain ratios of 3 O6 or greater. Also, it does notappear that knowledge of the element,ary operat.ions used
to obtain E from I greatly reduces the time for computing
D. And, since there is no round-off error in binary arithmetic, numerical stability is unimportantin the matrix
inversion. In spite of its lack of practicaleutility, this matrix
example is still useful for clarifying the relationships
necessary in a public key cryptosystem.
A more practical approach to finding a pair of easily
computed inverse algorithms E and D; such that, D is hardto infer from E, makes use of the difficulty of analyzing
programs in low level languages. Anyone who has tried todetermine what operation is accomplished by someone
else’s machine language program knows that E itself (i.e.,
what E does) can be hard to infer from an algorithm for E.
If the program were to be made purposefully confusing
through addition of umleeded variables and statements,
then determining an inverse algorithm could be made very
difficult. Of course, E must be complicated enough toprevent its identificationfrom input-output
pairs.
Essentially what is required is a one-way compiler: one
which takes an easily understood program writ,ten in a h.igh
level language and translates it into an incomprehensible
program in some machine language. The compiler is one-.
way because it must be feasible to do the compila.tion, but
infeasible to reverse the process. Since efficiency in size ofprogram and run time are not crucial in this application,such compilers may be possible if the struct,ure of themachine language can be optimized to assist in the confusion.
Merkle [I] has independently studied the problem of
distributiug keys over an insecure channel. His approachis different from that of the public key cryptosystems
suggested above, and will be termed a public key distribution system. The goal is for two .users, A and B, to securely exchange a key over an insecure charmel. This key
is then used by both users in a normal cryptosystemforboth enciphering and deciphering. Merkle bas a solu.tion
whose crypt,analytic cost grows as n,2 where n is the cost to
the legitimate users. Unfortunately
the cost to the legitimate users of the system is as much in transmission time
as in computation, because Merkle’s protocol requires n

DIFFIE

AND

IIELLMAN:NEWDIRECTIONS

IN

649

CRYPTOGRAPHY

potential keys to be transmitted before orie key can bedecided on. Merkle not.es that this high transmission
overhead prevents the system from being very useful inpractice. If a one megabit limit is placed on the setup
protocol’s overhead, his technique can achieve cost ratios
of approximately 10 000 to 1, which are too small for mostapplications. If inexpensive, high bandwidth data links
become available, ratios of a million to one or greater could
be achieved and the system would be of substantial practical value.
W e now suggest a new public key distribution system
which has several advantages. First, it requires only one“key” to be exchanged. Second, the cryptanalytic effort
appears 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 serves to authenticate user A to user B
and vice versa. By making the public file essentially a read
only memory, one personal appearance allows a user toauthenticate his identity many times to many users.
Merkle’s technique requires A and B to verify each other’s
identities through other means.
The new technique makes use of the apparent difficultyof computing logarithms over a finite field GF(q) with aprime number q of elements. Let
Y = crx mod q1

forl_<XIq-1,(4)

where 01is a fixed primit,ive element of GE’(q), then X isreferred to as the logarithm of Y to the base 01,mod q:
X = log, Y mod q,forl<YIq-1.

Computing X from Y, on the other hand can be much moredifficult and, for certain carefully chosen values of q, requires on the order of qlk operations, using the best known
algorithm [7, pp. 9, 575-5761, [$I.
The security of our technique depends crucially on the
difficulty of computing logarithms mod q, and if an algorithm whose complexity grew as logzq were to be found, oursyst.em would be broken. While the simplicity of the
problem statement might allow such simple algorithms,
it might instead allow a proof of the problem’s difficulty.
For now we assume that the best known algorithm forcomputing logs mod q is in fact close to optimal and hence
that q1/2 is a good measure of the problem’s complexity,
for a properly chosen q.
Each user generates an independent random number
Xi chosen uniformly from the set of integers {1,2, . . . ,q 1). Each keeps Xi secret, but places(7)

in a public file with his name and address. When users iand j wish t,o communicate privately, they use
Kij = 01~1x~ mod (1Y, from the

Kij z yj”[ mod q(9)= (a”/)Xl(10);: ,x-!x,

Inod qz NX,X lmodq.

(11)

User j obtains Kij in the similar fashion
Kij = Yx/ mod 4.

(12)Another user must compute Kij from Yi and Yj, for example, by computing
Kjj z ~~iyil~~cvY~)
mod q,(13)

W e thus see that if logs mod q are easily computed thesystem 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 difficult to compute), neither do we see any way
to compute Kij from Yi and Yj without first obtaining either Xi or Xi.
If q is a prime slightly less than 26, then all quantities
are representable as b bit numbers. Exponentiation thentakes at most 2b multiplications mod q, while by hypothesis taking logs requires q112 = 2b/2 operations. The
cryptanalytic effort therefore grows exponentially relative
to legitimate efforts. If b = 200, then at most 400 multiplications are required to compute Yi from Xi, or Kij fromYi and Xj, yet taking logs mod q requires 21°0 or approximately lO”O operations.

(5)

Calculation of Y from X is easy, taking at most 2 X log2 q
multiplications[6, pp. 398-4221. For example, for X =1%
y = ,I8 = (((u.“)2)“)2 x *2.
(6)

Yi =z a *ysrjlod q

as their key. .User i obtains Kij by obtaining
public file and letting(8)

The problem of authenCication is perhaps an even more
serious barrier to the universal adoption of telecomrnunications for business t,ransactions than the problem of key
distribution. Authentication is at the heart of any system
involving contracts and billing. W ithout it, business cannot
function. Current electronic authentication systems cannot
meet the need for a purely digital, unforgeable, message
dependent signature. They provide protection against
third party forgeries, but do not protect against disputes
between transmitter and receiver.
In order to develop a system capable of replacing thecurrent written contract with some purely electronic formof communication, we must discover a digital phenomenon
with the same properties as a written signature. It must be
easy for anyone to recognize the signature as authentic, but
impossible for anyone other than the legitimate signer toproduce it. W e will call any such technique one-way authentication. Since any digital signal can be copied precisely, a true digit,al signature must be recognizable without
being known.
Consider the “login” problem in a multiuser computer
system. When setting up his account, the user chooses a
password which is entered into the system’s password directory. Each time he logs in, the user is again asked toprovide his password. By keeping this password secretfrom all other users, forged logins are prevented. This,

1976

650

IEEE

however, makes it vital to preserve the security of thepassword directory since the information it contains would
allow perfect impersonation of any user. The problem isfurther compounded if system operators have legitimate
reasons for accessing the directory. Allowing such legitimate accesses, but preventing all others, is next to impossible.
This leads to the apparently impossible requirement for
a new login procedure capable of judging the authenticity
of passwords without actually knowing them. While appearing to be a logical impossibility, this proposal is easily
satisfied. When the user first enters his password PW, thecomputer automaticallyand transparently
computes afunction f(PW) and stores this, not PW, in the password
directory. At each successive login, the computer calculatesf(X), where X is the proffered password, and comparesf(X) with the st ored value f (P W). If and only if they ‘areequal, the user is accepted as being authentic. Since thefunction f must be calculated once per login, its computation time must be small. A million instructions (costing
approximately$0.10 at bicentennial prices) seems to bea reasonable limit on this computation. If we could ensure,
however, that calculation of f-l required 1030 or more instructions, someone who had subverted the system to obtain the password directory could not in practice obtain
PW from f(PW), and could thus not perform an unauthorized login. Note that f(PW) is not accepted as a password by the login program since it will automaticallycompute f (f(PW)) which will not match the entry f(PW)
in the password directory.
We assume that the function f is public information, sothat it is not ignorance off which makes calculation of f-ldifficult. Such functions are called one-way functions andwere first employed for use in login procedures by R. M.
Needham [9, p. 911. They are also discussed in two recent
papers [lo], [ll] which suggest interesting approaches tothe design of one-way functions.
More precisely, a function f is a one-way function if, for
any argument x in the domain off, it is easy to compute thecorresponding value f(x), yet, for almost all y in the range
off, it is computationallyinfeasible to solve the equationy = f(x) for any suitable argument x.
It is important to note that we are defining a function
which is not invertible from a computational point of view,
but whose noninvertibility
is entirely different from that
normally encountered in mathematics. A function f isnormally called “noninvertible” when the inverse of a point
y is not unique, (i.e., there exist distinct points 3~1and x2
such that f(xi) = y = f (x2)). We emphasize that this is not
the sort of inversion difficulty that is required. Rather, it
must be overwhelmingly
difficult, given a value y andknowledge of f, to calculate any x whatsoever with theproperty that f (3c) = y. Indeed, if f is noninvertible in theusual sense, it may make the task of finding an inverse
image easier. In the extreme, if f(x) = yc for all x: in thedomain, then the range off is (yc), and we can take any x
as f-l(yo). It is therefore necessary that f not be too degenerate. A small degree of degeneracy is tolerable and, as

discussed later, is probably present in the most promisingclass of one-way functions.
Polynomials offer an elementary example of one-way
functions. It is much harder to find a root xe of the polynomial equation p (3~) = y than it is to evaluate the polynomial p(x) at x = x0. Purdy [l l] has suggested the use ofsparse polynomials of very high degree over finite fields,
which appear to have very high ratios of solution to evaluation time. The theoretical basis for one-way functions
is discussed at greater length in Section VI. And, as shownin Section V, one-way functions are easy to devise inpractice.
The one-way function login protocol solves only someof the problems arising in a multiuser system. It protects
against compromise of the system’s authenticationdatawhen it is not in use, but still requires the user to send thetrue password to the system. Protection against eavesdropping must be provided by additional encryption, andprotection against the threat of dispute is absent altogether.
A public key cryptosystem can be used to produce a true
one-way authentication system as follows. If user A wishes
to send a message M to user B, he “deciphers” it in his
secret deciphering key and sends DA(M). When user B
receives it, he can read it, and be assured of its authenticity
by “enciphering” it with user A’s public enciphering key
EA. B also saves DA(M) as proof that the message camefrom A. Anyone can check this claim by operating on
DA(M) with the publicly known operation EA to recover
M. Since only A could have generated a message with thisproperty, the solution to the one-way authentication
problem would follow immediately from the developmentof public key cryptosystems.
One-way message authentication has a partial solution
suggested to the authors by Leslie Lamport of Massachusetts Computer Associates. This technique employs aone-way function f mapping k-dimensional binary space
into itself for h on the order of 100. If the transmitter
wishes to send an N bit message he generates 2N, randomly
chosen,k-dimensional
binaryvectors,XN,XN
which
he
keeps
secret.
The
rex1,x1,x2,x2,* * *ceiver is given the corresponding images under f, namely
Y 1, Yl,Y 2, yz, * * * ,YN,YN. Later, when the message m =sends xi or(1721+2,* - - ,mN) is to be sent, the transmitter
Xi depending on whether ml = 0 or 1. He sends x2 or X2
depending on whether m2 = 0 or 1, etc. The receiver operates with f on the first received block and sees whether
it yields yi or Yi as its image and thus learns whether it was
3~1or X1, and whether ml = 0 or 1. In a similar manner thereceiver is able to determine m2,m3, . . . ,mN. But the receiver is incapable of forging a change in even one bit of

TRANSACTIONSONINFORMATIONTHEORY,NOVEMBERm.

This is only a partial solution because of the approximately lOO-fold data expansion required. There is, however, a modification
which eliminates the expansion
problem when N is roughly a megabit or more. Let g be aone-way mapping from binary N-space to binary n-space
where n is approximately 50. Take the N bit message m

DIFFIEAND

HELLMAN:NEW

DIRECTIONS

IN

651

CRYPTOGRAPHY

and operate on it with g to obtain the n bit vector m’. Then
use the previous scheme to send m’. If iV = 106, n = 50, andk = 100, this adds kn = 5000 authentication bits to themessage. It thus entails only a 5 percent data expansion
during transmission (or 15 percent if the initial exchange
OfYl,Yl,-*- ,YN,YN is included). Even though there area large number of other messages (2N-n on the average)
with the same authentication sequence, the one-waynessof g makes them computationally infeasible to find andthus to forge. Actually g must be somewhat stronger thana normal one-way function, since an opponent has not only
m’ but also one of its inverse images m. It must be hardeven given m to find a different inverse image of m’.
Finding such functions appears to offer little trouble (seeSection V).
There is another partial solution to the one-way user
authentication problem. The user generates a password
X which he keeps secret. He gives the systemfT(X), where
f is a one-way function. At time t the appropriate authenticator is f T-t(X), which can be checked by the system by applying ft(X). Because of the one-wayness off,
past responses are of no value in forging a new response.
The problem with this solution is that it can require a fairamount of computation for legitimate login (althoughmany orders of magnitude less than for forgery). If forexample t is incremented every second and the system
must work for one month on each password then T = 2.6
million. Both the user and the system must then iterate f
an average of 1.3 million times per login. While not insurmountable, this problem obviously limits use of the technique. The problem could be overcome if a simple method
for calculating f c2tn), for n = 1,2, . . . could be found, muchas X8 = ((X2)2)2. For then binary decompositions of T t and t would allow rapid computation off T-t and ft. It
may be, however, that rapid computation of fn precludes
f from being one-way.
V. PROBLEMINTERRELATIONSANDTRAPDOORSIn this section, we will show that some of the cryptographic problems presented thus far can be reduced toothers, thereby defining a loose ordering according todifficulty. W e also introduce the more difficult problemof trap doors.
In Section II we showed that a cryptographic system
intended for privacy can also be used to provide authentication against third party forgeries. Such a system canbe used to create other cryptographic objects, as well.
A cryptosystem which is secure against a known
plaintext attack can be used to produce a one-way function.
As indicated in Fig. 3, take the cryptosystem (SK:(P) {C]}K,(Kf which is secure against a known plaintext attack,fix P = PO and consider the map

CIPHERTEXT
Y-f(x)

Fig. 3.

Secure cryptosystem used as one-way function.

defined byf(X) = SxPd.

(15)This function is one-way because solving for X given f(X)is equivalent to the cryptanalytic problem of finding the
key from a single known plaintext-cryptogram pair. Publicknowledge off is now equivalent to public knowledge of(SK] and PO.
While the converse of this result is not necessarily true,
it is possible for a function originally found in the searchfor one-way functions to yield a good cryptosystem. Thisactually happened with the discrete exponential function
discussed in Section III [8].
One-way functions are basic to both block ciphers andkey generators. A key generator is a pseudorandom bit
generator whose output, the keystream, is added modulo
2 to a message represented in binary form, in imitation ofa one-time pad. The key is used as a “seed” which determines the pseudorandom keystream sequence. A known
plaintext attack thus reduces to the problem of determining the key from the keystream. For the system to be
secure, computation of the key from the keystream must
be computationally infeasible. While, for the system to beusable, calculation of the keystream from the key must be
computationally simple. Thus a good key generator is, almost by definition, a one-way function.
Use of either type of cryptosystem as a one way function
suffers from a minor problem. As noted earlier, if thefunction f is not uniquely invertible, it is not necessary (orpossible) to find the actual value of X used. Rather any X
with the same image will suffice. And, while each mapping
SK in a cryptosystem must be bijective , there is no such
restriction on the function 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
chosen uniformly from all possible Y, and successive
choices are independent). In this case, if X is chosen uniformly and there are an equal number of keys and messages (X and Y), then the probability that the resultant
Y has k + 1 inverses is approximately e-l/k! for k =0123
7 , , f . . . . This is a Poisson distribution with mean X =1, shifted by 1 unit. The expected number of inverses isthus only 2. While it is possible for f to be more degenerate,
a good cryptosystem will not be too degenerate since then
the key is not being well used. In the worst case, if f (X) =Yc for some Yc, we have S,(P,) = Cc, and encipherment
of PO would not depend’on the key at all!

652

IEEE

While we are usually interested in functions whose domain and range are of comparable size, there are exceptions. In the previous section we required a one-way
function mapping long strings onto much shorter ones. By
using a block cipher whose key length is larger than theblocksize, such functions can be obtained using the above
technique.
Evans et al. [lo] have a different approach to the problem of constructing a one-way function from a block cipher.
Rather than selecting a fixed Pa as the input, they use thefunctionf(X) = SXLQ.

(16)This is an attractive approach because equations of thisform are generally difficult to solve, even when the family
S is comparatively simple. This added complexity, however, destroys the equivalence between the security of thesystem S under a known plaintext attack and the onewayness off.
Another relationship has already been shown in Section
IV.
A public key cryptosystem can be used to generate aone-way authentication
system.
The converse does not appear to hold, making the construction of a public key cryptosystem a strictly moredifficult problem than one-way authentication. Similarly,
a public key cryptosystem can be used as a public key
distribution system, but not conversely.
Since in a public key cryptosystem the general system
in which E and D are used must be public, specifying E
specifies a complete algorithm for transforming
input
messages into output cryptograms. As such a public key
system is really a set of trap-door one-way functions,
These are functions which are not really one-way in that
simply computed inverses exist. But given an algorithm
for the forward function it is computationallyinfeasible
to find a simply computed inverse. Only through knowledge of certain trap-door information(e.g., the random
bit string which produced the E-D pair) can one easily findthe easily computed inverse.
Trap doors have already been seen in the previous
paragraph in the form of trap-door one-way functions, butother variations exist. A trap-door cipher is one whichstrongly resists cryptanalysis by anyone not in possessionof trap-door information used in the design of the cipher.
This allows the designer to break the system after he has
sold it to a client and yet falsely to maintain his reputation
as a builder of secure systems. It is important to note that
it is not greater cleverness or knowledge of cryptography
which allows the designer to do what others cannot. If hewere to lose the trap-door information he would be no
better off than anyone else. The situation is precisely
analogous to a combination lock. Anyone who knows the
combination
can do in seconds what even a skilledlocksmith would require hours to accomplish. And yet, if
he forgets the combination, he has no advantage.
A trap-door cryptosystem can be used to produce
public key distribution system.

a

TRANSACTIONSONINFORMATIONTHEORY,NOVEMBER

1976

For A and B to establish a common private key, A
chooses a key at random and sends an arbitrary plaintext-cryptogram
pair to B. B, who made the trap-door cipher public, but kept the trap-door information secret,uses the plaintext-cryptogram
pair to solve for the key. A
and B now have a key in common.
There is currently little evidence for the existence of
trap-door ciphers. However they are a distinct possibility
and should be remembered when accepting a cryptosystemfrom a possible opponent [12].
By definition, we will require that a trap-door problem
be one in which it is computationally feasible to devise thetrap door. This leaves room for yet a third type of entity
for which we shall use the prefix “quasi.” For example aquasi one-way function is not one-way in that an easily
computed inverse exists. However, it is computationallyinfeasible everrfor the designer, to find the easily computed
inverse. Therefore a quasi one-way function can be usedin place of a one-way function with essentially no loss insecurity.
Losing the trap-door information to a trap-door one-way
function makes it into a quasi one-way function, but there
may also be one-way functions not obtainable in thismanner.
It is entirely a matter of definition that quasi one-way
functions are excluded from the class of one-way functions.
One could instead talk of one-way functions in the wide
sense or in the strict sense.
Similarly, a quasi secure cipher is a cipher which will
successfully resist cryptanalysis, even by its designer, andyet for which there exists a computationallyefficientcryptanalytic algorithm (which is of course computationally infeasible to find). Again, from a practical point ofview, there is essentially no difference between a secure
cipher and a quasi secure one.
We have already seen that public key cryptosystems
imply the existence of trap-door one-way functions.
However the converse is not true. For a trap-door one-way
function to be usable as a public key cryptosystem, it must
be invertible (i.e., have a unique inverse.)
VI. COMPUTATIONALCOMPLEXITY
Cryptography differs from all other fields of endeavor
in the ease with which its requirements may appear to besatisfied. Simple transformations will convert a legible text
into an apparently meaningless jumble. The critic, whowishes to claim that meaning might yet be recovered by
cryptanalysis, is then faced with an arduous demonstration
if he is to prove his point of view correct. Experience has
shown, however, that few systems can resist the concerted
attack of skillful cryptanalysts, and many supposedly secure systems have subsequently been broken.
In consequence of this, judging the worth of new systems
has always been a central concern of cryptographers.
During the sixteenth and seventeenth centuries, mathematical arguments were often invoked to argue thestrength of cryptographic
methods, usually relying on
counting methods which showed the astronomical number

DIFFIEAND

HELLMAN:NEW

DIRECTIONSINCRYPTOGRAPHY

of possible keys. Though the problem is far too difficult tobe laid to rest by such simple methods, even the noted algebraist Cardano fell into this trap [2, p. 1451. As systems
whose strength had been so argued were repeatedly broken, the notion of giving mathematical proofs for the security of systems fell into disrepute and was replaced bycertification via crypanalytic assault.
During this century, however, the pendulum has begun
to swing back in the other direction. In a paper intimately
connected with the birth of information theory, Shannon[3] showed that the one time pad system, which had beenin use since the late twenties offered “perfect secrecy” (aform of unconditional security). The provably securesystems investigated by Shannon rely on the use of either
a key whose length grows linearly with the length of themessage or on perfect source coding and are therefore too
unwieldy for most purposes. W e note that neither publickey cryptosystems nor one-way authentication systems canbe unconditionally secure because the public information
always determines the secret information uniquely among
the members of a finite set. W ith unlimited computation,
the problem could therefore be solved by a straightforward
search.
The past decade has seen the rise of two closely related
disciplines devoted to the study of the costs of computation: computational complexity theory and the analysis ofalgorithms. The former has classified known problems incomputing into broad classes by difficulty, while the latterhas concentrated on finding better algorithms andstudying the resources they consume. After a brief digression into complexity theory, we will examine its application to cryptography, particularly the analysis of
one-way functions.
A function is said to belong to the complexity class P (forpolynomial) if it can be computed by a deterministic
Turing Machine in a time which is bounded above by somepolynomial function of the length of its input. One might
think of this as the class of easily computed functions, but
it is more accurate to say that a function not in this classmust be hard to compute for at least some inputs. There
are problems which are known not to be in the class P [13,pp. 405-4251.
There are many problems which arise in engineering
which cannot be solved in polynomial time by any known
techniques, unless they are run on a computer with anunlimited degree of parallelism. These problems may or
may not belong to the class P, but belong to the class NP(for nondeterministic, polynomial) of problems solvablein polynomial time on a “nondeterministic” computer (i.e.,
one with an unlimited degree of parallelism). Clearly theclass NP includes the class P, and one of the great open
questions in complexity theory is whether the class NPisstrictly larger.
Among the problems known to be solvable in NP time,
but not known to be solvable in P time, are versions of thetraveling salesman problem, the satisfiability problem for
propositional calculus, the knapsack problem, the graphcoloring problem, and many scheduling and minimization
problems [13, pp. 363-4041, [14]. W e see that it is not lack653
of interest or effort which has prevented people fromfinding solutions in P time for these problems. It is thus
strongly believed that at least one of these problems mustnot be in the class P, and that therefore the class NP isstrictly larger.
Karp has identified a subclass of the NP problems,
called NP complete, with the property that if any one ofthem is in P, then all NPproblems are in P. Karp lists 21
problems which are NP complete, including all of the
problems mentioned above [14].
While the NP complete problems show promise forcryptographic use, current understanding of their difficulty includes only worst case analysis. For cryptographic
purposes, typical computational costs must be considered.
If, however, we replace worst case computation time withaverage or typical computation time as our complexity
measure, the current proofs of the equivalences among the
NPcomplete problems are no longer valid. This suggests
several interesting topics for research. The ensemble andtypicality concepts familiar to information theorists havean obvious role to play.
W e can now identify the position of the general
cryptanalytic problem among all computational problems.
The cryptanalytic
difficultyof a system whose encryption and decryption operations can be done in P timecannot be greater than NP.
To see this, observe that any cryptanalytic problem canbe solved by finding a key, inverse image, etc., chosen froma finite set. Choose the key nondeterministically and verify
in Ptime that it is the correct one. If there are M possible
keys to choose from, an M-fold parallelism must be employed. For example in a known plaintext attack, theplaintext is encrypted simultaneously under each of thekeys and compared with the cryptogram. Since, by assumption, encryption takes only P time, the cryptanalysis
takes only NP time.
W e also observe that the general cryptanalytic problem
is NP complete. This follows from the breadth of ourdefinition of cryptographic problems. A one-way function
with an NP complete inverse will be discussed next.
Cryptography can draw directly from the theory of NP
complexity by examining the way in which NY complete
problems can be adapted to cryptographic use. In particular, there is an NP complete problem known as the
knapsack problem which lends itself readily to the construction of a one-way function.
Let y = f(x) = a . x where a is a known vector of n intergers (al,az, . -. ,a,) and x is a binary n-vector. Calculation of y is simple, involving a sum of at most n integers.
The problem of inverting f is known as the knapsackproblem and requires finding a subset of the (ai) which sum
toy.
Exhaustive search of all 2n subsets grows exponentiallyand is computationally infeasible for n greater than 100
or so. Care must be exercised, however, in selecting theparameters of the problem to ensure that shortcuts are notpossible. For example if n = 100 and each ai is 32 bits long,y is at most 39 bits long, and f is highly degenerate; re-

IEEE

654

quiring on the average only 238 tries to find a solution.
Somewhat more trivially, if ai = 2i-1 then inverting f isequivalent to finding the binary decomposition of y.
This example demonstrates both the great promise andthe considerable shortcomings of contemporary
complexity theory. The theory only tells us that the knapsackproblem is probably difficult in the worst case. There is no
indication of its difficulty for any particular array. It appears, however, that choosing the {ai) uniformly from
{O,i,Z, * - - ,2n-l] results in a hard problem with probability
oneasn-m.
Another potential one-way function, of interest in theanalysis of algorithms, is exponentiation mod q, which was
suggested to the authors by Prof. John Gill of Stanford
University. The one-wayness of this functions has alreadybeen discussed in Section III.
VII.

HISTORICALPERSPECTIVE

While at first the public key systems and one-way authentication systems suggested in this paper appear to beunportended by past cryptographic
developments, it ispossible to view them as the natural outgrowth of trends
in cryptography stretching back hundreds of years.
Secrecy is at the heart of cryptography. In early cryptography, however, there was a confusion about what was
to be kept secret. Cryptosystems such as the Caesar cipher(in which each letter is replaced by the one three places
further on, so A is carried to D, B to E, etc.) depended fortheir security on keeping the entire encryption processsecret. After the invention of the telegraph [2, p. 1911, thedistinction between a general system and a specific key
allowed the general system to be compromised, for example by theft of a cryptographic device, without compromising future messages enciphered in new keys. This principle was codified by Kerchoffs [2, p. 2351 who wrote in1881 that the compromise of a cryptographic
systemshould cause no inconvenience to the correspondents.
About 1960, cryptosystems were put into service whichwere deemed strong enough to resist a known plaintext
cryptanalytic
attack, thereby eliminating the burden of
keeping old messages secret. Each of these developments
decreased the portion of the system which had to be protected from public knowledge, eliminating such tedious
expedients as paraphrasing diplomatic dispatches before
they were presented. Public key systems are a naturalcontinuation of this trend toward decreasing secrecy.
Prior to this century, cryptographic systems were limited
to calculations which could be carried out by hand or withsimple slide-rule-likedevices. The period immediately
after World War I saw the beginning of a revolutionary
trend which is now coming to fruition. Special purpose
machines were developed for enciphering. Until the development of general purpose digital hardware, however,cryptography was limited to operations which could be
performed with simple electromechanicalsystems. The
development of digital computers has freed it from thelimitations of computing with gears and has allowed thesearch for better encryption methods according to purely
cryptographic criteria.

TRANSACTIONSONINFORMATIONTHEORY,NOVEMBER

1976

The failure of numerous attempts to demonstrate thesoundness of cryptographic systems by mathematical proof
led to the paradigm of certification by cryptanalytic attack
set down by Kerchoffs [2, p. 2341 in the last century. Although some general rules have been developed, which aid
the designer in avoiding obvious weaknesses, the ultimate
test is an assault on the system by skilled cryptanalysts
under the most favorable conditions (e.g., a chosen plaintext attack). The development of computers has led for the
first time to a mathematical theory of algorithms which canbegin to approach the difficult problem of estimating thecomputationaldifficultyof breaking a cryptographic
system. The position of mathematical proof may thus comefull circle and be reestablished as the best method of certification.
The last characteristic which we note in the history ofcryptography is the division between amateur and professional cryptographers. Skill in production cryptanalysis
has always been heavily on the side of the professionals,
but innovation, particularly in the design of new types ofcryptographic systems, has come primarily from the amateurs. Thomas Jefferson, a cryptographic amateur, invented a system which was still in use in World War II [2,pp. 192-1951, while the most noted cryptographic systemof the twentieth century, the rotor machine, was invented
simultaneously by four separate people, all amateurs [2,pp. 415,420,422-4241. We hope this will inspire others towork in this fascinating area in which participationhas
been discouraged in the recent past by a nearly total government monopoly.

REFERENCES[I] R. Merkle, “Secure communication
over an insecure channel,”submitted to Communications of the ACM.
[2] D. Kahn, The Codebreakers, The Story of Secret Writing.
New
York: Macmillan, 1967.
[3] C. E. Shannon, “Communication
theory of secrecy systems,” Bell
Syst. Tech. J., vol. 28, pp. 656-715, Oct. 1949.
[4] M. E. Hellman, “An extension of the Shannon theory approach to
cryptography,” submitted to IEEE Trans. Inform. Theory, Sept.
1975.
[5] W. Diffie and M. E. Hellman, “Multiuser cryptographic techniques,”
presented at National Computer Conference, New York, June 7-10,
1976.
[6] D. Knuth, The Art of Computer Programming,Vol. 2, SemiNumerical Algorithms.
Reading, MA.: Addison-Wesley, 1969.
[7] --,The Art of Computer Programming, Vol. 3, Sorting and
Searching.
Reading, MA.: Addison-Wesley, 1973.
[S] S. Pohlig and M. E. Hellman, “An improved algorithm for computing algorithms in GF(p) and its cryptographic significance,”
submitted to IEEE Trans. Inform. Theorv.
[9] M. V. Wilkes, Time-Sharing Computer Systems. New York: Elsevier, 1972.
[lo] A. Evans, Jr., W. Kantrowitz, and E. Weiss, “A user authentication
system not requiring secrecy in the computer,” Communicationsof the ACM, vol. 17, pp. 437-442, Aug. 1974.
1111G. B. Purdy, “A high security log-in procedure,” Communicationsof the ACM, vol. 17, pp. 442-445, Aug. 1974.
1121W. Diffie and M. E. Hellman, “Cryptanalysis of the NBS data encryption standard” submitted to Computer, May 1976.
[I31 A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design andAnalysis of Computer Algorithms.
Reading, MA.: AddisonWesley, 1974.
among combinatorial problems,” in[I41 R. M, Karp, “Reducibility
Complexity of Computer Computations.
R. E. Miller and J. W.
Thatcher, Eds. New York: Plenum, 1972, pp. 855104.