United States Patent
`
`119]
`
`Rivest et a1.
`
`[11]
`
`[45]
`
`4,405,829
`
`Sep. 20, 1983
`
`[54] CRYPTOGRAPHIC COMMUNICATIONS
`SYSTEM AND METHOD
`
`[75]
`
`Inventors:
`
`{73] Assignee:
`
`Ronald L. Rivest, Belmont; Adi
`Shamir, Cambridge; Leonard M.
`Adleman, Arlington, all of Mass.
`Massachusetts Institute of
`Technology, Cambridge, Mass.
`
`[211 App]. No.: 860,586
`
`[22] Filed:
`
`Dec. 14, 1977
`
`Int. c1.3 ........................... H04K 1/00;H0419/04
`[51]
`
`.......... 178/22,]; 178/22.“
`i521
`
`[58] Field of Search ..................... 178/22, 22.1, 22.11,
`178/22.l4, 22.15
`
`![56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`3,657,476 4/1972 Aiken .................................... 178/22
`
`OTHER PUBLICATIONS
`
`“New Directions in Cryptography”, Diffie et 211., IEEE
`Transactions on Information Theory, vol. IT—22, No. 6,
`Nov. 1976, pp. 644-654.
`“Theory of Numbers” Stewart, MacMillan Co., 1952,
`pp. 133—135.
`“‘Diffie et al., Multi—User Cryptographic Techniques”,
`AFIPS. Conference Proceedings, vol. 45, pp. 109—112,
`Jun. 8, 1976.
`
`Primary Examiner—Sal Cangialosi
`Attorney, Agent, or Firm—Arthur A. Smith, Jr.; Robert
`J. Horn, Jr.
`
`[57]
`
`ABSTRACT
`
`A cryptographic communications system and method.
`The system includes a communications channel coupled
`to at least one terminal having an encoding device and
`to at least one terminal having a decoding device. A
`message-to-be-transferred is enciphered to ciphertext at
`the encoding terminal by first encoding the message as
`a number M in a predetermined set, and then raising that
`number to a first predetermined power (associated with
`the intended receiver) and finally computing the re-
`mainder, or residue, C, when the exponentiated number
`is divided by the product of two predetermined prime
`numbers (associated with the intended receiver). The
`residue C is the ciphertext. The ciphertext is deciphered
`to the original message at the decoding terminal in a
`similar manner by raising the ciphertext to a second
`predetermined power (associated with the intended
`receiver), and then computing the residue, M', when the
`exponentiated ciphertext is divided by the product of
`the two predetermined prime numbers associated with
`the intended receiver. The residue M’ corresponds to
`the original encoded message M.
`
`40 Claims, 7 Drawing Figures
`
`
`
`ENCODING
`DEVICE
`
`
`BLOCKING
`
`SUBSYS
`
`DECODING
`
`DEVICE
`
`
`
`A
`
`
`
`MESSAGE
`
`M'A (=MESSAGE)
`
`Petitioner RPX Corporation - Ex. 1023, p. 1
`
`Petitioner RPX Corporation - Ex. 1023, p. 1
`
`

`

`US. Patent
`
`Sep.20,1983
`
`Sheet 1 of3
`
`4,405,829
`
`TERMINAL B
`
`(53,03)
` ENCODING
`
`
`
`
`
`
`
`ENCODING
`KEY
`
`DEVICE
`
`TERMINAL
`A
`
`DECODING
`
`DEVICE
`
`I
`
`DECODING
`KEY
`
`FIG. 2
`
`Petitioner RPX Corporation - Ex. 1023, p. 2
`
`Petitioner RPX Corporation - Ex. 1023, p. 2
`
`

`

`US. Patent
`
`Sep. 20, 1983
`
`Sheet 2 of 3
`
`4,405,829
`
`MESSAGE
`
`ENCODING KEY (e,n)
`
`M
`
`e
`
`n
`
`
`
`
` n REGISTER
`
`M REGISTER
`
`
`
`PRESET
`
`C
`
`
`
`320
`
`I0
`
`
`
`
`DECODING
`IDECODING
`DEVICE
`KEY
`
`(03)
`
`KEY
`(DA)
`
`I
`
`
`KEY
`(EA)
`I
`
`ENCODINGI
`KEY
`IE3)
`
`MA
`
`M'B(=MB)
`
`FIG. 4
`IO
`
`
`MB
`
`M'A (=MAI
`
`
`
`
`
`DECODING
`DEVICE
`
`RMINALI
`
`ENCODING
`DEVICE
`
`TERMgNAL:
`
`MA
`
`FIG. 5
`
`M'A EMA)
`
`Petitioner RPX Corporation - Ex. 1023, p. 3
`
`Petitioner RPX Corporation - Ex. 1023, p. 3
`
`

`

`US. Patent
`
`Sep. 20, 1983
`
`Sheet 3 Of3
`
`4,405,829
`
`0
`
`COMMUNICATIONS CHANNEL
`
`CAs
`
`Cas
`
`cAs
`
`Bs
`
`IIZB_______ l2_BI
`IT2K______MIAI
`l
`DECODINGI DECODING
`ENCODING IENCODING
`ENCODINGI
`ENCODING
`DECODING
`IDECODING
`KEY I
`DEVICE
`DEVICE
`I
`KEY
`KEY
`DEVICE
`DEVICE
`I
`KEY
`(D)
`|
`I
`(E )
`{E H
`(DA)
`B
`| MAS
`M85 |
`A
`B
`I MAS
`MBs
`I
`DECODING
`DECODING
`ENCODING IENCODING ENCODINGI
`NCODING
`DECODING
`IDECODING
`(KEY)
`DEVICE
`DEVICE
`1
`(KEY)
`(KEY)
`I
`DEVICE
`DEVICE
`I
`(KEY)
`I
`DA
`EB
`EA
`|
`|
`De
`TERMINAL
`TERMINAL
`I105 __A_ _ _42_Al
`I121 _ _B____‘EB|
`
`MA
`
`M|B (=MB)
`
`MIA (= MA)
`
`MB
`
`IO
`
`COMMUNICATIONS CHANNEL
`
`_ ____Cis_______CA_s__
`|I2A
`I
`IMO
`I
`ENCODING I
`I
`I
`| DECODING.
`KEY
`|
`I
`I
`I
`(KEY)
`I 3
`I63
`I
`:65
`l
`B
`I
`|
`l
`I
`I
`I
`
`-
`
`D
`
`E )
`
`ENCODING
`DEVICE
`M"As
`BLOCKING
`SUBSYS
`
`DECODING
`DEVICE
`erlAs
`UNBLOCKING
`SUBSYS
`
`’
`
`MAs
`I4OA
`DECODING
`DECODINGI
`DEVICE
`(KEY)
`I
`.
`DA
`MA
`ISI
`BLOCKING
`I
`SUBSYS
`i
`TERMINA
`I
`________A_
`
`I
`I
`I
`I
`|
`
`I
`
`MS
`I425
`IENCODING
`I
`. ENCODING
`I
`(KEEY)
`l
`DEVICE
`I
`A
`|
`'67
`A
`I
`UNBLOCKING
`I
`l
`SUBSYS
`I
`TERMINALI
`l__ _____B____|
`
`MESSAGE
`
`M'A (=MESSAGE)
`
`FIG. 7
`
`Petitioner RPX Corporation - Ex. 1023, p. 4
`
`Petitioner RPX Corporation - Ex. 1023, p. 4
`
`

`

`1
`
`4,405,829
`
`CRYPTOGRAPHIC COMMUNICATIONS SYSTEM
`AND METHOD
`
`The Government has rights in this invention pursuant
`to Contract No. N00014-67-A-0204, awarded by the
`Department of the Navy, and Grant No. MCS76—I4249,
`awarded by the National Science Foundation.
`
`BACKGROUND OF THE DISCLOSURE
`
`IO
`
`15
`
`25
`
`3O
`
`35
`
`This invention relates to communications, and more
`particularly to cryptographic communications systems
`and methods.
`With the development of computer technology, the
`transfer of information in digital form has rapidly in-
`creased. There are many applications, including elec—
`tronic mail systems, bank systems and data processing
`systems, where the transferred information must pass
`over communications channels which may be moni-
`tored by electronic eavesdroppers. While the degree of 20
`security required may vary for various applications, it is
`generally important for all of these examples that the
`substance of particular communications pass directly
`from a sender to an intended receiver without interme-
`diate parties being able to interpret the transferred mes-
`sage.
`In addition,
`there are further instances where
`information in computer memory banks must be pro-
`tected from snoopers who have access to the memory
`through data processing networks.
`In addition to these privacy requirements, authentica-
`tion of the source of a message must often be insured
`along with the verification and security of the message
`content. For example, in banking applications, it is re-
`quired that a signed document, such as a bank draft, be
`authenticated as being actually signed by the indicated
`signator. Furthermore, in many applications, it is desir-
`able to further require safeguards against signature forg-
`ery by a message recipient.
`In the prior art, a number of cryptographic encoding
`and decoding techniques are readily available to pro-
`vide some degree of privacy and authentication for
`digital communications, for example. the data encryp-
`tion standards adopted by the National Bureau of Stan-
`dards, see Federal Register, Mar. 17, 1975, Volume 40,
`No. 52 and Aug. 1, 1975, Volume 40, No. 149.
`In general, cryptographic systems are adapted to
`transfer a message between remote locations. Such sys—
`tems include at least one encoding device at a first loca-
`tion and at least one decoding device at a second loca-
`tion, with the encoding and decoding devices all being
`coupled to a communication channel. For digital sys-
`tems, the message is defined to be a digital message, M,
`that is, a sequence of symbols from some alphabet. In
`practice,
`the alphabet
`is generally chosen to be the
`binary alphabet consisting of the symbols 0 and 1.
`Each encoding device is an apparatus which accepts
`two inputs: a message-to-be-encoded, M, and an encod-
`ing key or operator, E. Each encoding device trans-
`forms the message M in accordance with the encryption
`operator to produce an encoded version C of the mes-
`sage (which is denoted as
`the ciphertext) where
`C = E(M). The encoding key and the ciphertext are also
`digital sequences.
`Each decoding device is an apparatus which accepts
`two inputs: a ciphertext-to-be-decoded C and a decod-
`ing key or operator, D. Each decoding device trans-
`forms the ciphertext in accordance with the decryption
`operator to produce a decoded version M’ of the cipher-
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`text where M'=D(C), or M’=D(E(M)). Like the en-
`coding key, the decoding key and decoded message M’
`are also digital sequences. The encoding and decoding
`keys are selected so that M’=M for all messages M.
`In operation, a message, once encoded into cipher-
`text, is transmitted over the channel to a recipient who
`decodes the received ciphertext to.obtain the original
`message M. Thus, a recipient sees the original message
`M as the output of his decoding device.
`To a large degree, the quality of performance of a '
`cryptographic system depends on the complexity of the
`encoding and decoding devices. Regarding the problem
`of ensuring privacy of communications for a system
`where an eavesdropper can listen to every message
`transmitted on the communications channel
`(which
`might, for example, be a radio link), the effectiveness of v
`the system depends upon the ability to ensure that the
`eavesdropper is unable to understand any such over-
`heard messages. In the prior art systems, the sender and
`recipient arrange to have corresponding encoding and
`decoding keys which are kept secret from the eaves-
`dropper, so that even if the eavesdropper knows the
`construction of the encoding and decoding devices, he
`would not be able to decode the messages he hears,
`even after hearing a large number of messages. In prac-
`tice, however, this constraint results in extremely com—
`plex and correspodingly expensive equipment. A disad-
`vantage of the prior art systems results from the general
`requirement that the pre-arranged encoding and decod-
`ing keys must be delivered in a secure fashion (often by
`courier) to the sender and receiver, respectively,
`to
`enable communication through the systems.
`The "public-key cryptosystem” described by Diffie
`and Hellman, “New Directions In Cryptography",
`IEEE Transactions on Information Theory (Nov.
`1976), in principle, provides enciphered communication
`between arbitrary pairs of people, without the necessity
`of their agreeing on an enciphering key beforehand.
`The Diffie and Hellman system also provides a way of
`creating for a digitized document a recognizable, un-
`forgeable, document-dependent, digitized signature
`whose authenticity the signer cannot later deny.
`In a public-key cryptosystem, each user (e.g. user A)
`places in a public file an enciphering operator, or key,
`EA. User A keeps to himself the details of the corre-
`sponding deciphering key DA which satisfies the equa-
`tion
`
`D.4(EA(M )) =- M.
`
`for any message M. In order for the public key system
`to be practical, both EA and DA must be efficiently
`computable. Furthermore, user A must not compromise
`DA when revealing EA. That is, it should not be compu-
`tationally feasible for an eavesdropper to find an effi-
`cient way of computing DA, given only a specification
`of the enciphering key EA (even though a very ineffi-
`cient way exists: to compute DA(C), just enumerate all
`possible messages M until one such that EA(M)=C is
`found. Then DA(C)=M.). In a public key system, a
`judicious selection of keys ensures that only user A is
`able to compute DA efficiently.
`Whenever another user (e.g. user B) wishes to send a
`message M to A, he looks up 13,; in the public file and
`then sends the enciphered message EA(M) to user A.
`User A deciphers the message by computing DA.
`(EA(M))=M. Since DA is not derivable from E1 in a
`practical way, only user A can decipher the message
`
`Petitioner RPX Corporation - Ex. 1023, p. 5
`
`Petitioner RPX Corporation - Ex. 1023, p. 5
`
`

`

`4,405,829
`
`3
`E,4(M) sent to him. If user A wants to send a response to
`user B, user A enciphers the message using user B's
`encryption key EB, also available in the public file.
`Therefore no transactions between users A and B, such
`as exchange of secret keys. are required to initiate pri-
`vate communication. The only “setup" required is that
`each user who wishes to receive private communication
`must place his enciphering key E in the public file.
`The public key approach of Diffie and Hellman is
`also useful in principle to provide signed digital mes-
`sages that are both message-dependent and signer-
`dependent. The recipient of a “signed” message not
`only knOWS the message substance, but also can provide
`that the message originated from the identified sender.
`A signed message precludes the possibility that a recipi-
`ent could modify the received message by changing a
`few characters or that the recipient could attach the
`received signature to any message whatsoever. This is a
`particular problem for digital messages inasmuch as
`electronic "cutting and pasting" of sequences ofcharac-
`ters are generally undetectable in the final product.
`In order to implement signatures on messages trans—
`ferred between two users, e.g. user A and user B,
`in
`accordance with the Diffie and Hellman system, each
`user has encoding keys EA and E3, respectively, on a
`public file and decoding keys DA and D3, respectively,
`privately held. Each user's encoding and decoding keys
`must effect permutations of the same message space S,
`so that the following relation s hold:
`
`DA(E/1(M))=M
`
`E.II(D.4(M)l :- M
`
`DMEManM
`
`EMDthrM
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`4
`Accordingly, it is an object of this invention to pro-
`vide a system and method for implementing a private
`communications system.
`It is another object to provide a system and method
`for establishing a private communications system for
`transmission-of signed messages.
`It is still another object
`to provide a system and
`method for implementing a public key cryptographic
`communications system.
`It is a further object to provide a system and method
`for encoding and decoding digital data.
`‘
`SUMMARY OF THE INVENTION
`
`least One
`the present invention includes at
`Briefly,
`encoding device, at
`least one decoding device, and a
`communication channel, where the encoding and de-
`coding devices are coupled to the channel. The encod—
`ing device is responsive to an applied mesSage—to—be-
`transmitted M and an encoding key to provide a cipher-
`text word C for transmission to a particular decoding
`device. The encoding key E is a pair of positive integers
`e and n which are related to the particular decoding
`device. The message M is a number representative ofa
`message-to-be-transmitted and wherein
`0:: M in —
`l
`
`where n is a composite number of the form
`
`H=P~q
`ps where p and q are prime numbers.
`For messages represented by numbers outside the
`range 0 to 11-— l, a conventional blocking means is uti-
`lized to break the message into messageblock words
`before encoding, where each block word is representa-
`tive of a number within the specified range. Following
`subsequent decoding, the recovered block words may
`be transformed back to the original message.
`The presently described encoding device can dis-
`tinctly encode each of the 11 possible messages. In alter-
`native but equivalent embodiments, the numbers repre-
`sentative of the possible messages-to-be-transmitted
`need not be integers in the range 0 to n— l, but could be
`integers selected from each residue class modulo n. For
`example, where n = 3, the numbers representative of the
`set of messages-to-be-transmitted might include 0(EO
`mod 3), 10(21 mod 3), and 8(52 mod 3). Accordingly,
`the range limitations for n expressed hereafter in this
`application are appropriate for the numbers in the mod-
`ulo residue classes within the respective ranges, but it
`will be understood that numbers outside the range but
`selected from the appropriate residue classes are consid-
`ered to be equivalent to those within the specified range
`and are intended to be embraced by the claims.
`The transformation provided by the encoding device
`is described by the relation
`
`CaaM‘Kmod 11)
`
`where e is a number relatively prime to (p— l)(q-1).
`The particular decoding deviceIS also coupled to the
`channel andis adapted to receive the ciphertext C from
`the channel. The decoding device is responsive to the
`received ciphertext word C and a decoding key to
`transform that ciphertext to a received message word
`M’. The decoding key D is a pair of positive integers d
`and n. M'
`is a number representative of a deciphered
`
`40
`
`45
`
`50
`
`for any message M.
`When user A wants to send user B a “signed” docu—
`ment M, user A first uses his own decryption key DA to
`transform M into a signed message word MS=DA(M).
`User A then uses user B’s encryption key E3 (from the
`public file)
`to generate a signed ciphertext word
`C_,=E3(M,):EB(D,4(M)), which is sent to user B. User
`B initially uses his secret decryption key D3 to reduce
`the signed ciphertext C, to a signed message word in
`accordance with D3(C_,)=DB(EB(M,~))=MK. Now
`using user A’s encoding key EA (available from the
`public file), user B decodes the signed message word in
`accordance with EA(M,)= EA): M.
`User A cannot deny having sent user B this message,
`since no one but A could have created M§:DA(M),
`provided that DA is not computable from EA. Further-
`more, user B can show that the public key EA is neces—
`sary to extract the message M so that user B has “proof"
`that user A has signed the document. User B cannot
`modify M to a different version M‘, since then user B
`would have to create the corresponding signature
`D,1(M’) as well. Therefore user B must have received a
`document “signed” by A, which he can “prove" that A
`sent, but which B cannot modify in any detail.
`While the public-key cryptosystem principles as de—
`scribed above, and their potential use as a means of 65
`implementing digital “signatures", are known in the
`prior art, there are no practical implementations which
`are known, either with or without signature.
`
`55
`
`60
`
`Petitioner RPX Corporation - Ex. 1023, p. 6
`
`Petitioner RPX Corporation - Ex. 1023, p. 6
`
`

`

`5
`form of C (i.e. reconstituted plaintext) and corresponds
`to the relation
`
`4,405,829;
`
`M'Ecd(mod n)
`
`a multiplicative inverse of e(de(1
`where d is
`WIKP— 1), (q— 1)))) so that
`
`e-da l(mod(l cm((p — l).(q — l))))
`
`where l cm((p— 1),(q— 1)) is the least common multiple
`of numbers p——l and q—l.
`With these encoding and deCoding devices, a message
`sent from the encoding device to the decoding deviceis
`transformed from M to C by the encoding device, and
`then back from C to M’ by the decoding device, where
`EM’(mod n).
`In a communication system which is adapted to pro-
`vide digital signatures, each transmitting and receiving
`terminal is provided with both an encoding and decod-
`ing device, each device being functionally equivalent to
`the devices described above but operating on a different
`set of input words with a different key. The transmitting
`terminal decoding device transforms a message M using
`its own decoding key to generate a signed message M5.
`Then the encoding device transforms the resultant
`signed message M, with the intended receiving termi-
`nal‘s encoding key to generate signed ciphertext word
`C;. The receiving terminal’s decoding device then
`transforms the received C, with its own decoding key to
`obtain the signed message Ms, and then the encoding
`device transforms the resultant signed message with the
`transmitting terminal‘s encoding key to obtain the origi-
`nal message. For example, in a system for transmitting
`signed messages from user A to user B, the terminal for
`user A includes at least one encoding device character-
`ized by an encoding key E3=(e3, ng)vand at least one
`decoding device, characterized by a decoding key
`JDA =(dA, nA). Similarly, the terminal for user B includes
`an encoding device characterized by an encoding key
`EA =(eA, mg) and a decoding device characterized by a
`decoding key D3=(dg, n3). The encoding and decod-
`ing devices of terminals A and B are of the same form
`described above for the privacy system.
`'
`In operation, to provide a signed message, user A first
`generates a ciphertext signed message word M3
`
`M‘EMII.Al(m0d ml)
`
`and then transforms that signed message word to a
`signed ciphertext word Cs:
`
`C\'——=M,"B(mod n3)
`
`which is then transferred to user B. User A may readily
`use d4 and m: from his own decoding key to reduce the
`signed ciphertext word to a signed message word, and
`then perform the encoding transformations using es and
`n3 from the publicly available file.
`User B deciphers the received C...- into the signed
`message word M, in accordance with
`
`M.E(Codfitmod n3).
`
`User B then transforms M,- to M in accordance with
`
`M a M ,""(mod nu).
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`50
`
`55
`
`60
`
`65
`
`6
`User B may readily perform his decoding transformav
`tions since Cl]; and n3 are part of his decoding key and
`eg and nA are readily available on the public file.
`In any of the above operations, the underlying mes-
`sages may be initially encoded using conventional en-
`cryption techiques, and the subsequently decoded mes-
`sages may be decoded using a corresponding decryp-
`tion technique. The present invention may be used with
`any length messages provided that the message is bro-
`ken into suitable length blocks before encoding. For
`(example, very long messages may readily be broken
`into blocks, with each block labelled with a “this is
`black t of R” notation and transmitted after signing
`each block separately. Any word to be tansformed,
`using either the encoding or decoding key for a termi-
`nal, must be broken into blocks, wherein each block-is
`representative of a number in the range 0 ton-3]"l for
`the corresponding terminal. F0110wing transmission
`over the channel and the second transformation, the
`resultant words may readily be “unblocked”.
`The present invention provides a public key system
`for establishing private communications and also for
`providing private communications with the signature.
`A characteristic of this system is that the public revela-
`tion of the encryption key does not reveal the corre-
`sponding decryption key. As a result, couriers or other
`secure means are not required to transmit keys, since a
`message can be enciphered using an encryption key
`publicly revealed by the intended recipient. Only the
`intended recipient can decipher the message since only
`he knows the corresponding decryption key. Further-
`more, the :message can be “signed” by deciphering it
`with the privately held decryption key. Anyone can
`verify the signature using the corresponding publicly
`revealed encryption key corresponding to the origina-
`t.or Signatures cannot be forged and the signer cannot
`later deny the validity of his signature
`In other forms, the present invention may=be utilized
`with both the encoding and decoding keys secret. In
`such forms, if users A and B wish to communicate pri-
`vately over an insecure channel, they may use the chan-
`nel to transmit EA and E3 to B and A, respectively.
`Then when A wishes to send B a message M, he first
`produces E3(M)=C and sends this to B. B applies D3 to
`C to obtain M. An eavesdropper on the channel will
`have access to E3, EA and C but without access to D1;
`is unable to decode C.
`In alternative forms, the present invention may be
`utilized with the encoding and decoding devices cou-
`pled by a data path to a memory so that encoded only,
`or encoded signed, data words may be stored in the
`memory,
`thereby ensuring file integrity. In such an
`embodiment, the data path and memory are considered
`to be a communications channel coupling the encoding
`and decoding devices (which devices may be at the
`same physical location). In addition, the present system
`is suitable for use in access control systems.
`
`BRIEF DESCRIPTION'OF THE DRAWINGS
`
`The foregoing and other objects of this invention, the
`various features thereof, as well as the invention itself,
`may be more fully understood from the following de-
`scription, when-read together with the accompanying
`drawings in which:
`FIG. 1 shows in block diagram form, a communica-
`tions system in accordance with the present invention;
`FIG. 2 shows in block diagram form an embodiment
`of the system of FIG. 1 adapted to transfer enciphered
`
`Petitioner RPX Corporation - Ex. 1023, p. 7
`
`Petitioner RPX Corporation - Ex. 1023, p. 7
`
`

`

`7
`digital messages in one direction between two termi—
`nals;
`FIG. 3 shows in detailed block diagram form, the
`encoding device in the system of FIG. 2;
`FIG. 4 shows in block diagram form an embodiment
`of the system of FIG. 1 adapted to transfer enciphered
`digital messages in two directions between two termi—
`nals;
`FIG. 5 shows in block diagram form, an embodiment
`of the system of FIG.
`1 adapted to transfer signed,
`enciphered digital messages in one direction between
`two terminals:
`FIG. 6 shows in block diagram form, an embodiment
`of the system of FIG.
`1 adapted to transfer signed,
`enciphered digital messages in two directions between
`two terminals; and
`FIG. 7 shows in block diagram form, an embodiment
`of the system of FIG. 1 adapted to transfer blocked
`messages in one direction between two terminals.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`
`FIG. 1 shows an embodiment ofthe present invention
`in block diagram form. This system includes a commu-
`nications channel 10 and two terminals A and B coupled
`to the channel, where each terminal has an associated
`encoding key E and decoding key D: EA, DA. respec-
`tively, for terminal A and E3, D3, respectively, for
`terminal B. The communications channel 10 may in-
`clude, for example, a conventional broad-band cable
`with associated modulator and demodulator equipment
`at the various remote terminals to permit data transfer
`between teminals connected to the channel and the
`channel itself. The system of FIG. 1 is suitable for the
`two—way transfer of messages between terminal A and
`terminal B. Each of terminals A and B is adapted to
`transform a plaintext message to an encoded form and
`transfer the encoded message over channel 10 to the
`other terminal. When received at the other terminal, the
`encoded message is transformed back to its plaintext
`form. In the figures, the message, encoded form and
`reconstituted plaintext are represented by the symbols
`M, C, and M’, respectively, with subscripts A or B
`being representative of the originating terminal.
`In one embodiment (e.g. the system of FIG. 2 de-
`scribed below),
`the encoded form of the message is
`encrypted to ciphertext that may only be decoded by
`the intended receiver terminal.
`In a second embodi-
`ment, the encoded form is representative of a message
`combined with a digital signature indicative of the send-
`ing terminal. In a third embodiment (e.g. the system of
`FIG. 5 described below),
`the encoded form is both
`encrypted to a form intelligible only to the intended
`receiver and also signed by the sending terminal. Alter-
`native form systems may include additional
`remote
`terminals (each having associated encoding and decod-
`ing keys) coupled to the channel 10, as well as associ—
`ated terminal and channel equipment so that messages
`may be addressed to particular ones of the terminals in
`a conventional manner.
`FIG. 2 shows a form of the invention wherein mes-
`sages MA may be transferred in encrypted form in one
`direction from terminal A to terminal B. In this embodi-
`ment, terminal A includes an encoding device 12 and
`terminal B includes a decoding device 14.
`Encoding device 12 is adapted to receive an input
`message MA to be transferred to the terminal B. Mes-
`sage MA may be pre-coded by conventional encoding
`
`IO
`
`20
`
`25
`
`30
`
`35
`
`4o
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4,405,829
`
`8
`techniques to a digital form. In embodiments, where
`relatively large messages are being utilized,
`the pre-
`coded form may be in terms of short data blocks which
`may be individually encoded by the device 12 into cor-
`responding words of ciphertext CA. To establish com-
`munications with terminal B, the encoding device 12
`performs the transformation from MA to CA utilizing the
`terminal B encoding key, E3 (defined more fully be-
`low). The decoding device 14 receives ciphertext
`words CA from the channel 10 and transforms them into
`reconstituted plaintext from MA’ utilizing the terminal B
`decoding key, D3 (defined more fully below). The en-
`coding and decoding keys are adapted so that the de-
`coded message MA’ is the same as the message MA. To
`establish communication with any other terminal, the
`encoding device 12 of the sending terminal utilizes the
`encoding key associated with the intended receiver
`terminal. The decoding device 14 of the receiving ter-
`minal utilizes its own decoding key to transform the
`received ciphertext to plaintext.
`In accordance with the present invention, for the i”'
`terminal, the encoding key E, is a pair of positive inte-
`gers e,- and n; specifically associated with that terminal,
`and the decoding key is a pair of positive integers d/and
`niwhere diis also specifically associated with that termi-
`nal. In accordance with the invention, It; is a composite
`number equal to the product of prime factors pi and q,,
`e,-is relatively prime to (Pi— l)-(q,~— l), and diis a multi-
`plicative inverse of e,(mod(1 cm((p,—- l), (q,-—1)))). By
`way of example, di can be a multiplicative inverse of
`e.<mod(pi—1)-(qi— 1)).
`The encoding transformation performed by the i”1
`terminal encoding device for a message destined for the
`j”’ terminal is in accordance with the relation:
`
`CiEM,"l(mod 11/).
`
`The message M,-is a number in the range OéMiénj— I.
`This condition may be met by initially transforming, or
`pre-coding, the message-to-be-transmitted into blocks
`which are in that range at the i"1 terminal, and then
`recombining the blocks at thej’h terminal. The decoding
`transformation performed by the j"' terminal decoding
`device for the ciphertext received from the i’h terminal
`is in accordance with the relation:
`
`M,',—=C,“'1(mod 11,).
`
`the encoding device 12 and decoding
`Accordingly,
`device 14 perform substantially the same functional
`operation but with different message inputs (M or C)
`and different keys (E or D). In the present exemplary
`embodiment which transfers an encrypted message
`from terminal A to terminal B, i=A and j=B.
`The FIG. 2 embodiment is also suitable for sending
`signed messages MA, (in lieu of CA) from terminal A to
`terminal B. In this form, the system of FIG. 2 is substan-
`tially the same as that described above except that ter—
`minal A utilizes its own decoding key DA as the “encod-
`ing key” for device 12, and terminal B utilizes terminal
`A’s encoding key for the “decoding key” for device 14.
`With this configuration, MA is in the range OéMAé—
`nA—l and terminal A transforms the message MA to
`M4,- in accordance with:
`
`MmEM.-1""(m0d 11.4)
`
`Petitioner RPX Corporation - Ex. 1023, p. 8
`
`Petitioner RPX Corporation - Ex. 1023, p. 8
`
`

`

`9
`and terminal B transforms the received signed message
`MA, back to M4 in accordance with:
`
`MAEMArMII'HDd “A)-
`
`An exemplary form for the encoding device 12 is
`shown in FIG. 3. The device 12 includes an M register
`20 for receiving an "applied digital message-to-be-trans-
`ferred and e register 22 and n register 24 for receiving
`an applied encoding key consisting of binary signals
`representative of the numbers e and n for the intended
`receiver terminal (which, in a public key cryptographic
`system, are readily available from a public file for all
`terminals). Encoding device 12 further includes an e
`shift register 26, a multiplier selector 28, ciphertext
`register 30 and a modulo n multiplier 32. These blocks
`in the device 12 are conventionally arranged together
`with timing control circuitry to perform “exponentia-
`tion by repeated squaring and multiplication.” In alter-
`native embodiments, other exponentiation procedures
`may readily be utilized in keeping with the present
`invention.
`In the operation of device 12 after a message M is
`loaded into the message register 20, the ciphertext regis-
`ter 30 is preset to the number 1 and the e and n registers
`are loaded with binary words representative of the
`numbers e and n, respectively, for the intended receiver
`terminal. The shift register 26 is clocked to shift the bits
`of the e word so that one bit at a time starting with the
`most significant bit is applied to the control input of the
`multiplier selector 28. In response to each applied. e
`word bit, the current contents of C register 30 are ap-
`plied as a first input to multiplier 32. In addition, the
`selector 28 selects the contents of C register 30 as a
`second input to multiplier 32, and the multiplier 32 then
`is activated to provide an intermediate product (modulo
`n) of the signals at its first and second inputs, thereby
`effecting a squaring (modulo n) of the contents of C
`register 30. C register 30 is then updated with the inter-
`mediate product signal, which is in turn applied to the
`first input of multiplier 32. The selector 28 then selects
`either the contents of M register 20 (if the currently
`applied e word bit is I) or binary 1 (if the currently
`applied e word bit is O) as the second input of multiplier
`32, and the multiplier 32 is activated‘to provide a final
`product (modulo n) of the signals at its first and second
`inputs. The C register 30 is then updated with the final
`product signal. The e shift register is then activated to
`shift the e word by one bit so that the next e word bit is
`applied to selector 28 and the above operation repeats.
`Following the completion of the above operation for
`the last bit of the e word, the contents of the C register
`30 are representative of the ciphertext corresponding to
`the