United States Patent 1191
`Rivest et a1.
`
`[11]
`[45]
`
`4,405,829
`Sep. 20, 1983
`
`{73] Assignee:
`
`[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.
`[211 App]. No.: 860,586
`[22] Filed:
`Dec. 14, 1977
`[51] Int. c1.3 ......................... ..11041< 1/00;11o419/o4
`[s2] U.S.Cl. ............................... ..17s/22.1;17s/22.11
`[58] Field of Search ................... .. 178/22, 22.1, 22.11,
`l78/22.l4, 22.15
`
`1[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`3,657,476 4/1972 Aiken .................................. .. 178/22
`
`OTHER PUBLICATIONS
`“New Directions in Cryptography”, Dif?e 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.
`“Dif?e 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.
`
`ABSTRACT
`[57]
`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 ?rst encoding the message as
`a number M in a predetermined set, and then raising that
`number to a ?rst predetermined power (associated with
`the intended receiver) and ?nally 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
`
`E
`
`.
`
`/|o
`I
`COMMUNICATIONS CHANNEL
`L
`______:°2__
`_ ___FA_S __
`:IZAL
`:
`:|4121_1
`:
`DECODING
`I DECODING
`ENCODING
`ENCODING
`DEVICE
`(KEY)
`‘I ' DEVICE
`:
`|
`'|
`(KDEY)
`1M ‘As
`5
`leew
`|
`:esq
`|
`i/M'ks
`B
`|
`BLOCKING
`l
`l
`UNBLOCKING
`|
`I
`SUBSYS
`|
`I
`SUBSYS
`|
`|4OA-\
`f/MA,
`:
`‘4215-,
`1714A,
`:
`ENCODING I ENCODING
`|
`DECODING
`DECODING I
`(K511)
`| '
`DEVICE
`:
`|
`DEVICE
`|
`(KEEY)
`A
`|
`A
`:SIq
`i’MA
`|
`I671 MA I
`I
`BLOCKING
`l
`'
`UNBLOCKING
`I
`suBsYs
`I
`I
`SUBSYS
`1
`'
`I TERMINA
`:
`TERMINAL:
`
`_________
`
`______B__
`
`MESSAGE
`
`11
`M'A (=MESSAGE)
`
`GROUPON - EXHIBIT 1006
`
`

`

`US. Patent Sep. 20, 1983
`
`Sheet 1 of3
`
`4,405,829
`
`‘JIO
`COMMUNICATIONS CHANNEL
`
`I
`TERMINAL A
`(EA,DA)
`
`TERMINAL 8
`(EB,DB)
`
`MA M‘B
`
`MB M'A
`
`FIG. I
`
`I0
`(J
`COMMUNICATIONS CHANNEL
`
`ENCODING
`KEY
`
`I
`I
`ENCODING
`I
`|
`DEVICE
`I '
`TERMINALl
`I
`|____ _;_\__|
`
`MA
`
`:
`
`I
`I
`DECODING
`DEVICE
`" |
`‘TERMINALI
`I
`|_________B__|
`
`DECODING
`KEY
`
`I
`
`I
`
`MA (=MA)
`
`FIG. 2
`
`

`

`U.S. Patent Sep. 20, 1983
`
`Sheet 2 Of 3
`
`4,405,829
`
`MESSAGE
`
`T
`
`M REGIsTER
`
`zo/
`
`ENCODING KEY (e,n)
`L i
`
`f
`
`I
`I
`
`e REGISTER
`
`e SHIFT
`REGISTER
`
`n
`
`‘22
`26
`
`n REGISTER
`
`24/
`
`V28
`I
`T__—,———> SELECTOR _
`MM MC
`-—> MULTIPLIER ~32
`> (MOD n)
`
`0
`I
`
`I_2_
`
`I=REsET——> C REGIsTER
`
`so
`
`q
`320
`
`V
`FIG. 3 CIPHER TEXT 0
`IO
`r
`COMMUNICATIONS CHANNEL
`VCB
`'ICA
`CA
`|EA__ ______FIKI
`"-2;- ______ _—
`f
`'\
`ENCODING| ENCODING
`DECODING IIIDECODING ENCODINGI ENCODING
`DECODING lDECODING
`KEY
`DEVICE
`DEVICE
`KEY
`KEY I
`DEVICE
`DEvICE
`KEY
`“58) I
`TERMINAL
`I
`(DA)
`(EA) I
`TERMINAL
`I
`(DB)
`I ____ __A_______I
`I ____ __B_____I
`
`MA
`
`v
`MIBI=MBI
`
`MB
`
`1
`MIA (=MAI
`
`F _ 4
`[I0
`1
`COMMUNICATIONS CHANNEL
`I
`____‘:°is__
`____TI“_AS___
`l
`fI2A|
`|I4Bq
`l
`ENCODING I
`ENCODING
`|
`l
`DECODING
`I DECODING
`(IEEY)
`II ’ DEVICE
`:
`|
`DEvICE ‘ I
`(KD'E"'Y‘)“"
`B
`~
`I
`B
`I
`MAS
`40A
`l
`42B
`MA
`I
`P‘I f
`i
`|
`7
`s
`|
`DECODING I
`DECODING
`|
`ENCODING
`I ENCODI G
`KEY I
`DEVICE
`|
`DEvICE
`l
`KEY
`I
`IDA I
`I
`RNKNAL}
`:
`TERMINAL:
`(EA I
`
`I
`
`v
`
`MA
`
`F|G_ 5
`
`I
`
`II
`
`MA(=MA)
`
`

`

`US. Patent Sep. 20, 1983
`
`Sheet 3 Of3
`
`4,405,829
`
`)0
`COMMUNICATIONS CHANNEL
`A’ CBS
`cAs
`
`CA5“.
`
`Ir/cas
`
`:I2A1
`
`(MA:
`
`{I43
`
`fIZB:
`
`ENCODING IENCODING
`DECODING DECODING DECODING DECODING
`ENCODING ENCODING
`DEVICE ‘I KEY
`DEVICE ‘I KEY
`' KEY I’ DEVICE
`‘KEY I’ DEVICE
`I
`|
`(E I
`(DA)
`(D) l
`IE II
`'“MBs |
`A
`rMBs |
`B
`| Mid
`B I MQT
`DECODING IDECODING
`ENCODING IENCODING ENCODINGI ENCODING
`DECODING| DECODING
`DEVICE ':
`(KEY)
`DEVICE ‘II (KEY)
`(KEY) I" DEVICE
`(KDEY)
`DEVICEI
`A
`TERMINAL
`I
`EB
`EA I /
`TERMINAL
`DB
`‘105) __A _ _42_AI
`I2B_
`_B____Z‘EBI
`
`MA
`
`MIB (=MB)
`
`M'A (= MA)
`
`MB
`
`L
`
`IO /
`COMMUNICATIONS CHANNEL
`
`_____°A~=» _ _
`
`KEY)
`5
`
`(E
`
`I
`
`|I2Aq
`|
`I
`I
`ENCODING
`ENCODING
`lI ’ DEVICE
`:
`I63
`I/M'AS
`|
`|
`BLOCKING
`I
`I
`SUBSYS
`I
`|4OA’\
`DMAS
`i
`DECODINGI
`DECODING
`(KDEY) |'
`DEVICE
`:
`A
`:Glq
`I/MA
`|
`BLOCKING
`I
`I
`l
`SUBSYS
`I
`I
`TERMINAL1
`_____ _A_
`
`_ _ _ ___"A_~@»__
`
`DECODING
`
`III
`
`'
`
`DECODING .
`
`(KEY)
`B
`
`D
`
`|I4B
`|
`l
`I
`DEVICE
`l
`|
`IMAS
`:esq
`I
`I
`UNBLOCKING
`I
`I
`SUBSYS
`|
`|42Bq
`I'M,‘s
`:
`|
`- ENCODING
`, ENCODING
`|
`DEVICE
`|
`(KEEY)
`|
`I671
`#MA
`|
`A
`I
`UNBLOCKING
`|
`I
`SUBSYS
`I
`TERMINALI
`I________B__I
`
`MESSAGE
`
`FIG. 7
`
`v
`M'A (=MEssAGE)
`
`

`

`1
`
`4,405,829
`
`CRYPTOGRAPHIC COMMUNICATIONS SYSTEM
`AND METHOD
`
`The Government has rights in this invention pursuant
`to Contract No. N000l4-67-A-0204, awarded by the
`Department of the Navy, and Grant No. MCS76-l4249,
`awarded by the National Science Foundation.
`
`l0
`
`25
`
`35
`
`40
`
`BACKGROUND OF THE DISCLOSURE
`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 veri?cation 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 ?rst 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 de?ned 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
`
`55
`
`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 toobtain 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 '
`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 Dif?e 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 ?le an enciphering operator, or key,
`EA. User A keeps to himself the details of the corre
`sponding deciphering key DA which satis?es the equa
`tion
`
`DAiE/iiM )) =- M.
`
`for any message M. In order for the public key system
`to be practical, both EA and DA must be ef?ciently
`computable. Furthermore, user A must not compromise
`DA when revealing EA. That is, it should not be compu
`tationally feasible for an eavesdropper to ?nd an ef?
`cient way of computing DA, given only a speci?cation
`of the enciphering key EA (even though a very inef?
`cient way exists: to compute DA(C), just enumerate all
`possible messages M until one such that E,-;(M)=C is
`found. Then D,4(C)=M.). In a public key system, a
`judicious selection of keys ensures that only user A is
`able to compute DA ef?ciently.
`Whenever another user (e.g. user B) wishes to send a
`message M to A, he looks up BA in the public ?le and
`then sends the enciphered message E,4(M) to user A.
`User A deciphers the message by computing DA.
`(E,4(M))=M. Since DA is not derivable from E4 in a
`practical way, only user A can decipher the message
`
`

`

`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 ?le.
`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 ?le.
`The public key approach of Dif?e 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 identi?ed 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 ?nal product.
`In order to implement signatures on messages trans
`ferred between two users, e.g. user A and user B, in
`accordance with the Dif?e and Hellman system, each
`user has encoding keys EA and EH, respectively, on a
`public ?le and decoding keys DA and DB, 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:
`
`20
`
`25
`
`35
`
`Accordingly, it is an object of this invention to pro
`vide a system and method for implementing a private
`communlcatlons 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
`Briefly, the present invention includes at least one
`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
`
`05 M in —
`
`l
`
`where n is a composite number of the form
`
`"=P-q
`ps where p and q are prime numbers.
`For messages represented by numbers outside the
`range 0 to n- 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 speci?ed 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 n 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(~—~=0
`mod 3), 10(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 speci?ed range
`and are intended to be embraced by the claims.
`The transformation provided by the encoding device
`is described by the relation
`
`where e is a number relatively prime to (p— l)-(q- l).
`_ 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
`
`45
`
`:
`for any message M.
`When user A wants to send user B a “signed” docu
`ment M, user A ?rst uses his own decryption key D4 to
`transform M into a signed message word MS:D,4(M).
`User A then uses user B‘s encryption key EB (from the
`public ?le) to generate a signed ciphertext word
`C_,=EB(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 DB(C_,):D3(EB(M,,~))=My. Now
`using user A’s encoding key EA (available from the
`public ?le), user B decodes the signed message word in
`accordance with E,,|(M,): E,;): 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 E 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
`
`

`

`M'Ecdmod n)
`
`where d is a multiplicative inverse of e(mQd(1
`UmKP- 1), (q— I)))) so that
`
`where l cm((p— l),(q— l)) 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 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 M_,.
`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 EB=(eB, ng)vand at least one
`decoding device, characterized by a decoding key
`DA =(dA, nA). Similarly, the terminal for user B includes
`an encoding device characterized by an encoding key
`EA =(eA, M) and a decoding device characterized by a
`decoding key D3=(dg, ha). 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 ?rst
`generates a ciphertext signed message word M,Y
`
`25
`
`30
`
`35
`
`4,405,829;v
`6
`5
`User B may readily perform his decoding transforma—
`form of C (i.e. reconstituted plaintext) and corresponds
`tions since dB and m; are part of his decoding key and
`to the relation
`.
`e}; and n,; are readily available on the public ?le.
`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 tansfor‘med,
`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-311 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 ?rst
`produces Eg(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, E4 and C but without access to D3
`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 ?le 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.
`
`and then transforms that signed message word to a
`signed ciphertext word Cs:
`
`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 e}; and
`m; from the publicly available ?le.
`User B deciphers the received C,- into the signed
`message word M, in accordance with
`
`55
`
`60
`
`Mtg?jsi’mtmnd n”)
`
`User B then transforms M, to M in accordance with
`
`65
`
`M E M t""(mod n4).
`
`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
`
`

`

`4,405,829
`
`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.
`
`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, EB (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, DB (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; speci?cally associated with that terminal,
`and the decoding key is a pair of positive integers diand
`niwhere d,~is also speci?cally associated with that termi
`nal. In accordance with the invention, n; is a composite
`number equal to the product of prime factors pi and q;,
`e,- is relatively prime to (Pi— l)-(q,~— l), and d,-is a multi
`plicative inverse of e,(mod(1 cm((p,'- l), (q,-—1)))). By
`way of example, d; can be a multiplicative inverse of
`ei(m0d(Pi—1)'(qi— 1)).
`The encoding transformation performed by the i'''
`terminal encoding device for a message destined for the
`j''1 terminal is in accordance with the relation:
`
`CiEMf’Kmod 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'" terminal, and then
`recombining the blocks at thej'h terminal. The decoding
`transformation performed by the 1''" terminal decoding
`device for the ciphertext received from the ill’ terminal
`is in accordance with the relation:
`
`Accordingly, the encoding device 12 and decoding
`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 021m;
`n/1—l and terminal A transforms the message MA to
`M4,- in accordance with:
`
`25
`
`35
`
`45
`
`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 EB, DB, 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 ?gures, 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 (eg 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
`
`55
`
`60
`
`65
`
`

`

`MAEMArMIITIDd M)
`
`25
`
`35
`
`4,405,829
`9
`10
`and terminal B transforms the received signed message
`sponding to the deciphered message M’, and the blocks
`MA, back to M4 in accordance with:
`corresponding to blocks 26, 28 and 32 perform the same
`functions in their corresponding elements in the encod
`ing device 12, but for the numbers d and n. As in the
`encoding device 12, timing control circuitry is adapted
`to control the sequential operation of those elements in
`the manner described. The device of FIG. 3 is also
`suitable for the signed message mode of operation, with
`the substitution of the appropriate encoding and decod
`ing keys.
`The communications system illustrated in FIG. 2 is
`suitable for one-directional communicating» messages
`from terminal A to terminal B. FIG. 4 illustrates a simi
`lar configuration which accommodates the two-way
`transmission of messages between terminals A and B. In
`a similar manner, additional terminals may be added to
`the network (with suitable selection of encoding keys
`for each desired communication) and coupled to the
`communications channel 10 by way of conventional
`modulator and demodulator networks and terminal
`addressing networks to control the appropriate ?ow of
`messages from originating terminal to a desired receiv
`ing terminal.
`In the FIG. 4 configuration, separate encoding and
`decoding devices are shown for each terminal. How
`ever, as noted above, the encoding and decoding de
`vices perform substantially the same functions but with
`different input message and