United States Patent [191
`Hellman et al.
`
`[54] PUBLIC KEY CRYPTOGRAPHIC
`APPARATUS AND MEI'HOD
`
`[75] Inventors: Martin E. Hellman, Stanford; Ralph
`.
`C. Merkle, Palo Alto, both of Calif.
`
`[73] Assignee: The Board of Trustees of the Leland
`sword Junior University, Smnford,
`Calif.
`[21] APPL No’: 839,939
`_
`[22] Filed:
`[511 Int. Cl 2
`{521 U S
`[58] Fielh
`
`oct- 6, 1977
`
`"ML 9/04
`364/900
`178/22
`
`.......................................
`"" "
`........................................ ..
`References Cited
`PUBLICATIONS
`
`[56]
`
`“New Directions in Cryptography,” Dif?e et al., IEEE
`Transactions on Information Theory, vol. 1122, No. 6,
`Nov. 1976, pp. 644-654.
`“A User Authentication Scheme not Requiring Secrecy
`in the Computer,” Evans, .lr., et al., Communications of
`the ACM, Aug. 1974, vol. 17, No. 8, pp. 437-442.
`“A High Security Log-In Procedure,” Purdy, Commu
`
`[11]
`[45]
`
`4,218,582
`Aug. 19, 1980
`
`nications of the ACM. Aug. 1974, vol. 17, No. 8, pp.
`442-445.
`Dif?e et al., “Multi-User Cryptographic Techniques,”
`AFIPS Conference
`eedin
`Proc
`gs, vol. 45, pp. 109-112,
`mm 8’ 1976_
`
`-
`-
`- _
`-
`Primary Examiner Howard A. Blrmlel
`[57]
`ABSTRACT
`A cryptographic system‘transmits a computationally
`secure cryptogram that is generated from a publicly
`known transformation of the message sent by the trans
`mitter; the cryptogram is again transformed by the au
`themed receiver using a secret reciprocal transtbrmaf
`tion to reproduce the message sent. The authorized
`reoeiver,s transformation is known only by the au?m
`rized receiver and is used to generate the transmitter’s
`transformation that is made publicly known. The pub
`licly known transformation uses operations that are
`easily performed but extremely difficult to invert. It is
`infeasible for an unauthorized receiver to invert the
`publicly known transformation or duplicate the autho
`rized receiver's secret transformation to obtain the mes
`sage sent.
`
`17 Claims, 13 Drawing Figures
`
`/I3
`I__——TQ—_—;2T_II
`I
`DECIPHERING ‘i
`may
`I
`I
`oavacz
`GENERATOR
`|
`:
`S L___’—TE
`I
`
`i___ ______ ________l
`
`F ---- “TI
`l
`I
`ENCIPHERING
`I
`"I
`ocwc:
`l
`|_
`'5/
`2
`
`E
`
`II/
`
`TRANSMITTER _’ INSECURE *’ TRANSMITTER
`RECEIVER __ CHANNEL
`RECEIVER
`3//
`19
`32/
`
`/6 l
`[-
`|
`oecwusnms
`i
`|
`news:
`'5
`D
`KEY
`GENERATOR
`‘mm
`KEY
`sounca
`\zs
`
`x
`
`2 3
`'
`|
`.
`I 9
`I
`i
`|
`:
`
`IE
`:
`I
`I
`l2~|
`
`1
`
`EX 1010
`IPR of Pat. No. 6,892,304
`
`

`

`U.S. Patent
`
`UA
`
`o_mx8.59_,oz.mu:n__umo_w\3_ulmhc
`II1!I.
`
`mofimmzmo-mu.>8
`
`Exoz_mm:m_H._o
`
`4,218,582
`
`\Gxk
`
`
`
`ylululIn|I|.nJ_
`
`mm(8_/_W__13_|_‘OLD—Cm1mum_mozmmzmo
`
`
`E>_m_H_mdzz<5E>mammmo58_.myEt_s_mz<E.
`
`
`mm8mmz_EC_s_mz<Eoz_mm:n__uzm
`
`2
`
`
`
`

`

`aPS_
`
`4|.H
`
`U
`
`0.5
`
`000N
`
`hS
`
`7F.02
`
`4,218,582
`
`UM.mi.
`
`
`
`..,..Efllflaé
`
`AEfllfififm
`
`w,Efllgfiln
`
`afllflnK:
`
`
`
`Jot.»mmQD<l\nh.h.
`
`m._.m._n=2OUmo»<m<n_s_ou
`
`
`
`mo_.<m<n__2oo\mm
`
`
`
`moB<Em:m{um
`
`V?
`
`N..o\:.\
`
`3
`
`
`

`

`U.S. Patent
`
`Aug. 19, 1980
`
`Sheet 3 of7
`
`4,218,582
`
`6\4
`
`55
`
`zmzk-5"’: Zo
`
`Pk-: Pk-2'"
`0 I
`
`
`m mooom
`
`P>""
`
`4
`
`

`

`U.S. Patent Aug. 19, 1980
`
`Sheet 4 of?
`
`4,218,582
`
`W
`
`I
`
`/9/
`
`INVERTOR
`
`D
`
`m
`‘ vr'modm
`Oi
`s———-——> MULTIPLIER f9?
`
`5 /94
`4
`»——> SUBTRACTOR <—
`
`@
`
`/93
`
`—> COMPARATOR
`
`x
`
`"—_>. .
`
`.
`
`.
`
`’95
`
`COMPARATOR
`O
`*——->
`
`HALT
`
`/96
`
`FIG‘. 7
`
`uk-r uk-z "' “I
`
`vk-I vk-Z "~ "I
`
`//0/
`uo “—
`
`//0Z
`V0
`
`//03
`UP-DOWN
`COUNTER
`
`vbI
`
`//05
`"-_>
`SUBTRACTQR
`
`v
`
`5H|FT
`CONTROL
`
`u-v
`
`//O4
`»
`COMPARATOR --—— qi
`—_>
`
`FIG. 8
`
`5
`
`

`

`US. Patent Aug. 19, 1980
`
`Sheet 5 of7
`
`4,218,582
`
`m
`1 / Pbs d
`F?’ EXPONENTIATOR ' m m
`D *H I
`L.
`//2/_"_
`I
`I
`
`5
`
`O
`
`DIVIDER
`
`T’
`
`x_
`///3
`COMPARATOR ————'
`
`F [6‘. 9
`
`/2// sk-I sk-z °°° 5|
`
`so
`
`IZZF O
`
`O "0 O
`
`I
`
`I23
`
`/24-_ MULTIPLIER
`
`FIG. l0
`
`6
`
`

`

`US. Patent Aug. 19, 1980
`
`Sheet 6 of7
`
`4,218,582
`
`ei(FROM KEY SOURCE 26)
`
`/3/
`/
`TABLE OF
`SMALL PR|MES
`
`pi
`
`I32
`l /
`
`p6;
`
`i
`
`P EXPONENTIATOR
`
`//33
`MULTlPLER
`
`?pfi
`
`—__’
`
`|—>
`
`//34
`ADDER
`
`m
`
`//35
`‘-—-> PRIME TESTER
`
`050}
`
`b (FROM KEY SOURCE 26)
`
`L w w“
`
`LOGARITHMIC CONVERTOR
`/36/
`
`FIG‘. //
`
`m
`
`9-. D
`
`lo_ M m
`
`7
`
`

`

`US. Patent Aug. 19, 1980
`
`Sheet 7 of7
`
`4,218,582
`
`@a FIG‘. l2
`
`> I
`1
`B<—B2 (mod p)
`
`i
`
`TRUE
`
`FIG‘. 13
`
`8
`
`

`

`1
`
`PUBLIC KEY CRYPTOGRAPHIC APPARATUS
`AND METHOD
`
`The Government has rights in this invention pursuant 5
`to Grant No. ENG- 10173 of the National Science
`Foundation and IPA No. 0005.
`
`4,218,582
`2
`proach, a machine language approach and a logic map
`ping approach. While the matrix approach can be de
`signed with matrices that require a demonstrably infea
`sible cryptanalytic time (i.e., computing D from B)
`using known methods, the matrix approach exhibits a
`lack of practical utility because of the enormous dimen
`sions of the required matrices. The machine language
`approach and logic mapping approach are also sug
`gested, but there is no way shown to design them in
`such a manner that they would require demonstrably
`infeasible cryptanalytic time.
`Dif?e also introduces a procedure using the proposed
`public key cryptosystems, that could allow the receiver
`to easily verify the authenticity of a message, but which
`prevents him from generating apparently authenticated
`messages. Dif?e describes a protocol to be followed to
`obtain authentication with the proposed public key
`cryptosystem. However, the authentication procedure
`relies on the existence of a public key cryptosystem
`which Diffie did not provide.
`
`10
`
`BACKGROUND OF THE INVENTION
`1. Field of Invention
`The invention relates to cryptographic systems.
`2. Description of Prior Art
`Cryptographic systems are widely used to ensure the
`privacy and authenticity of messages communicated
`over insecure channels. A privacy system prevents the
`extraction of information by unauthorized parties from
`messages transmitted over an insecure channel, thus
`assuring the sender of a message that it is being read
`only by the intended receiver. An authentication system
`prevents the unauthorized injection of messages into an
`insecure channel, assuring the receiver of the message
`of the legitimacy of its sender.
`Currently, most message authentication consists of
`appending an authenticator pattern, known only to the
`transmitter and intended receiver, to each message and
`encrypting the combination. This protects against an
`eavesdropper being able to forge new, properly authen
`ticated messages unless he has also stolen the cipher key
`being used. However, there is little protection against
`the threat of dispute; that is, the transmitter may trans
`mit a properly authenticated message, later deny this
`action, and falsely blame the receiver for taking unau
`thorized action. Or, conversely, the receiver may take
`unauthorized action, forge a message to itself, and
`falsely blame the transmitter for these actions. The 35
`threat of dispute arises out of the absence of a suitable
`receipt mechanism that could prove a particular mes
`sage was sent to a receiver by a particular transmitter.
`One of the principal difficulties with existing crypto
`graphic systems is the' need for the sender and receiver
`to exchange a cipher key over a secure channel to
`which the unauthorized party does not have access. The
`exchange of a cipher key frequently is done by sending
`the key in advance over a secure channel such as private
`courier or registered mail; such secure channels are
`usually slow and expensive.
`Diffie, et al, in “Multiuser Cryptographic Tech
`niques,” AFIPS-Conference Proceedings. Vol. 45, pp.
`109-112, June 8, 1976, propose the concept of a public
`key cryptosystem that would eliminate the need for a
`secure channel by making the sender’s keying informa
`tion public. It is also proposed how such a public key
`cryptosystem could allow an authentication system
`which generates an unforgeable message dependent
`digital signature. Dif?e presents the idea of using a pair 55
`of keys E and D, for enciphering and deciphering a
`message, such that E is public information while D is
`kept secret by the intended receiver. Further, although
`D is determined by B, it is infeasible to compute D from
`E. Dif?e suggests the plausibility of designing such a
`public key cryptosystem that would allow a user to
`encipher a message and send it to the intended receiver,
`but only the intended receiver could decipher it. While
`suggesting the plausibility of designing such systems,
`Diffie presents neither proof that public key cryptosys
`tems exist, nor a demonstration system.
`Dif?e suggests three plausibility arguments for the
`existence of a public key cryptosystem: a matrix ap
`
`20
`
`SUMMARY AND OBJECTS OF THE
`INVENTION
`Accordingly, it is an object of the invention to allow
`authorized parties to a conversation (conversers) to
`converse privately even though an unauthorized party
`(eavesdropper) intercepts all of their communications.
`Another object of this invention is to allow a con
`verser on an insecure channel to authenticate another
`converser’s identity.
`Another object of this invention is to provide a re
`ceipt to a receiver on an insecure channel to prove that
`a particular message was sent to the receiver by a par
`ticular transmitter. The object being to allow the re
`ceiver to easily verify the authenticity of a message, but
`to prevent the receiver from generating apparently
`authenticated messages.
`An illustrated embodiment of the present invention
`describes a method and apparatus for communicating
`securely over an insecure channel, by communicating a
`computationally secure cryptogram that is a publicly
`known transformation of the message sent by the trans
`mitter. The illustrated embodiment differs from prior
`approaches to a public key cryptosystem, as described
`in “Multiuser Cryptographic Techniques,” in that it is
`both practical to implement and is demonstrably infeasi
`ble to invert using known methods.
`In the present invention, a receiver generates a secret
`deciphering key and a public enciphering key, such that
`the secret deciphering key is difficult to generate from
`the public enciphering key. The transmitter enciphers a
`message to be communicated by transforming the mes
`sage with the public enciphering key, wherein the trans
`formation used to encipher the message is easy to effect
`but difficult to invert without the secret deciphering
`key. The enciphered message is then communicated
`from the transmitter to the receiver. The receiver deci
`phers the enciphered message by inverting the enci
`phering transformation with the secret deciphering key.
`Another illustrated embodiment of the present inven
`tion describes a method and apparatus for allowing a
`transmitter to authenticate an authorized receiver’s
`identity. The authorized receiver generates a secret
`deciphering key and a public enciphering key, such that
`the secret deciphering key is difficult to generate from
`the public enciphering key. The transmitter enciphers a
`message to be communicated by transformln g the mes
`sage with the public enciphering key, wherein the trans
`
`25
`
`40
`
`65
`
`9
`
`

`

`4,218,582
`4
`3
`alternative deciphering device of FIG. 9 and the public
`formation used to encipher the message is easy to effect
`key generator of FIG. 11.
`but difficult to invert without the secret deciphering
`FIG. 11 is a public key generator for generating the
`key. The enciphered message is then transmitted from
`public enciphering key in the public key cryptosystem
`the transmitter to the receiver. The receiver deciphers
`the enciphered message by inverting the enciphering
`of FIG. 1.
`FIG. 12 is a flow chart for the algorithm of the loga
`transformation with the secret deciphering key. The
`rithmic converter of FIG. 11 when p— l is a power of 2.
`receiver’s identity is authenticated to the transmitter by
`FIG. 13 is a ?ow chart for the algorithm for comput
`the receiver's ability to decipher the enciphered mes
`ing the coefficients {bj} of the expansion
`sage.
`Another illustrated embodiment of the present inven
`tion describes a method and apparatus for providing a
`receipt for a communicated message. A transmitter
`generates a secret key and a public key, such that the
`secret key is difficult to generate from the public key.
`The transmitter then generates a receipt by transform
`ing a representation of the communicated message with
`the secret key, wherein the transformation used to gen
`erate the receipt is difficult to effect without the secret
`key and easy to invert with the public key. The receipt
`is then communicated from the transmitter to the re
`ceiver. The receiver inverts the transformation with the
`public key to obtain the representation of the communi
`cated message from the receipt and validates the receipt
`by comparing the similarity of the representation of the
`communicated message with the communicated mes
`sage.
`Additional objects and features of the present inven
`tion will appear from the description that follows
`wherein the preferred embodiments have been set forth
`in detail in conjunction with the accompanying draw
`mgs.
`
`x(modp'-" = ""51 b- ,1‘
`I
`j=0 ]P
`
`where Oébjé p,-— l, of the logarithmic convertor of
`FIG. 11, when p- l is not a power of 2.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`Referring to FIG. 1, a public key cryptosystem is
`shown in which all transmissions take place over an
`insecure communication channel 19, for example a tele
`phone line. Communication is effected on the insecure
`channel 19 between transmitter 11 and receiver 12 using
`transmitter-receiver units 31 and 32, which may be
`modems such as Bell 201 modems. Transmitter 11 pos
`sesses an unenciphered or plaintext message X to be
`communicated to receiver 12. Transmitter 11 and re
`ceiver 12 include an enciphering device 15 and deci
`phering device 16 respectively, for enciphering and
`deciphering information under the action of an enci
`phering key E on line B and a reciprocal deciphering
`key D on line D. The enciphering and deciphering
`devices 15 and 16 implement inverse transformations
`when loaded with the corresponding keys E and D. For
`example, the keys may be a sequence of random letters
`or digits. The enciphering device 15 enciphers the plain
`text message X into an euciphered message or cipher
`text S that is transmitted by transmitter 11 through the
`insecure channel 19; the ciphertext S is received by
`receiver 12 and deciphered by deciphering device 16 to
`obtain the plaintext message X. An unauthorized party
`or eavesdropper 13 is assumed to have key generator 23
`and deciphering device 18 and to have access to the
`insecure channel 19, so if he knew the deciphering key
`D he could decipher the ciphertext S to obtain the
`plaintext message X.
`The example system makes use of the difficulty of the
`so-called “knapsack problem.” De?nitions of the knap
`sack problem exist in the literature, for example, Ellis
`Horowitz and Sartaj Sahni, “Computing Partitions with
`Applications to the Knapsack Problem", JACM, Vol.
`21, No. 2, April 1974, pp. 277-292; and O. H. Ibarra and
`C. E. Kim, “Fast Approximation Algorithms for the
`Knapsack and Sum of Subset Problems”, JACM, Vol.
`22, No. 4, October 1975, pp. 464-468. The definition
`used here is adapted from R. M. Karp, “Reducibility
`Among Combinatorial Problems” in Complexity of
`Computer Computations, by R. E. Miller and J. W.
`Thatcher, eds., Plenum Press, New York (1972), pp.
`85-104. Simply stated, given a one-dimensional knap
`sack of length S and a vector a composed of n rods of
`lengths a1, a2, .
`.
`. an, the knapsack problem is to ?nd a
`subset of the rods which exactly ?lls the knapsack, if
`such a subset exists. Equivalently, find a binary n-vector
`x of Us and l’s such that S =a‘x, if such an x exists, ('
`applied to vectors denotes dot product, applied to sea
`lars denotes normal multiplication).
`
`5
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a public key cryptosys
`tem that transmits a computationally secure cryptogram
`over an insecure communication channel.
`FIG. 2 is a block diagram of an enciphering device
`for enciphering a message into ciphertext in the public
`key cryptosystem of FIG. 1.
`FIG. 3 is a block diagram of a multiplier for perform
`ing modular multiplications in the deciphering device of
`FIG. 7, the exponentiator of FIG. 10, and the public key
`generator of FIG. 11.
`FIG. 4 is a detailed schematic diagram of an adder for
`performing additions in the enciphering device of FIG.
`2, the multiplier of FIG. 3, and the public key generator
`of FIG. 11.
`FIG. 5 is a detailed schematic diagram of a compara
`tor for performing magnitude comparisons in the enci
`phering device of FIG. 2, the multiplier of FIG. 3, the
`deciphering device of FIG. 7, the divider of FIG. 8, and
`the alternative deciphering device of FIG. 9.
`FIG. 6 is a detailed schematic diagram of a subtractor
`for performing subtraction in the multiplier of FIG. 3,
`the deciphering device of FIG. 7, and the dividier of
`FIG. 8.
`FIG. 7 is a block diagram of a deciphering device for
`deciphering a ciphertext into message in the public key
`cryptosystem of FIG. 1.
`FIG. 8 is a block diagram of a divider for performing
`division in the inverter of FIG. 7 and the alternative
`deciphering device of FIG. 9.
`FIG. 9 is a block diagram of an alternative decipher
`ing device for deciphering a ciphertext into message in
`the public key cryptosystem of FIG. 1.
`FIG. 10 is an exponentiator for raising various num
`bers to various powers in modulo arithmetic in the
`
`40
`
`45
`
`55
`
`65
`
`10
`
`

`

`4,218,582
`6
`w have no common factors except 1). For example, the
`key source 26 may contain a random number generator
`that is implemented from noisy ampli?ers (e.g., Fair
`child ,1. 709 operational ampli?ers) with a polarity de
`tector. The key generator 22 is provided a knapsack
`vector, a’ which satisfies (1) and therefore allows solu
`tion of S'=a"x, and transforms the easily solved knap
`sack vector a’ into a trap door knapsack vector a via
`the relation
`
`5
`A supposed solution, x, is easily checked in at most It
`additions; but, to the best of current knowledge, ?nding
`a solution requires a number of operations which grows
`exponentially in n. Exhaustive trial and error search
`over all 2" possible x’s is computationally infeasible if n
`is larger than one or two hundred. Thus, it is computa
`tionally infeasible to invert the transformation; such
`transformations are characterized by the class of mathe
`matical functions known as one-way cipher functions.
`A task is considered computationally infeasible if its
`cost as measured by either the amount of memory used
`or the computing time is ?nite but impossibly large, for
`example, on the order of approximately 1030 operations
`with existing computational methods and equipment.
`Theory suggests the dif?culty of the knapsack prob
`lem because it is an NP-complete problem, and is there
`fore one of the most difficult computational problems of
`a cryptographic nature. (See for example, A. V. Aho, J.
`E. Hopcraft and J. D. Ullman, The Design and Analysis‘
`of Computer Algorithms, Reading, Ma.; Addison-Wes
`ley, 1974, pp. 363-404.) Its degree of difficulty, how
`ever, is dependent on the choice of a. If a=(l, 2, 4, . . .
`2("—l)), then solving for x is equivalent to ?nding the
`binary representation of S. Somewhat less trivially, if
`for all i,
`
`a,-=w'a'i mod m
`
`(3)
`
`The vector a serves as the public enciphering key E on
`line E, and is either placed in a public ?le or transmitted
`over the insecure channel 19 to transmitter 11. The
`enciphering key E is thereby made available to both the
`transmitter 11 and the eavesdropper 13. The transmitter
`11 uses the enciphering key E, equal to a, to generate
`the ciphertext S from the plaintext message X, repre
`sented by vector x, by letting S=a'x. However, be
`cause the a; may be psuedo-randomly distributed, the
`eavesdropper 13 who knows a, but not w or m, cannot
`feasibly solve a knapsack problem involving a to obtain
`the desired message it.
`The deciphering device 16 of receiver 12 is given w,
`m and a’ as its secret deciphering key D, and can easily
`compute
`
`20
`
`25
`
`'—
`l > I a,
`a,
`I
`
`(1)
`
`then x is also easily found: xn=l if and only if 85a",
`and, for i=n-l, n-2, . . . l, xi=l ifand only if
`
`n
`
`_
`
`> _
`
`(2)
`
`35
`
`If m is chosen so that
`
`If the components of x are allowed to take on integer
`values between 0 and 1 then condition (1) can be re
`placed by
`
`i-—1
`a,- > lj=2l rlj
`
`and xican be recovered as the integer part of
`
`xj ‘ aj)/a,:
`
`Equation (2) for evaluating it; when xiis binary valued is
`equivalent to this rule for l= l.
`A trap door knapsack is one in which careful choice
`of a allows the designer to easily solve for any x, but
`which prevents anyone else from ?nding the solution.
`Two methods will be described for constructing trap
`door knapsacks, but ?rst a description of their use in a
`public key cryptosystem as shown in FIG. 1 is pro
`vided. Receiver 12 generates a trap door knapsack vec
`tor a, and either places it in a public ?le or transmits it
`to transmitter 11 over the insecure channel 19. Trans
`mitter 11 represents the plaintext message X as a vector
`x of n 0’s and 1's, computes S=a"x, and transmits S to
`receiver 12 over the insecure channel 19. Receiver 12
`can solve S for x, but it is infeasible for eavesdropper 13
`to solve S for x.
`In one method for generating trap door knapsacks,
`the key generator 22, uses random numbers generated
`by key source 26 to select two large integers, in and w,
`such that w is invertible modulo in, (Le, so that m and
`
`m>Zai'
`
`(3)
`
`then (7) implies that S’ is equal to 2x,-"a,-’ in integer
`arithmetic as well as mod m. This knapsack is easily
`solved for x, which is also the solution to the more
`difficult trap door knapsack problem S=a"x. Receiver
`12 is therefore able to recover the plaintext message X,
`represented as the binary vector it. But, the eavesdrop
`per 13’s trap door knapsack problem can be made com
`putationally infeasible to solve, thereby preventing the
`eavesdropper 13 from recovering the plaintext message
`
`To help make these ideas more clear, an illustrative
`example is given in which n=5. Taking m=8443,
`a'=(17l, 196, 457, 1191, 2410), and w=2550, then
`a=(5457, 1663, 216, 6013, 7439). Given x=(0, 1, 0, 1, l)
`the
`enciphering
`device
`15
`computes
`S: 1663 +6013+7439= 15115. The deciphering device
`16 uses Euclid’s algorithm (see for instance, D. Knuth,
`The Art of Computer Programming, vol. II, Addison
`Wesley, 1969, Reading Ma.) to compute 1/w=3950 and
`then computes
`
`45
`
`50
`
`55
`
`S‘ = 1/w 'Smod m
`= 3950 ' l5ll5 mod 8443
`= 3797
`
`(9)
`
`65
`
`Because S'>a5', the deciphering device 16 determines
`that x5=l. Then, using (2) for the a’ vector, it deter
`mines that x4= l, x3=0, x2=l, x1=0 or x=(0, 1, 0, l,
`l), which is also the correct solution to S=a"x
`The eavesdropper, 13 who does not know m, w or a’
`has great difficulty in solving for x in S=a*x even
`
`11
`
`

`

`A’
`7
`14
`5
`[0
`
`P
`0
`0 + 7 = 7
`7 + 14 = 21
`2l + 5 = 3mod 23
`
`4,218,582
`8
`7
`though he knows the method used for generating the
`Next, the contents of W register 51 are shifted one bit
`to the right and a 0 is shifted in at the left so its contents
`trap door knapsack vector a. His task can be made infea
`sible by choosing larger values for n, m, w and a’. His
`become 0wk_1 wk_1 .
`. . wzwl, so that w is ready for
`task can be further complicated by scrambling the order
`conputing 2w1a' mod m. The quantity of 2a’ mod m is
`computed for this purpose by using adder 55 to add a’ to
`of the a,-, and by adding different random multiples of m
`itself, using comparator 56 to determine if the result, 20',
`to each of the a.
`The example given was extremely small in size and
`is less than m, and using subtractor 57 for subtracting m
`only intended to illustrate the technique. Using n= 100
`from 2:!‘ if the result is not less than m. The result, 2a’
`mod m is then stored in the A’ register 52. The right
`(which is the lower end of the usable range for high
`most bit, containing W1, of the W register 51 is then
`security systems at present) as a more reasonable value,
`it is suggested that m be chosen approximately uni
`examined, as before, and the process repeats.
`formly from the numbers between 220! +1 and 2202- 1;
`This process is repeated a maximum of k times or
`until the W register 51 contains all Us, at which point
`that a)’ be chosen uniformly from the range (l, 2100);
`that a’; be chosen uniformly from (2109+ l, P2100); that
`wa’ modulo m is stored in the P register 54.
`As an example of these operations, consider the prob
`a3’ be chosen uniformly from (3X2l°°+ I, 4*2lm); .
`.
`.
`lem of computing 7X 7 modulo 23. The following steps
`and that a,’ be chosen uniformly from ((2"-‘— l)‘I
`show the successive contents of the W, A’ and P regis~
`2100+], 2"-1'2100); and that w’ be chosen uniformly
`ters which result in the answer 7 X7=3 modulo 23.
`from (2, m-2) and then divided by the greatest com
`mon divisor of (w', m) to yield w.
`These choices ensure that (8) is met and that an eaves
`dropper 13 has at least 2100 possibilities for each parame
`ter and hence cannot search over them all.
`The enciphering device 15 is shown in FIG. 2. The
`sequence of integers a1, a2, .
`.
`. a,I is presented sequen
`tially in synchronization with the sequential presenta
`tion of 0’s and l‘s of x1, x2, .
`.
`. x”. The S register 41 is
`initially set to zero. If xi=l the S register 41 contents
`are ai are added by adder 42 and the result placed in the
`S register 41. If x,'=0 the contents of the S register 41
`are left unchanged. In either event, i is replaced by i+l
`until i=n, in which case the enciphering operation is
`complete. The i register 43 is initially set to zero and
`incremented by 1 after each cycle of the enciphering
`device. Either the adder 42, or a special up counter can
`be used to increment the i register 43 contents. With the
`range of values suggested above, the S and i registers 41
`and 43 both can be obtained from a single 1024 bit ran
`dom access memory (RAM) such as the Intel 2102. The
`implementation of the adder 42 will be described in
`40
`more detail later, as will the implementation of a com
`parator 44 required for comparing i and n to determine
`when the enciphering operation is complete.
`The key generaor 22 comprises a modulo m multi
`plier, such as that depicted in FIG. 3, for producing
`a,-=w"a,-' mod m. The two numbers w and a,-' to be
`multiplied are loaded into the W and A’ registers 51 and
`52 respectively, and m is loaded into the M register 53.
`The product w‘af modulo m will be produced in the P
`register 54 which is initially set to zero. If k, the number
`of bits in the binary representation of m, is 200, then all
`four registers can be obtained from a single 1024 bit
`RAM such as the Intel 2l02. The implementation of
`FIG. 3 is based on the fact that wa,’ mod m=w,,a,-' mod
`m+2 wla,’ mod m+4 wza," mod m+ .
`.
`. +2!‘-1
`wk_1a,~' mod In.
`To multiply w times ai’, if the rightmost bit, contain
`ing w,, of the W register 51 is 1 then the contents of the
`A’ register 53 are added to the P register 54 by adder 55.
`If w,,=0, then the P register 54 is unchanged. Then the
`M and P register contents are compared by comparator
`56 to determine if the contents of the P register 54 are
`greater than or equal to m, the contents of the M regis
`ter 53. If the contents of the P register 54 are greater
`than or equal to m then subtractor 57 subtracts m from
`the contents of the P register 54 and places the differ
`ence in the P register 54, if less than m the P register 54
`is unchanged.
`
`FIG. 4 depicts an implementation of an adder 42 or 55
`for adding two k bit numbers p and z. The numbers are
`presented one bit at a time to the device, low order bit
`?rst, and the delay element is initially set to 0. (The
`delay represents the binary carry bit.) The AND gate 61
`determines if the carry bit should be a one based on p;
`and 2,‘ both being 1 and the AND gate 62 determines if
`the carry should be 1 based on the previous carry being
`a l and one of p; or 2; being 1. If either of these two
`conditions is met, the OR gate 63 has an output of 1
`indicating a carry to the next stage. The two exclusive
`or (XOR) gates 64 and 65 determine the i‘'' bit of the
`sum, s,-, as the modulo-2 sum of p,-, z.- and the carry bit
`from the previous stage. The delay 66 stores the previ
`ous carry bit. Typical parts for implementing these
`gates and the delay are SN7400, SN7404, and SN7474.
`FIG. 5 depicts an implementation of a comparator 44
`or 56 for comparing two numbers p and m. The two
`numbers are presented one bit at a time, high order bit
`?rst. ‘If neither the p<m nor the p>m outputs have
`been triggered after the last bits pa and mo have been
`presented, then p=m. The ?rst triggering of either the
`p<m or the p>m output causes the comparison opera
`tion to cease. The two AND gates 71 and 72 each have
`one input inverted (denoted by a circle at the input). An
`SN7400 and SN7404 provide all of the needed logic
`circuits.
`FIG. 6 depicts an implementation of a subtractor 57
`for subtracting two numbers. Because the numbers sub
`tracted in FIG. 3 always produce a non-negative differ
`ence, there is no need to worry about negative differ
`ences. The larger number, the minuend, is labelled p and
`the smaller number, the subtrahend, is labelled m. Both
`p and m are presented serially to the subtractor 57, low
`order bit ?rst. AND gates 81 and 83, OR gate 84 and
`XOR gate 82 determine if borrowing (negative carry
`ing) is in effect. A borrow occurs if either p,'=0 and
`m,~= l, or p;=m; and borrowing occurred in the previ
`ous stage. The delay 85 stores the previous borrow
`state. The ith bit of the difference, d,-, is computed as the
`XOR, or modulo-2 difference, of pr, mi and the borrow
`bit. The output of XOR gate 82 gives the modulo~2
`
`i W (in binary)
`0 0011]
`I
`00011
`2 0000]
`3 00000
`
`65
`
`12
`
`

`

`U
`
`lllO
`0110
`0010
`
`V
`
`1000
`0100
`-
`
`counter
`
`1
`0
`halt
`
`q,
`
`l
`l
`-
`
`S’
`
`bsmod m
`1312“ mod 257
`II II II II II ,_. M
`
`which implies that x=(0, l, l, 0). This is because
`
`(10)
`
`(ll)
`(l2)
`(13)
`
`(14)
`
`It is seen that q= ll in binary form and is equivalent to
`q=3, and that r=00l0 in binary form and is equivalent
`to r= 2.
`Another method for generating a trap door knapsack
`vector a uses the fact that a multiplicative knapsack is
`easily solved if the vector entries are relatively prime.
`Given a'=(6, 11, 35, 43, 169) and a partial product
`P=2838, it is easily determined that P=6"ll‘43 be
`cause 6, 11 and 43 evenly divide P but 35 and 169 do
`not. A multiplicative knapsack is transformed into an
`additive knapsack by taking logarithms. To make both
`vectors have reasonable values, the logarithms are
`taken over GF(m), the Galois (?nite) ?eld with m ele
`ments, where m is a prime number. It is also possible to
`use non-prime values of m, but the operations are some
`what more difficult.
`A small example is again helpful. Taking n=4,
`m =257, a'=(2, 3, 5, 7) and the base of the logarithms to
`be b= 131 results in a=(80, 183, 81, 195). That is
`13l3°=2 mod, 257; l3ll33=3 mod 257; etc. Finding
`logarithms over GF (m) is relatively easy if m-l has
`only small prime factors.
`Now, if -the deciphering device 16 is given
`S = 183 + 81:264, it uses the deciphering key D consist
`ing of m, a’ and b, to compute
`
`4,218,582
`10
`9
`difference between piand rm, and XOR gate 86 takes the
`cut iteration the remainder, r, is in the U register. The
`following sequence of register contents helps in follow
`modulo-2 difference of this with the previous borrow
`ing these operations.
`bit. Typical parts for implementing these gates and the
`delay are SN7400, SN7404 and SN7474.
`The deciphering device 16 is depicted in FIG. 7. It is
`given the ciphertext S, and the deciphering key consist
`ing of w, m and a’, and must compute x.
`To compute x, ?rst, w and m are input to a modulo m
`invertor 91 which computes w-1 mod m. It then uses
`the modulo rn multiplier 92 to compute S'=w—1 S mod
`in. As noted in equations (7) and (8), S'=a"'x, which is
`easily solved for x. The comparator 93 then compares S’
`with an’ and decides that xn=l if S’ 2a,,‘ and that xn=0
`if S'<a,,'. If x,,= l, S’ is replaced by S'—a,.’, computed
`by the subtractor 94. If x,.=0, S’ is unchanged. The
`process is repeated for a,,_1’ and x,,_1 and continues
`until x is computed. The j register 95 is initially set to n
`and is decremented by I after each stage of the deci
`phering process until j=0 results, causing a halt to the
`process and s