644
`
`IEEE
`
`TRANSACTIONS
`
`ON
`
`INFORMATION
`
`THEORY,
`
`VOL.
`
`IT-22,
`
`NO. 6, NOVEMBER
`
`1976
`
`in Cryptography
`New Directions
`Invited Paper
`
`WHITFIELD
`
`DIFFIE
`
`AND MARTIN
`
`E. HELLMAN,
`
`MEMBER,
`
`IEEE
`
`in cryp-
`developments
`kinds of contemporary
`Abstract-Two
`tography
`are examined. Widening
`applications
`of teleprocessing
`have given
`rise to a need for new
`types of cryptographic
`systems,
`which minimize
`the need for secure key distribution
`channels and
`supply
`the equivalent
`of a written
`signature.
`This paper suggests
`ways to solve these currently
`open problems.
`It also discusses how
`the theories
`of communication
`and computation
`are beginning
`to
`provide
`the
`tools
`to solve cryptographic
`problems
`of long stand-
`ing.
`
`I.
`
`INTRODUCTION
`
`W E STAND TODAY on the brink of a revolution
`
`in
`of cheap digital
`The development
`cryptography.
`hardware has freed it from
`the design limitations
`of me-
`chanical computing
`and brought
`the cost of high grade
`cryptographic
`devices down to where they can be used in
`such 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 the
`same time, theoretical developments
`in information
`theory
`and computer science show promise of providing provably
`secure cryptosystems,
`changing
`this ancient art
`into a
`science.
`communica-
`of computer controlled
`The development
`tion networks pron$ses effortless and inexpensive contact
`between people or computers
`on opposite sides of the
`world,
`replacing most mail and many excursions with
`telecommunications.
`For many applications
`these contacts
`must be made secure against both eavesdropping.and
`the
`injection of illegitimate messages. At present, however, the
`solution of security problems
`lags well behind other areas
`of communications
`technology.
`Contemporary
`cryp-
`tography
`is unable to meet the requirements,
`in that its use
`would
`impose such severe inconveniences
`on the system
`users, as to eliminate many of the benefits of teleprocess-
`ing.
`
`received June 3,1976. This work was partially supported
`Manuscript
`by 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.
`of Electrical Engineering, Stanford
`is with the Department
`W. Diffie
`Universitv. Stanford. CA. and the St,anford Artificial
`IntelliPence Lab-
`Y
`oratory, g&ford,
`CIk 94.505.
`M. E. Hellman
`is with
`the Department
`of Electrical Engineering,
`Stanford University, Stanford, CA 94305.
`
`is that of pri-
`problem
`The best known cryptographic
`extraction of informa-
`vacy: preventing
`the unauthorized
`tion
`from communications
`over an insecure channel.
`In
`order to use cryptography
`to insure privacy, however,
`it is
`currently necessary for the communicating
`parties to share
`a key which
`is known
`to no one else. This is done by send-
`ing the key in advance over some secure channel such as
`private courier or registered mail. A private conversation
`between
`two people with no prior acquaintance-is
`a com-
`mon occurrence
`in business, however, and it is unrealistic
`to expect
`initial business contacts
`to be postponed
`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
`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 a
`public key cryptosystem
`enciphering and deciphering are
`governed by distinct keys, E and D, such that computing
`D from E is computationally
`infeasible
`(e.g., requiring
`lOloo instructions).
`The enciphering
`key E can thus be
`publicly disclosed without compromising
`the deciphering
`key D. Each user of the network can, therefore, place his
`enciphering key in a public directory. This enables any user
`of the system
`to send a message to any other user enci-
`phered in such a way that only the intended
`receiver is able
`to decipher
`it. As such, a public key cryptosystem
`is a
`multiple
`access cipher. A private conversation
`can there-
`fore be held between any two
`individuals
`regardless of
`whether
`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 re-
`ceives using his own secret deciphering
`key.
`We propose some techniques
`for developing public key
`cryptosystems,
`but the problem
`is still
`largely open.
`ap-
`Public key distribution
`systems offer a different
`proach 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 ex-
`change must find it computationally
`infeasible
`to compute
`the key from
`the information
`overheard, A possible solu-
`tion
`to the public key distribution
`problem
`is given
`in
`Section
`III, and Merkle
`[l] has a partial solution of a dif-
`ferent
`form.
`solution,
`to cryptographic
`A second problem, amenable
`which stands in the way of replacing contemporary
`busi-
`
`.
`
`BlackBerry Corporation Exhibit 1019, pg. 1
`
`

`

`DIFFIE
`
`AND
`
`HELLMAN:
`
`NEW
`
`DIRECTIONS
`
`IN
`
`CRYPTOGRAPHY
`
`645
`
`by teleprocessing systems is au-
`ness communications
`thentication.
`In current business, the validity of contracts
`is guaranteed by signatures. A signed contract serves as
`legal evidence of an agreement which
`the holder can
`present in court if necessary. The use of signatures, how-
`ever, requires
`the
`transmission
`and storage of written
`contracts. In order to have a purely digital replacement for
`this 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 can
`be viewed as a broadcast cipher. Current electronic au-
`thentication
`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
`into
`a one-way authentication
`system.
`of various
`Section V will consider
`the
`interrelation
`cryptographic
`problems and
`introduce
`the even more
`difficult
`problem of trap doors.
`At the same time that communications and computation
`have,given rise to new cryptographic problems,
`their off-
`spring, 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 the
`nineteen
`twenties, however, the “one time pad” was in-
`vented, 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 infor-
`mation
`theory
`[3]. One time pads require extremely
`long
`keys and are therefore prohibitively
`expensive
`in most
`applications.
`the security of most cryptographic systems
`In contrast,
`resides in the computational difficulty
`to the cryptanalyst
`of discovering the plaintext without knowledge of the key.
`This problem
`falls within
`the domains of computational
`complexity and analysis of algorithms,
`two recent disci-
`plines which study the difficulty
`of solving computational
`problems. Using the results of these theories,
`it may be
`possible to extend proofs of security to more useful classes
`of 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
`CRYPTOGRAPHY
`systems
`Cryptography
`is the study of “mathematical”
`for solving
`two kinds of security problems: privacy and
`authentication. A privacy system prevents the extraction
`of information
`by unauthorized
`parties
`from messages
`
`KEY
`SOURCE
`
`Fig. 1. Flow of information
`
`in conventional cryptographic system.
`
`transmitted over a public channel, thus assuring the sender
`of a message that
`it is being read only by the intended
`re-
`cipient. An authenticationsystemprevents
`the unauthor-
`ized 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 inade-
`quate for the needs of its users. A channel such as a tele-
`phone line may therefore be considered private by some
`users and public by others. Any channel may be threatened
`with 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 the
`use of a wiretap,
`is technically more difficult
`and legally
`hazardous.
`In radio, by comparison,
`the situation
`is re-
`versed. Eavesdropping
`is passive and involves no legal
`hazard, while injection exposes the illegitimate
`transmitter
`to discovery and prosecution.
`into those of privacy and
`Having divided our problems
`authentication
`we will sometimes
`further subdivide au-
`thentication
`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 in-
`dividual who presents a credit card must be verified, but
`there is no message which he wishes to transmit.
`In spite
`of this apparent absence of a message in user authentica-
`tion,
`the two problems are largely equivalent.
`In user au-
`thentication,
`there is an implicit message “I AM USER X,”
`while message authentication
`is just verification
`of the
`identity of the party sending the message. Differences
`in
`the threat environments and other aspects of these two
`subproblems, however, sometimes make it convenient
`to
`distinguish between them.
`in a conven-
`Fig. 1 illustrates
`the flow of information
`tional cryptographic
`system used for privacy of commu-
`nications. There are three parties: a transmitter, a receiver,
`and an eavesdropper. The transmitter
`generates a plain-
`text or unenciphered message P to be communicated over
`an insecure channel to the legitimate
`receiver. In order to
`prevent the eavesdropper from learning P, the transmitter
`operates on P with an invertible
`transformation
`SK to
`produce the ciphertext or cryptogram C = SK(P). The key
`K is transmitted onlv to the legitimate receiver via a secure
`channel, indicated by a shielded path in Fig. 1. Since the
`legitimate
`receiver knows K, he can decipher C by oper-
`ating with SK-~ to obtain SK-~(C) = SK-~(SK(P))
`= P,
`the original plaintext message. The secure channel cannot
`
`BlackBerry Corporation Exhibit 1019, pg. 2
`
`

`

`646
`
`IEEE
`
`TRANSACTIONS
`
`ON
`
`INFORMATION
`
`THEORY.
`
`NOVEMBER
`
`1976
`
`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
`{SKJK~~I(~ of invertible
`transformations
`
`family
`
`(1)
`- WI
`SdPl
`from a space (P) of plaintext messages to a space (C) of ci-
`phertext messages. The parameter K is called the key and
`is selected from a finite set (K) called the keyspace. If the
`message spaces (PI and {C) are equal, we will denote them
`both by (M). When discussing
`individual
`cryptographic
`transformations
`SK, we will sometimes omit mention of
`the system and merely refer to the transformation
`K.
`The goal in designing
`the cryptosystem
`{SK) is to make
`the 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 com-
`putational cost of cryptanalysis, but which would succumb
`to an attack with unlimited
`computation,
`is called com-
`putationally
`secure; while a system which can resist any
`cryptanalytic
`attack, no matter how much computation
`is allowed,
`is called unconditionally
`secure. Uncondi-
`tionally
`secure systems are discussed
`in [3] and
`[4] and
`belong
`to that portion of information
`theory, called
`the
`Shannon
`theory, which
`is concerned with optimal perfor-
`mance obtainable with unlimited
`computation.
`Unconditional
`security
`results
`from
`the existence of
`multiple meaningful
`solutions
`to a cryptogram.
`For ex-
`ample, the simple substitution
`cryptogram XMD
`resulting
`from English
`text can represent
`the plaintext messages:
`now, and, the, etc. A computationally
`secure cryptogram,
`in contrast, contains sufficient
`information
`to uniquely
`determine
`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 combined
`with a randomly chosen key of the same length. While such
`a system
`is provably secure, the large amount of key re-
`quired makes it impractical
`for most applications. Except
`as otherwise noted, this paper deals with computationally
`secure 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 sys-
`tems using ‘only’ a few; hundred bits of key and
`imple-
`mentable
`in either a small amount of digital hardware or
`a few hundred
`lines of software.
`if its cost
`infeasible
`We will call a task computationally
`as measured by either
`the amount of memory used or the
`runtime
`is finite but impossibly
`large.
`into convo-
`Much as error correcting codes are divided
`lutional
`and block codes, cryptographic
`systems can be
`divided
`into two broad classes: stream ciphers and block
`ciphers. Stream ciphers process
`the plaintext
`in small
`chunks
`(bits or characters), usually producing a pseudo-
`random sequence of bits which
`is added modulo 2 to the
`
`bits of the plaintext. Block ciphers act in a purely combi-
`natorial
`fashion on large blocks of text, in such a way that
`a small change in the input block produces a major change
`in the resulting output. This paper deals primarily with
`block,ciphers,
`because this error propagation
`property
`is
`valuable
`in many authentication
`applications.
`is used to
`In an authentication
`system, cryptography
`guarantee
`the authenticity
`of the message to the receiver.
`Not only must a meddler be prevented
`from
`injecting
`to-
`tally 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.
`of a message, information
`To guarantee the authenticity
`is added which
`is a function not only of the message and
`a secret key, but of the date and time as well; for example,
`by attaching
`the date and time
`to each message and en-
`crypting
`the entire
`sequence. This assures
`that only
`someone who possesses the key can generate a message
`which, when decrypted, will contain
`the proper date and
`time. Care must be taken, however,
`to use a system
`in
`which small changes
`in
`the ciphertext
`result
`in
`large
`changes in the deciphered plaintext. This intentional
`error
`propagation ensures that if the deliberate
`injection of noise
`on the channel changes a message such as “erase file 7” into
`a different message such as “erase file 8,” it will also cor-
`rupt
`the authentication
`information.
`The message will
`then 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 crypto-
`graphic systems employed
`for either privacy or authenti-
`cation.
`attack
`is a cryptanalytic
`only attack
`A ciphertext
`which
`the cryptanalyst
`possesses only ciphertext.
`in
`A known plaintext
`attack
`is a cryptanalytic
`attack
`which
`the cryptanalyst
`possesses a substantial
`quantity
`of corresponding
`plaintext
`and ciphertext.
`in
`attack
`A chosen plaintext
`attack
`is a cryptanalytic
`number
`which
`the cryptanalyst
`can submit an unlimited
`of plaintext messages of his own choosing and examine the
`resulting cryptograms.
`the opponent knows the
`In all cases it is assumed that
`general system (SK) in use since this
`information
`can be
`obtained by studying a cryptographic
`device. While many
`users of cryptography
`attempt
`to keep their equipment
`secret, many commercial applications
`require not only that
`the general system be public but that
`it be standard.
`A ciphertext
`only attack occurs frequently
`in practice.
`The cryptanalyst
`uses only knowledge of the statistical
`properties of the language in use (e.g., in English,
`the letter
`e occurs 13 percent of the time) and knowledge of certain
`“probable”
`words
`(e.g., a letter probably
`begins “Dear
`Sir:“).
`It is the weakest
`threat
`to which a system can be
`subjected, and any system which succumbs
`to it is con-
`sidered
`totally
`insecure.
`
`in
`
`BlackBerry Corporation Exhibit 1019, pg. 3
`
`

`

`DIFFIE
`
`AND
`
`HELLMAN:
`
`NEW
`
`DIRECTIONS
`
`IN
`
`CRYPTOGRAPHY
`
`647
`
`A system which is secure against a known plaintext at-
`tack frees its users from the need to keep their past mes-
`sages secret, or to paraphrase
`them prior
`to declassifica-
`tion. This is an unreasonable burden
`to place on the sys-
`tem’s users, particularly
`in commercial situations where
`product announcements or press releases may be sent in
`encrypted
`form for later public disclosure. Similar situa-
`tions in diplomatic correspondence have led to the cracking
`of many supposedly secure systems. While a known
`plaintext
`attack
`is not always possible, its occurrence
`is
`frequent enough that a system which cannot resist it is not
`considered secure.
`in
`to achieve
`is difficult
`attack
`A chosen plaintext
`practice, but can be approximated. For example, submit-
`ting a proposal
`to a competitor may result
`in his enci-
`phering
`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 can
`plant messages in their system.
`systems as secure, it is
`For the purpose of certifying
`appropriate
`to consider the more formidable cryptanalytic
`threats as these not only give more realistic models of the
`working environment of a cryptographic system, but make
`the assessment of the system’s strength easier. Many sys-
`tems which are difficult
`to analyze using a ciphertext only
`attack can be ruled out immediately under known plain-
`text or chosen plaintext attacks.
`is a
`cryptanalysis
`As is clear from
`these definitions,
`system identification
`problem. The known plaintext and
`chosen plaintext attacks correspond to passive and active
`system identification
`problems, respectively. Unlike many
`subjects in which system identification
`is considered, such
`as automatic
`fault diagnosis, the goal in cryptography
`is
`to build systems which are difficult,
`rather
`than easy, to
`identify.
`is often called an IFF at-
`The chosen plaintext attack
`tack, terminology which descends from
`its origin
`in the
`development of cryptographic
`“identification
`friend or
`foe” 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 ter-
`ritory, enemy cryptanalysts can send challenges and ex-
`amine 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
`is
`countered by restricting
`the form of the challenges, which
`need not be unpredictable,
`but only nonrepeating.
`There are other threats to authentication systems which
`cannot be treated by conventional
`cryptography,
`and
`which require
`recourse to the new ideas and techniques
`introduced
`in this paper. The threat of compromise of the
`receiver’s authentication
`data is motivated by the situa-
`tion in multiuser networks where the receiver is often the
`
`tables and other
`system itself. The receiver’s password
`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
`also protect against the threat of dispute. That
`is, a mes-
`sage may‘ be sent but
`later
`repudiated
`by either
`the
`transmitter or the receiver. Or, it may be alleged by either
`party that a message was sent when in fact none was. Un-
`forgeable digital signatures and receipts are needed. For
`example, a dishonest stockbroker might
`try
`to cover up
`unauthorized
`buying and selling
`for personal gain by
`forging orders from clients, or a client might disclaim an
`order actually authorized by him but which he later sees
`will cause a loss. We will
`introduce concepts which allow
`the receiver to verify
`the authenticity
`of a message, but
`prevent him from generating apparently authentic mes-
`sages, thereby protecting against both the threat of com-
`promise of the receiver’s authentication
`data and the
`threat of dispute.
`
`III. PUBLIC
`KEY CRYPTOGRAPHY
`As shown in Fig. 1, cryptography has been a derivative
`security measure. Once a secure channel exists along which
`keys can be transmitted,
`the security can be extended
`to
`other channels of higher bandwidth
`or smaller delay by
`encrypting
`the messages sent on them. The effect has been
`to limit
`the use of cryptography
`to communications among
`people 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 n
`results 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 with
`no prior acquaintance will be able to wait for a key to be
`sent by some secure physical means, or that keys for all (n2
`n)/2 pairs can be arranged in advance. In another paper
`th e authors have considered a conservative approach
`ii
`requiring no new development
`in cryptography
`itself, but
`this involves diminished security,
`inconvenience, and re-
`striction of the network
`to a starlike configuration with
`respect to initial connection protocol.
`We propose that
`it is possible to develop systems of the
`type 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. We examine two
`approaches to this problem, called public key cryptosys-
`
`Fig. 2. Flow of information
`
`in public key system.
`
`BlackBerry Corporation Exhibit 1019, pg. 4
`
`

`

`64X
`
`IEEE
`
`TRANSACTJONS
`
`ON
`
`INFORMATION
`
`THEORY,
`
`NOVEMBER
`
`1976
`
`respectively.
`terns and public key distribution
`systems,
`lending
`first are more powerful,
`themselves
`to the
`The
`solution 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
`
`ID K K E JRJ of algorithms 1
`representing
`PKIK E (KI and
`invertible
`transformations,
`
`I&:(Mj
`D[(:(M)
`
`-+ {M)
`--- *’ {M)
`
`(2)
`(3)
`
`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
`in-
`version which
`is a harder problem. And it is at least con-
`ceptually
`simpler
`to obtain an arbitrary
`inverse
`pair of
`matrices
`than it is to invert a given mabrix, St.art with
`the
`row and column op-
`identity matrix
`I and do elementary
`erations
`to obtain an arbitrary
`invertible matrix E. Then
`I do the inverses of these same elementary
`starting with
`operations
`in reverse order
`to obtain 61 - E--l. The se-
`quence of elementary
`operations
`could be easi1.y deter-
`mined
`from a random bit string.
`takes only a.bout n3
`Unfortunately,
`matrix
`inversion
`The ratio of “cryptanalytic”
`time
`(i.e., com-
`operations.
`puting D from E)
`to enciphering
`or deciphering
`t,ime is
`thus at most n, and enormous block sizes would be re-
`quired
`to obtain
`ratios of 3 O6 or greater. Also, it does not
`appear 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 arith-
`is unimportant
`in the matrix
`metic, numerical
`stability
`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 hard
`from E, makes use of the difficulty
`of analyzing
`to infer
`programs
`in low level languages. Anyone who has tried
`to
`determine 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
`to
`prevent
`its identification
`from
`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 of
`program and run time are not crucial
`in this application,
`such compilers may be possible
`if the struct,ure of the
`machine
`language can be optimized
`to assist in the con-
`fusion.
`the problem of
`studied
`[I] has independently
`Merkle
`keys over an insecure channel. His approach
`distributiug
`from
`that of the public key cryptosystems
`is different
`suggested above, and will be termed a public key distri-
`.users, A and B, to se-
`bution system. The goal is for
`two
`curely exchange a key over an insecure charmel. This key
`for
`is then used by both users in a normal cryptosystem
`both 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 legiti-
`mate users of the system is as much in transmission
`time
`as in computation,
`because Merkle’s protocol
`requires n
`
`to compute
`
`inverse
`
`3)
`
`4)
`
`on a finite message space
`(MJ, such
`that
`1)
`for every K E {Kb EK is the inverse of DK,
`for every K E {KJ and M E (MI, the algorithms EK
`2)
`and DK are easy to compute,
`for almost every K E (KJ, each easily computed al-
`gorithm
`equivalent
`to Df(
`is computationally
`in-
`feasible
`to derive
`from EK,
`for every K E {K), it is feasible
`pairs EK and DK from K.
`key
`Because of the third property, a user’s enciphering
`the security
`EK can be made public without compromising
`of his secret deciphering
`key DK. The cryptographic
`sys-
`tem is therefore split into two parts, a family of enciphering
`transformations
`and a family of deciphering
`transforma-
`it
`tions
`in such a way that, given a member of one family,
`is infeasible
`to find
`the corresponding member of the
`other.
`is a feasible
`that
`The fourth property guarantees
`there
`pairs of inverse
`trans-
`way of computing
`corresponding
`is placed on what either the
`formations when no constraint
`enciphering
`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.
`the problem of key distri-
`Given a system of this kind,
`simplified.
`Each user generates a pair of
`bution
`is vastly
`inverse
`transformations,
`E and D, at his terminal. The
`deciphering
`transforrnation
`D must be kept secret, but
`need never be communicated
`on any channel. The enci-
`phering 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. Public
`key cryptosystems can thus be regarded as multiple access
`ciphers.
`keys be
`file of enciphering
`the public
`that
`It is crucial
`task
`is
`protected
`from unauthorized modification.
`This
`file. Read prot,ec
`made easier by the public nature of the
`is modified
`infre-
`tion
`is unnecessary and, since the file
`quently,
`elaborate write protection mechanisms
`can be
`economically employed.
`useless, example
`A suggestive, although unfortunate!.y
`is to encipher
`the plaintext,
`of a public key cryptosystem
`n-vector m, by multiplying
`it by
`represented
`as a binary
`an invertible binary n X n matrix E. The cryptogram
`thus
`
`BlackBerry Corporation Exhibit 1019, pg. 5
`
`

`

`DIFFIE
`
`AND
`
`IIELLMAN:
`
`NEW
`
`DIRECTIONS
`
`IN
`
`CRYPTOGRAPHY
`
`649
`
`before orie key can be
`keys to be transmitted
`potential
`this high
`transmission
`decided on. Merkle not.es that
`overhead prevents
`the system from being very useful in
`practice.
`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 most
`applications.
`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 prac-
`tical value.
`system
`We now suggest a new public key distribution
`First,
`it requires only one
`which has several advantages.
`“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 to
`authenticate
`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 difficulty
`of computing
`logarithms over a finite
`field GF(q) with a
`prime number q of elements. Let
`forl_<XIq-1,
`Y = crx mod q1
`(4)
`where 01 is a fixed primit,ive element of GE’(q), then X is
`referred
`to as the logarithm of Y to the base 01, mod q:
`
`X = log, Y mod q,
`
`(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%
`
`forl<YIq-1.
`
`y = ,I8 = (((u.“)2)“)2 x *2.
`
`(6)
`Computing X from Y, on the other hand can be much more
`difficult
`and, for certain carefully chosen values of q, re-
`quires 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