`
`[45]
`
`4,405,829
`
`Sep. 20, 1983
`
`Primary Examiner—Sal Cangialosi
`Attorney, Agent, or Firm—Arthur A. Smith, Jr.; Robert
`J. Horn, Jr.
`
`[57]
`
`ABSTRACI‘
`
`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
`
`United States Patent
`
`09]
`
`Rivest et al.
`
`[54] CRYPTOGRAPHIC COMMUNICATIONS
`SYSTEM AND METHOD
`
`[75]
`
`Inventors: Ronald L. Rivest, Belmont; Adi
`Shamir, Cambridge; Leonard M.
`Adleman, Arlington, all of Mass.
`Massachusetts Institute of
`Technology, Cambridge, Mass.
`
`{'73} Assignee:
`
`[21] App]. No.: 860,586
`
`[22] Filed:
`
`Dec. 14, 1977
`
`l~{04K 1/00; H041 9/04
`Int. cu ......................... ..
`[51]
`........ .. 17s/22.1; 178/22.11
`][52]
`[58] Field of Search ................... .. 178/22, 22.1, 22.11,
`178/22.14, 22.15
`
`
`
`![56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`3,657,476 4/1972 Aiken .................................. .. 178/22
`
`OTHER PUBLICATIONS
`
`“New Directions in Cryptography”, Diffie eta1., 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 a1., Multi—User Cryptographic Techniques”,
`AFIPS. Conference Proceedings, vol. 45, pp. 109-112,
`Jun. 8, 1976.
`
`
`
`COMMUNICATIONS CHANNEL
`
`
`
`
`
`
`
`
`ENCODING
`DEVICE
`
`BLOCKING
`SUBSYS
`
`DECODING
`DEVICE
`
`A
`
`MESSAGE
`
`M‘, (=MESSAGE)
`
`Petitioner Apple - Ex. 1023, p. 1
`
`Petitioner Apple - Ex. 1023, p. 1
`
`
`
`U.S. Patent
`
`Sep.20,1983
`
`Sheet 1 of3
`
`4,405,829
`
`
`
`COMMUNlCAT|ONS CHANNEL
`
`
`
`
`
`TERMINAL B
`
`(EB ,oB)
`
`
`
`
`
`
`
`DEVICE
`
`E
`
`ENCODING
`KEY
`
`ENCODING
`DEVICE
`
`
`
`DECODING
`KEY
`
`DECODING‘
`
`
`
`
`Petitioner Apple - Ex. 1023, p. 2
`
`Petitioner Apple - Ex. 1023, p. 2
`
`
`
`U.S. Patent
`
`Sep. 20, 1983
`
`Sheet 2 of 3
`
`4,405,829
`
`MESSAGE
`
`ENCODING KEY (e,n)
`
`M
`
`e
`
`n
`
`
` n REGISER
`
`M REGISTER
`
`e REGISTER
`
`
`
`20
`
`IE
`
`
`
`
`
`
`
`e SHIFT
`REGISTER
`
`SELECTOR
`
` MorC
`
`PRESET
`
`
`C REGISTER
`320
`
`
`MULTIPLIER
`
`(MOD n)
`
`F|G_ 3 CIPHER TEXT c
`
`
`
`ENCODINGI
`KEY
`
`v NCODING
`DEVICE
`
`( E 3 )
`
`DECODING
`DEVICE
`
`|DECODING
`KEY
`
`
`COMMUNICATIONS CHANNEL
`
`
`
`DECODING
`DEVICE
`
`RMINALI
`
`
`
`ENCODING
`DEVICE
`
`TERMEINAL:
`
`MA
`
`FIG. 5
`
`M2 W
`
`Petitioner Apple - Ex. 1023, p. 3
`
`Petitioner Apple - Ex. 1023, p. 3
`
`
`
`U.S. Patent
`
`Sep. 20, 1983
`
`Sheet 3 of3
`
`4,405,829
`
`0
`
`COMMUNICATIONS CHANNEL
`
`CA5
`
`CB5
`
`CA5
`
`Bs
`
`IIZB— ‘ _ _ ‘ ——I?aI
`I723____ _ —I4KI
`I
`DECODINGI DECODING
`ENCODING IENCODING
`ENCODINGI
`ENCODING
`DECODING
`IDECODING
`KEY I
`DEVICE
`DEVICE
`I
`KEY
`(KEEYM
`DEVICE
`DEVICE
`I
`KEY
`(De)
`I M
`M
`I
`(EA)
`3
`M
`M
`(DA)
`I
`As
`85 I
`I
`As
`Bs
`|
`DECODING DECODING
`ENCODING IENCODING ENCODINGI NCODING
`DECODING
`IDECODING
`KEY I
`DEVICE
`DEVICE
`KEY
`KEY
`I
`DEVICE
`DEVICE
`I
`KEY
`I
`IDA)
`(EB)
`(EA)
`I
`|
`(D I
`I40A
`TERMINAL
`42“
`I423
`TERMFIINAL
`4OBI
`8
`
`MA
`
`MI; (=MB)
`
`MA (= MA)
`
`MB
`
`IO
`
`COMMUNICATIONS CHANNEL
`
`CA5
`IE? ____ '"I
`ENCODING I
`ENCODING
`I
`KEY
`DEVICE
`I
`(EB)
`II
`I
`I
`MAs
`I
`I63
`BLOCKING
`I
`I
`sussvs
`I
`I
`MAS
`I
`I4OA
`DECODING
`I
`DECODINGI
`DEVICE
`I
`KEY
`I
`-
`I
`IDA)
`MA
`I
`IGI
`BLOCKING
`I
`I
`sussvs
`I
`I
`TERMINA
`I
`_____ _A_
`
`'
`
`CA5
`IITIET """ _"I
`I
`DECODING
`I DECODING.
`I
`DEVICE
`I
`KEY
`I
`II
`(DB)
`I65
`MAS
`I
`I
`UNBLOCKING
`I
`I
`suesvs
`I
`I425
`MAS
`I
`I
`- ENCODING
`IENCODING
`I
`DEVICE
`I
`KEY
`|
`(EA)
`I6?
`A
`I
`I
`UNBLOCKING
`I
`sussvs
`I
`I
`TERMINALI
`I________B____I
`
`I7’
`
`MESSAGE
`
`M'A (=MEssAGE)
`
`FIG. 7
`
`Petitioner Apple - Ex. 1023, p. 4
`
`Petitioner Apple - Ex. 1023, p. 4
`
`
`
`1
`
`4,405,829
`
`CRYPTOGRAPHIC COMMUNICATIONS SYSTEM
`AND METHOD
`
`The Government has rights in this invention pursuant
`to Contract No. NOOOI4-67-A-0204, awarded by the
`Department of the Navy, and Grant No. MCS76-14249,
`awarded by the National Science Foundation.
`
`BACKGROUND OF THE DISCLOSURE
`
`IO
`
`15
`
`25
`
`30
`
`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 E,-;(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 BA 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 EA in a
`practical way, only user A can decipher the message
`
`Petitioner Apple - Ex. 1023, p. 5
`
`Petitioner Apple - 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 E3, 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/l(M))=M
`
`E.-i(D.4(M)):=M
`
`D1;(E3(M)) : M
`
`E;;(D,:,»(M)):M
`
`10
`
`I5
`
`20
`
`25
`
`30
`
`35
`
`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 M5=D,4(M).
`User A then uses user B‘s encryption key E}; (from the
`public file)
`to generate a signed ciphertext word
`C_,«=E/3(M,,):E;3(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 Dg(C_,)=D3(E3(M,~))=M,-. Now
`using user A’s encoding key EA (available from the
`public file), user B decodes the signed message word in
`accordance with E,;(M_.v)= EA): M.
`User A cannot deny having sent user B this message,
`since no one but A could have created M,=D,;(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
`
`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-5 M -in -
`l
`
`where n is a composite number of the form
`
`’7=P'lI
`ps where p and q are prime numbers.
`For messages represented by numbers outside the
`range 0 to n-1, 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 it 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 O(EO
`mod 3), lO(El mod 3), and 8(E2 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
`
`C=—~:M"(mnd n)
`
`where e is a number relatively prime to (p— 1)-(q-1).
`_ The particular decoding device is also coupled to the
`channel and is 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
`
`Petitioner Apple - Ex. 1023, p. 6
`
`Petitioner Apple - 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(mod(1
`where d is
`»‘m((p— 1). (q~1)))) so that
`
`e-da l(mod(l cm((p — l).(q — l))))
`
`where l cm((p— l),(q— 1)) is the least common multiple
`of numbers p——l and q— 1.
`_.
`With these encoding and decoding devices, a message
`sent from the encoding device to the decoding device is
`transformed from M to C by the encoding device, and
`then back from C to M’ by the decoding device, where
`M'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 C5 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 =(d,;, nA). Similarly, the terminal for user B includes
`an encoding device characterized by an encoding key
`EA =(eA, n,;) and a decoding device characterized by a
`decoding key D3=(dg, n;;). 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,a=.M"-“(mod n_.[)
`
`and then transforms that signed message word to a
`signed ciphertext word C,-:
`
`C,'—-=M,“3(mod n3)
`
`which is then transferred to user B. User A may readily
`use d,4 and n,4 from his own decoding key to reduce the
`signed ciphertext word to a signed message word, and
`then perform the encoding transformations using eg and
`n3 from the publicly available file.
`User B deciphers the received C_,- into the signed
`message word M, in accordance with
`
`M.E(C;)‘”’(mnd nu)-
`
`User B then transforms M, to M in accordance with
`
`M -1’ M ,"*‘(mod n4).
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`50
`
`55
`
`60
`
`65
`
`6
`User B may readily perform his decoding transforma-
`tions since dB and X13 are part of his decoding key and
`e,'4 and n,4 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
`block 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 blockis
`representative of a number in the range 0 ton-3]-'1 for
`the corresponding terminal. Following 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-
`tor. Signatures cannot be forged and the signer canno
`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 DESCRIPTIONOF 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 Apple - Ex. 1023, p. 7
`
`Petitioner Apple - 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
`
`I0
`
`20
`
`25
`
`30
`
`35
`
`40
`
`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(def1ned 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 this 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-1)-(q,~— l), and d,-is a multi-
`plicative inverse of e,(mod(1 cm((p,-—- 1), (q,-—1)))). By
`way of example, d; can be a multiplicative inverse of
`e.(mod(pz—1)-(qz— 1))
`The encoding transformation performed by the i"'
`terminal encoding device for a message destined for the
`j”' terminal is in accordance with the relation:
`
`C,-:~:M,"l(mod n/-).
`
`The message M,-is a number in the range 0§M,-§n,-— 1.
`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”' terminal, and then
`recombining the blocks at thej”’ terminal. The decoding
`transformation performed by the j"' terminal decoding
`device for the ciphertext received from the i”’ terminal
`is in accordance with the relation:
`
`M,'EC,‘-’I(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 0§M,;§-
`nA—l and terminal A transforms the message MA to
`M4,, in accordance with:
`
`M/nEM.4""(m0d 11.4)
`
`Petitioner Apple - Ex. 1023, p. 8
`
`Petitioner Apple - Ex. 1023, p. 8
`
`
`
`4,405,829
`
`9
`and terminal B transforms the received signed message
`MA, back to M4 in accordance with:
`
`MAEMAx""‘(mod HA)-
`
`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 I 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 l) or binary 1 (if the currently
`applied e word bit is O) as the second input of multiplier
`32, and the multiplier 32 is activatedto 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 representa