US4405829A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cryptographic communications system and method
Assignee: Massachusetts Institute of Technology
•
Filing: 1977-12-14
•
Granted: 1983-09-20
•
Expires: 1997-12-14
Abstract
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 remainder, 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.
Inventors
- 👤 Ronald L. Rivest
- 👤 Adi Shamir
- 👤 Leonard M. Adleman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 05:18
CPC Classifications
G; G11; G11B; G11B20/00; G11B20/00086; G11B20/0021; H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302; G06; G06F; G06F2211/00; G06F2211/007
Claims Analysis
Total Claims: 52
Claim 1
Independent Claim
156 words
A cryptographic communications system comprising: A. a communications channel, B. an encoding means coupled to said channel and adapted for transforming a transmit message word signal M to a ciphertext word signal C and for transmitting C on said channel, where M corresponds to a number representative of a message and 0≦M≦n-1 where n is a composite number of the form n=p·q where p and q are prime numbers, and where C corresponds to a number representative of an enciphered form of said message and corresponds to C≡M.sup.e (mod n) where e is a number relatively prime to 1 cm(p-1,q-1), and C. a decoding means coupled to said channel and adapted for receiving C from said channel and for transforming C to a receive message word signal M' where M' corresponds to a number representative of a deciphered form of C and corresponds to M'≡C.sup.d (mod n) where d is a multiplicative inverse of e(mod(1 cm((p-1),(q-1)))).
Claim 2
Dependent Claim
156 words
A cryptographic communications system comprising: A. a communications channel, B. an encoding means coupled to said channel and adapted for transforming a transmit message word signal M to a ciphertext word signal C and for transmitting C on said channel, where M corresponds to a number representative of a message and 0≦M≦n-1 where n is a composite number of the form n=p·q where p and q are prime numbers, and where C corresponds to a number representative of an enciphered form of said message and corresponds to C≡M.sup.e (mod n) where e is a number relatively prime to 1 cm(p-1,q-1), and C. a decoding means coupled to said channel and adapted for receiving C from said channel and for transforming C to a receive message word signal M' where M' corresponds to a number representative of a deciphered form of C and corresponds to M'≡C.sup.d (mod n) where d is a multiplicative inverse of e(mod(1 cm((p-1),(q-1)))).
Claim 3
Dependent Claim
292 words
A system according to claim 1 wherein at least one of said transforming means comprises: a first register means for receiving and storing a first digital signal representative of said signal-to-be-transformed, a second register means for receiving and storing a second digital signal representative of the exponent of the equivalence relation defining said transformation, a third register means for receiving and storing a third digital signal representative of the modulus of the equivalency relation defining said transformation, and an exponentiation by repeated squaring and multiplication network coupled to said first, second and third register means, said network including: A. an output register means for receiving and storing a first multiplier signal and for applying said first multiplier signal to a first multiplier input line, B. selector means for successively selecting each of the bits of said second digital signal as a multiplier selector signal, C. means operative for each of said multiplier selector signals for selecting as a second multiplier signal either the contents of said output register means or the contents of said first register means, and for said second applying multiplier signal to a second multiplier input line, said selection being dependent on the binary value of the successive bits of said second digital signal, and D. modulo multiplier means operative in step with said selector means and responsive to said first and second multiplier signals on said first and second multiplier input lines for successively generating first multiplier signals and for transferring said first multiplier signals to said output register means, said first multiplier signal initially being representative of binary 1, and thereafter being representative of the modulo product of said first and second multiplier signals, where the modulus of said modulo product corresponds to said third digital signal.
Claim 4
Dependent Claim
185 words
A communications system for transferring message signals M i , comprising k terminals, wherein each terminal is characterized by an encoding key E i =(e i , n i ) and decoding key D i =(e i , n i ), where i=1,2, . . . ,k, and wherein Mi corrresponds to a number representative of a message signal to be transmitted from the i th terminal, and 0≦M.sub.i ≦n.sub.i -1, n i is a composite number of the form n.sub.i =p.sub.i ·q.sub.i p i and q i are prime numbers, e i is relatively prime to 1 cm(p-1,q-1), d i is a multiplicative inverse of e.sub.i (mod(1 cm((p.sub.i -1), (q.sub.i -1)))) wherein a first terminal includes means for encoding a digital message word signal M a for transmission from said first terminal (i=A) to a second terminal (i=B), said first terminal including: means for transforming said message word signal M A to a signed message word signal M As , M As corresponding to a number representative of an encoded form of said message word signal M A , whereby: M.sub.As ≡M.sub.A.sup.d.sbsp.A (mod n.sub.A).
Claim 5
Dependent Claim
185 words
A communications system for transferring message signals M i , comprising k terminals, wherein each terminal is characterized by an encoding key E i =(e i , n i ) and decoding key D i =(e i , n i ), where i=1,2, . . . ,k, and wherein Mi corrresponds to a number representative of a message signal to be transmitted from the i th terminal, and 0≦M.sub.i ≦n.sub.i -1, n i is a composite number of the form n.sub.i =p.sub.i ·q.sub.i p i and q i are prime numbers, e i is relatively prime to 1 cm(p-1,q-1), d i is a multiplicative inverse of e.sub.i (mod(1 cm((p.sub.i -1), (q.sub.i -1)))) wherein a first terminal includes means for encoding a digital message word signal M a for transmission from said first terminal (i=A) to a second terminal (i=B), said first terminal including: means for transforming said message word signal M A to a signed message word signal M As , M As corresponding to a number representative of an encoded form of said message word signal M A , whereby: M.sub.As ≡M.sub.A.sup.d.sbsp.A (mod n.sub.A).
Claim 6
Dependent Claim
292 words
A system according to claim 3 wherein at least one of said transforming means comprises: a first register means for receiving and storing a first digital signal representative of said signal-to-be-transformed, a second register means for receiving and storing a second digital signal representative of the exponent of the equivalence relation defining said transformation, a third register means for receiving and storing a third digital signal representative of the modulus of the equivalency relation defining said transformation, and an exponentiation by repeated squaring and multiplication network coupled to said first, second and third register means, said network including: A. an output register means for receiving and storing a first multiplier signal and for applying said first multiplier signal to a first multiplier input line, B. selector means for successively selecting each of the bits of said second digital signal as a multiplier selector signal, C. means operative for each of said multiplier selector signals for selecting as a second multiplier signal either the contents of said output register means or the contents of said first register means, and for said second applying muliplier signal to a second multiplier input line, said selection being dependent on the binary value of the successive bits of said second digital signal, and D. modulo multiplier means operative in step with said selector means and responsive to said first and second multiplier signals on said first and second multiplier input lines for successively generating first multiplier signals and for transferring said first multiplier signals to said output register means, said first multiplier signal initially being representative of binary 1, and thereafter being representative of the modulo product of said first and second multiplier signals, where the modulus of said modulo product corresponds to said third digital signal.
Claim 7
Dependent Claim
75 words
The system of claim 3 further comprising: means for transmitting said signal message word signal M As from said first terminal to said second terminal, and wherein said second terminal includes means for decoding said signed message word signal M As to said message word signal M A , said second terminal including: means for transforming said ciphertext word signal C A to said message word signal M A , whereby M.sub.A ≡M.sub.As.sup.e.sbsp.A (mod n.sub.A).
Claim 8
Dependent Claim
112 words
The system of claim 3 wherein said encoding means further comprises: means for transforming said sfgned message word signal M As to one or more signed message block word signals M As ", each block word signal M As " corresponding to a number representative of a portion of said signed message word signal M A in the range 0≦M As "≦n B -1, and means for transforming each of said signed message block word signals M As " to a signed ciphertext word signal C As , C As corresponding to a number representative of an encoded form of said signed message block word signal, whereby C.sub.As ≡M.sub.As ".sup.e.sbsp.B (mod n.sub.B).
Claim 9
Dependent Claim
120 words
The system of claim 6 comprising the further steps of: means for transmitting said signed ciphertext word signal C As from said first terminal to said second terminal, wherein said second terminal includes means for decoding said signed ciphertext word signals to said message word signal M A , said second terminal including: means for transforming each of said signed ciphertext word signal C As to one of said signed message block word signals M As ", whereby M.sub.As "≡C.sub.As.sup.d.sbsp.B (mod n.sub.B) means for transforming said signed message block word signals to said signed message word signal M As means for transforming said sfgned message word signal to safd message word signal M A , whereby M.sub.A ≡M.sub.As.sup.e.sbsp.A (mod n.sub.A).
Claim 10
Dependent Claim
238 words
A communications system for transferring a message signal M i comprising k terminals, wherein each terminal is characterized by an encoding key E i =(e i , n i ) and decoding key D i =(e i , n i ), where i=1,2, . . . ,k, and wherein M i corresponds to a number representative of a message signal to be transmitted from the i th terminal, n i is a composite number of the form n.sub.i =p.sub.i ·q.sub.i P i and q i are prime numbers, e i is relatively prime to 1 cm(p i -1,q i -1), d i is a multiplicative inverse of e.sub.i (mod(1 cm((p.sub.i -1),(q.sub.i -1)))) wherein a first terminal includes means for encoding a digital message word signal M A for transmission from said first terminal (i=A) to a second terminal (i=B), said first terminal including: means for transforming said message word signal M A to one or more message block word signals M A ', each block word signal M A being a number representative of a portion of said message word signal M A in the range 0≦M A ≦n B -1, means for transforming each of said message block word signals M A " to a ciphertext word signal C A , C A corresponding to a number representative of an encoded form of said message block word signal M A ", whereby: C.sub.A ≡M.sub.A ".sup.e.sbsp.B (mod n.sub.B).
Claim 11
Dependent Claim
238 words
A communications system for transferring a message signal M i comprising k terminals, wherein each terminal is characterized by an encoding key E i =(e i , n i ) and decoding key D i =(e i , n i ), where i=1,2, . . . ,k, and wherein M i corresponds to a number representative of a message signal to be transmitted from the i th terminal, n i is a composite number of the form n.sub.i =p.sub.i ·q.sub.i P i and q i are prime numbers, e i is relatively prime to 1 cm(p i -1,q i -1), d i is a multiplicative inverse of e.sub.i (mod(1 cm((p.sub.i -1),(q.sub.i -1)))) wherein a first terminal includes means for encoding a digital message word signal M A for transmission from said first terminal (i=A) to a second terminal (i=B), said first terminal including: means for transforming said message word signal M A to one or more message block word signals M A ', each block word signal M A being a number representative of a portion of said message word signal M A in the range 0≦M A ≦n B -1, means for transforming each of said message block word signals M A " to a ciphertext word signal C A , C A corresponding to a number representative of an encoded form of said message block word signal M A ", whereby: C.sub.A ≡M.sub.A ".sup.e.sbsp.B (mod n.sub.B).
Claim 12
Dependent Claim
292 words
A system according to claim 8 wherein at least one of said transforming means comprises: a first register means for receiving and storing a first digital signal representative of said signal-to-be-transformed, a second register means for receiving and storing a second digital signal representative of the exponent of the equivalence relation defining said transformation, a third register means for receiving and storing a third digital signal representative of the modulus of the equivalency relation defining said transformation, and an exponentiation by repeated squaring and multiplication network coupled to said first, second and third register means, said network including: A. an output register means for receiving and storing a first multiplier signal and for applying said first multiplier signal to a first multiplier input line, B. selector means for successively selecting each of the bits of said second digital signal as a multiplier selector signal, C. means operative for each of said multiplier selector signals for selecting as a second multiplier signal either the contents of said output register means or the contents of said first register means, and for said second applying multiplier signal to a second multiplier input line, said selection being dependent on the binary value of the successive bits of said second digital signal, and D. modulo multiplier means operative in step with said selector means and responsive to said first and second multiplier signals on said first and second multiplier input lines for successively generating first multiplier signals and for transferring said first multiplier signals to said output register means, said first multiplier signal initially being representaative of binary 1, and thereafter being representative of the modulo product of said first and second multiplier signals, where the modulus of said modulo product corresponds to said third digital signal.
Claim 13
Dependent Claim
93 words
The system of claim 8 further comprising: means for transmitting said ciphertext word signals from said first terminal to said second terminal, and wherein said second terminal includes means for decoding said ciphertext word signals to said message word signal M A , said second terminal including: means for transforming each of said ciphertext word signals C A to one of said message block word signals M A ", whereby M.sub.A ≡C.sub.A.sup.d.sbsp.B (mod n.sub.B) means for transforming said message block word signals M A " to said message word signal M A ".
Claim 14
Dependent Claim
105 words
The system of claim 8 wherein said encoding means further comprises: means for transforming said ciphertext word signal C A to one or more ciphertext block word signals C A ", each block word signal C A " being a number representative of a portion of said ciphertext word signal C A in the range 0≦C A "≦n A -1, means for transforming each of said ciphertext block word signals C A " to a signed ciphertext word signal C As corresponding to a number representative of an encoded form of said ciphertext block word signal C A ", whereby C.sub.As ≡C.sub.A ".sup.d.sbsp.A (mod n.sub.A).
Claim 15
Dependent Claim
112 words
The system of claim 11 further comprising: means for transmitting said signed ciphertext word signals from said first terminal to said second terminal, wherein said second terminal includes means for decoding said signed ciphertext word signals to said message word signal M A , said second terminal including: means for transforming each of said signed ciphertext word signals C AS to one of said ciphertext block word signals C A ", whereby C.sub.A "≡C.sub.As.sup.e.sbsp.A (mod n.sub.A) means for transforming said ciphertext block word signals to said message block word signals, whereby M.sub.A "≡C.sub.A ".sup.d.sbsp.B (mod n.sub.B) means for transforming said message block word signals to said message word signal M A .
Claim 16
Dependent Claim
226 words
A communications system having a plurality of terminals coupled by a communications channel, including a first terminal characterized by an associated encoding key E A =(e A , n A ) and decoding key D A =(d A , n A ), and including a second terminal, wherein n A is a composite number of the form n.sub.A =p.sub.A ·q.sub.A p A and q A are prime numbers, e A is relatively prime to 1 cm(p A -1, q A -1), d A is a multiplicative inverse of e.sub.A (mod(1 cm((p.sub.A -1), (q.sub.A -1)))), wherein said first terminal comprises: encoding means coupled to said channel and adapted for transforming a transmit message word signal M A to a signed message word signal M As and for transmitting M As on said channel, where M A corresponds to a number representative of a message and 0≦M.sub.A ≦n.sub.A -1 where M As corresponds to a number representative of a signed form of said message and corresponds to M.sub.As ≡M.sub.A.sup.d.sbsp.A (mod n.sub.A) wherein said second terminal comprises: decoding means coupled to said channel and adapted for receiving M As from said channel and for transforming M As to a receive message word signal M A ' where M A ' corresponds to a number representative of an unsigned form of M A and corresponds to M.sub.A '≡M.sub.As.sup.e.sbsp.A (mod n.sub.A).
Claim 17
Dependent Claim
226 words
A communications system having a plurality of terminals coupled by a communications channel, including a first terminal characterized by an associated encoding key E A =(e A , n A ) and decoding key D A =(d A , n A ), and including a second terminal, wherein n A is a composite number of the form n.sub.A =p.sub.A ·q.sub.A p A and q A are prime numbers, e A is relatively prime to 1 cm(p A -1, q A -1), d A is a multiplicative inverse of e.sub.A (mod(1 cm((p.sub.A -1), (q.sub.A -1)))), wherein said first terminal comprises: encoding means coupled to said channel and adapted for transforming a transmit message word signal M A to a signed message word signal M As and for transmitting M As on said channel, where M A corresponds to a number representative of a message and 0≦M.sub.A ≦n.sub.A -1 where M As corresponds to a number representative of a signed form of said message and corresponds to M.sub.As ≡M.sub.A.sup.d.sbsp.A (mod n.sub.A) wherein said second terminal comprises: decoding means coupled to said channel and adapted for receiving M As from said channel and for transforming M As to a receive message word signal M A ' where M A ' corresponds to a number representative of an unsigned form of M A and corresponds to M.sub.A '≡M.sub.As.sup.e.sbsp.A (mod n.sub.A).
Claim 18
Dependent Claim
292 words
A system according to claim 13 wherein at least one of said transforming means comprises: a first register means for receiving and storing a first digital signal representative of said signal-to-be-transformed, a second register means for receiving and storing a second digital signal representative of the exponent of the equivalence relation defining said transformation, a third register means for receiving and storing a third digital signal representative of the modulus of the equivalency relation defining said transformation, and an exponentiation by repeated squaring and multiplication network coupled to said first, second and third register means, said network including: A. an output register means for receiving and storing a first multiplier signal and for applying said first multiplier signal to a first multiplier input line, B. selector means for successively selecting each of the bits of said second digital signal as a multiplier selector signal, C. means operative for each of said multiplier selector signals for selecting as a second multiplier signal either the contents of said output register means or the contents of said first register means, and for said second applying multiplier signal to a second multiplier input line, said selection being dependent on the binary value of the successive bits of said second digital signal, and D. modulo multiplier means operative in step with said selector means and responsive to said first and second multiplier signals on said first and second multiplier input lines for successively generating first multiplier signals and for transferring said first multiplier signals to said output register means, said first multiplier signal initially being representative of binary 1, and thereafter being representative of the modulo product of said first and second multiplier signals, where the modulus of said modulo product corresponds to said third digital signal.
Claim 19
Dependent Claim
213 words
The system according to claim 13 wherein said second terminal is characterized by an associated encoding key E B =(e B , n B ) and decoding key D B =(d B , n B ), where: n B is a composite number of the form n.sub.B =p.sub.B ·q.sub.B p B and q B are prime numbers, e B is relatively prime to 1 cm(p B -1,q B -1), d B is a multiplicative inverse of e.sub.B (mod(1 cm((p.sub.B -1),(q.sub.B -1)))), wherein said second terminal comprises: encoding means coupled to said channel and adapted for transforming a transmit message word signal M B to a signed message word signal M Bs and for transmitting M Bs on said channel, where M B corresponds to a number representative of a message and ≦ M.sub.B ≦n.sub.B -1 where M Bs corresponds to a number representative of an enciphered form of said message signal M B and corresponds to M.sub.Bs ≡M.sub.B.sup.d.sbsp.B (mod n.sub.B) wherein said first terminal comprises: decoding means coupled to said channel and adapted for receiving M Bs from said channel and for transforming M Bs to a receive message word signal M B ' where M' is a number representative of an unsigned form of C and corresponds to M.sub.B '≡M.sub.Bs.sup.e.sbsp.B (mod n.sub.B).
Claim 20
Dependent Claim
251 words
The system according to claim 13 wherein said second terminal is characterized by an associated encoding key E B =(e B , n B ) and decoding key D B =(d B , n B ), where: n B is a composite number of the form n.sub.B =p.sub.B ·q.sub.B p B and q B are prime numbers, e B is relatively prime to 1 cm(p B -1,q B -1), d B is a multiplicative inverse of e B (mod(1 cm((p-1),(q-1)))), wherein said encoding means of said first terminal is adapted for transforming said message word signal M A to a signed ciphertext word signal C As , and for transmitting C As on said channel in place of M As whereby C As corresponds to a number representative of a signed enciphered form of said message and corresponds to: C.sub.As ≡M.sub.As ".sup.e.sbsp.B (mod n.sub.B) where M As " corresponds to a number representative of a block of said signed message word signal M As in the range 0≦M As "≦n B -1 wherein said decoding means of said second terminal is adapted to first transform said signed enciphered form of said message C As to M As in accordance with: M.sub.As '≡C.sub.As.sup.d.sbsp.B (mod n.sub.B) then to transform M As " to M As , and then to transform M As to said receive message word signal M A ', where M A ' is a number representative of a deciphered form of C As and corresponds to M.sub.A ≡M.sub.As.sup.e.sbsp.A (mod n.sub.A).
Claim 21
Dependent Claim
309 words
The system according to claim 15 wherein said encoding means of said first terminal is adapted for transforming said message word signal M A to a signed ciphertext word signal C As , and for transmitting C As on said channel in place of M As , whereby C As corresponds to a number representative of a signed enciphered form of said message and corresponds to: C.sub.As ≡M.sub.As ".sup.e.sbsp.B (mod n.sub.B) wherein said decoding means of said second terminal is adapted to first transform said signed enciphered form of said message C As to M As " in accordance with: M.sub.As "≡C.sub.As.sup.e.sbsp.B (mod n.sub.B) then to transform M As to M As , and then to transform M As to said receive message word signal M A ', where M A ' corresponds to a number representative of a deciphered form of C As and corresponds to M.sub.A '≡M.sub.As.sup.e.sbsp.A (mod n.sub.A) wherein further said encoding means of said second terminal is adapted for transforming said message word signal M B to a signed ciphertext word signal C Bs , and for transmitting C Bs on said channel in place of M Bs , whereby C Bs corresponds to a number representative of a signed enciphered form of said message and corresponds to: C.sub.Bs ≡M.sub.Bs ".sup.e.sbsp.A (mod n.sub.A) where M Bs corresponds to a number representative of a block of said signed message word signal M Bs in the range 0≦M Bs ≦n A -1, wherein said decoding means of said first terminal is adapted to first transform said signed enciphered form of said message C As to M Bs " in accordance with: M.sub.Bs "≡C.sub.Bs.sup.e.sbsp.A (mod n.sub.A) then to transform M Bs " to M Bs , and then to transform M Bs to said receive message word signal M B ', and corresponds to M.sub.B '≡M.sub.Bs.sup.e.sbsp.B (mod n.sub.B).
Claim 22
Dependent Claim
271 words
A cryptographic communications system having a plurality of terminals coupled by a communications channel, including a first terminal characterized by an associated encoding key E A =(e A ,n A ) and decoding key D A =(d A ,n A ), and including a second terminal wherein n A is a composite number of the form n.sub.A =p.sub.A ·q.sub.A p A and q A are prime numbers, e A is relatively prime to 1 cm(p A -1,q A -1), d A is a multiplicative inverse of e.sub.A (mod(1 cm((p.sub.A -1),(q.sub.A -1)))), wherein said second terminal comprises: blocking means for transforming a message-to-be-transmitted from said second terminal to said first terminal, to one or more transmit message word signals M B , where M B corresponds to a number representative of said message in the range 0≦M.sub.B ≦n.sub.A -1 encoding means coupled to said channel and adapted for transforming each transmit message word signal M B to a ciphertext word signal C B and for transmitting C B on said channel, where C B corresponds to a number representative of an enciphered form of said message and corresponds to C.sub.B ≡M.sub.B.sup.e.sbsp.A (mod n.sub.A) wherein said first terminal comprises: decoding means coupled to said channel and adapted for receiving said ciphertext word signals C B from said channel and for transforming each of said ciphertext word signals to a receive message word signal M B , and means for transforming said receive message word signals M B ' to said message, where M B ' is a number representative of a deciphered form of C B and corresponds to M.sub.B '≡C.sub.B.sup.d.sbsp.A (mod n.sub.A).
Claim 23
Dependent Claim
271 words
A cryptographic communications system having a plurality of terminals coupled by a communications channel, including a first terminal characterized by an associated encoding key E A =(e A ,n A ) and decoding key D A =(d A ,n A ), and including a second terminal wherein n A is a composite number of the form n.sub.A =p.sub.A ·q.sub.A p A and q A are prime numbers, e A is relatively prime to 1 cm(p A -1,q A -1), d A is a multiplicative inverse of e.sub.A (mod(1 cm((p.sub.A -1),(q.sub.A -1)))), wherein said second terminal comprises: blocking means for transforming a message-to-be-transmitted from said second terminal to said first terminal, to one or more transmit message word signals M B , where M B corresponds to a number representative of said message in the range 0≦M.sub.B ≦n.sub.A -1 encoding means coupled to said channel and adapted for transforming each transmit message word signal M B to a ciphertext word signal C B and for transmitting C B on said channel, where C B corresponds to a number representative of an enciphered form of said message and corresponds to C.sub.B ≡M.sub.B.sup.e.sbsp.A (mod n.sub.A) wherein said first terminal comprises: decoding means coupled to said channel and adapted for receiving said ciphertext word signals C B from said channel and for transforming each of said ciphertext word signals to a receive message word signal M B , and means for transforming said receive message word signals M B ' to said message, where M B ' is a number representative of a deciphered form of C B and corresponds to M.sub.B '≡C.sub.B.sup.d.sbsp.A (mod n.sub.A).
Claim 24
Dependent Claim
291 words
A system according to claim 18 wherein at least one of said transforming means comprises: a first register means for receiving and storing a first digital signal representative of said signal-to-be-transformed, a second register means for receiving and storing a second digital signal representative of the exponent of the equivalence relation defining said transformation, a third register means for receiving and storing a third digital signal representative of the modulus of the equivalency relation defining said transformation, and an exponentiation by repeated squaring and multiplication network coupled to said first, second and third register means, said network including: A. an output register means for receiving and storing a first multiplier signal and for applying said first multiplier signal to a first multiplier input line, B. selector means for successively selecting each of the bits of said second digital signal as a multiplier selector signal, C. means operative for each of said multiplier selector signals for selecting as a second multiplier signal either the contents of said output register means or the contents of said first register means, and for said second applying multiplier signal to a second multiplier input line, said selection being dependent on the binary value of the successive bits of said second digital signal, and (D. modulo multiplier means operative in step with said selector means and responsive to said first and second multiplier signals on said first and second multiplier input lines for successively generating first multiplier signals for transferring said first multiplier signals to said output register means, said first multiplier signal initially being representative of binary 1, and thereafter being representative of the modulo product of said first and second multiplier signals, where the modulus of said modulo product corresponds to said third digital signal.
Claim 25
Dependent Claim
259 words
The system according to claim 18 wherein said second terminal is characterized by an associated encoding key E B =(e B , n B ) and decoding key D B =(d B , n B ), where: n B is a composite number of the form n.sub.B =p.sub.B ·q.sub.B P B and q B are prime numbers, e B is relatively prime to 1 cm(p B -1,q B -1), d B is a multiplicative inverse of e.sub.B (mod(1 cm((p.sub.B -1),(q.sub.B -1)))), wherein said first terminal comprises: blocking means for transforming a message-to-be-transmitted from said first terminal to said second terminal, to one or more transmit message word signals M A , where M A corresponds to a number representative of said message in the range ≦ M.sub.A ≦n.sub.B -1 encoding means coupled to said channel and adapted for transforming each transmit message word signal M A to a ciphertext word signal C A and for transmitting C A on said channel, where C A corresponds to a number representative of an enciphered form of said message and corresponds to C.sub.A ≡M.sub.A.sup.e.sbsp.B (mod n.sub.B) wherein said second terminal comprises: decoding means coupled to said channel and adapted for receiving said ciphertext word signals C A from said channel and for transforming each of said ciphertext word signals to a receive message word signal M A ', and means for transforming said receive message word signals M A to said message, where M' corresponds to a number representative of a deciphered form of C and corresponds to M.sub.A '≡C.sub.A.sup.d.sbsp.B (mod n.sub.B).
Claim 26
Dependent Claim
252 words
The system according to claim 18 wherein said second terminal is characterized by an associated encoding key E B =(e B , n B ) and decoding key D B =(d B , n B ), where: n B is a composite number of the form n.sub.B =p.sub.B ·q.sub.B p B and q B are prime numbers, e B is relatively prime to 1 cm(p B -1,q B -1), d B is a multiplicative inverse of e.sub.B (mod(1 cm((p-1),(q-1)))), wherein said encoding means of said second terminal is adapted for transforming said message word signal M B to a signed cipher-text word signal C Bs , and for transmitting C Bs on said channel in place of C B , whereby C Bs corresponds to a number representative of a signed enciphered form of said message and corresponds to: C.sub.Bs ≡C.sub.B ".sup.d.sbsp.B (mod n.sub.B) where C B " corresponds to a number representative of a block of said ciphertext word signal C B in the range 0≦C B "≦n B -1, wherein said decoding means of said first terminal is adapted to first transform said signed enciphered form of said message C Bs to C B " in accordance with: C.sub.B "≡C.sub.Bs.sup.e.sbsp.B (mod n.sub.B) then to transform C B " to C B , and then to transform C B to said receive message word signal M B ', where M B ' corresponds to a number representative of a deciphered form of C Bs and corresponds to: M.sub.B '≡C.sub.B.sup.d.sbsp.A (mod n.sub.A).
Claim 27
Dependent Claim
353 words
The system according to claim 20 wherein said encoding means of said second terminal is adapted for transforming said message word signal M B to a signed ciphertext word signal C Bs , and for transmitting C Bs on said channel in place of C B , whereby C Bs corresponds to a number representative of a signed enciphered form of said message and corresponds to: C.sub.Bs ≡C.sub.B ".sup.d.sbsp.B (mod n.sub.B) where C B " corresponds to a number representative of a block of said ciphertext word signal C B in the range 0≦C B "≦n B -1, wherein said decoding means of said first terminal is adapted to first transform said signed enciphered form of said message C Bs to C B " in accordance with: C.sub.B "≡C.sub.Bs.sup.e.sbsp.B (mod n.sub.B) and then to transform C B to C B , and then to transform C B to said receive message word signal M B ', where M B ' is a number representative of a deciphered form of C B and corresponds to: M.sub.B '≡C.sub.B.sup.d.sbsp.A (mod n.sub.A) wherein further said encoding means of said first terminal is adapted to transform said message word signal M A to a signal ciphertext word signal C As , as for transmitting C As on said channel in place of C B , whereby C A corresponds to a number representative of a signed enciphered form of said message and corresponds to: C.sub.A ≡C.sub.A ".sup.d.sbsp.A (mod n.sub.A) where C A " corresponds to a number representative of a block of said ciphertext word signal C A in the range of 0≦C A "≦n A -1, wherein said decoding means of said second terminal is adapted to first transform said signaled enciphered form of said message C As to C A " in accordance with: C.sub.A "≡C.sub.As.sup.e.sbsp.A (mod n.sub.A), then to transform C A " to C A , and then to transform C A to said receive message word signal M A ', where M A ' corresponds to a number representative of a deciphered form of C A and corresponds to: M.sub.A ≡C.sub.A.sup.d.sbsp.B (mod n.sub.B).
Claim 28
Independent Claim
91 words
A method for establishing cryptographic communications comprising the step of: encoding a digital message word signal M to a ciphertext word signal C, where M corresponds to a number representative of a message and 0≦M≦n-1 where n is a composite number of the form n=p·q where p and q are prime numbers, and where C is a number representative of an encoded form of message word M, wherein said encoding step comprises the step of: transforming said message word signal M to said ciphertext word signal C whereby C≡M.sup.e (mod n)
Claim 29
Independent Claim
91 words
A method for establishing cryptographic communications comprising the step of: encoding a digital message word signal M to a ciphertext word signal C, where M corresponds to a number representative of a message and 0≦M≦n-1 where n is a composite number of the form n=p·q where p and q are prime numbers, and where C is a number representative of an encoded form of message word M, wherein said encoding step comprises the step of: transforming said message word signal M to said ciphertext word signal C whereby C≡M.sup.e (mod n)
Claim 30
Dependent Claim
9 words
where e is a number relatively prime to (p-1)·(q-1).
Claim 31
Dependent Claim
9 words
where e is a number relatively prime to (p-1)·(q-1).
Claim 32
Dependent Claim
51 words
The method according to claim 23 comprising the further step of: decoding said ciphertext word signal C to said message word signal M, wherein said decoding step comprises the step of: transforming said ciphertext word signal C, whereby: M≡C.sup.d (mod n) where d is a multiplicative inverse of e(mod(1 cm((p-1), (q-1)))).
Claim 33
Independent Claim
185 words
A method for transferring a message signal M i in a communications system having k terminals, wherein each terminal is characterized by an encoding key E i =(e i , n i ) and decoding key D i =(e i , n i ), where i=1,2, . . . ,k, and wherein M i corresponds to a number representative of message-to-be-transmitted from the i th terminal, and 0≦M.sub.i ≦n.sub.i -1, n i is a composite number of the form n.sub.i =p.sub.i ·q.sub.i p i and q i are prime numbers, e i is relatively prime to 1 cm(p i -1,q i -1), d i is a multiplicative inverse of e.sub.i (mod(1 cm((p.sub.i -1),(q.sub.i -1)))) comprising the step of: encoding a digital message word signal M A for transmission from a first terminal (i=A) to a second terminal (i=B), said encoding step including the sub-step of: transforming said message word signal M A to a signed message word signal M As , M A corresponding to a number representative of an encoded form of said message word signal M A , whereby: M.sub.As ≡M.sub.A.sup.d.sbsp.A (mod n.sub.A).
Claim 34
Independent Claim
185 words
A method for transferring a message signal M i in a communications system having k terminals, wherein each terminal is characterized by an encoding key E i =(e i , n i ) and decoding key D i =(e i , n i ), where i=1,2, . . . ,k, and wherein M i corresponds to a number representative of message-to-be-transmitted from the i th terminal, and 0≦M.sub.i ≦n.sub.i -1, n i is a composite number of the form n.sub.i =p.sub.i ·q.sub.i p i and q i are prime numbers, e i is relatively prime to 1 cm(p i -1,q i -1), d i is a multiplicative inverse of e.sub.i (mod(1 cm((p.sub.i -1),(q.sub.i -1)))) comprising the step of: encoding a digital message word signal M A for transmission from a first terminal (i=A) to a second terminal (i=B), said encoding step including the sub-step of: transforming said message word signal M A to a signed message word signal M As , M A corresponding to a number representative of an encoded form of said message word signal M A , whereby: M.sub.As ≡M.sub.A.sup.d.sbsp.A (mod n.sub.A).
Claim 35
Dependent Claim
66 words
The method of claim 25 comprising the further steps of: transmitting said signed message word signal M As to said second terminal, and decoding said signed message word signal M As to said message word signal M A , said decoding step including the sub-step of: transforming said ciphertext word signal C A to said message word signal M A , whereby M.sub.A ≡M.sub.As.sup.e.sbsp.A (mod n.sub.A).
Claim 36
Dependent Claim
109 words
The method of claim 25 wherein said encoding step comprises the further steps of: transforming said signed message word signal M As , one or more signed message block word signals M As , each block word signal M As " corresponding to a number representative of a portion of said signed message word signal M A in the range 0≦M As "≦n B -1, and transforming each of said signed message block word signals M As to a signed ciphertext word signal C As , C As corresponding to a number representative of an encoded form of said signed message block word signal, whereby C.sub.As ≡M.sub.As.sup.e.sbsp.B (mod n.sub.B).
Claim 37
Dependent Claim
104 words
The method of claim 26 comprising the further steps of: transmitting said signed ciphertext word signal C As to said second terminal, decoding said signed ciphertext words to said message word signal M A , said decoding step including the sub-steps of: transforming each of said signed ciphertext word signals C As to one of said signed message block word signals M As ", whereby M.sub.As "≡C.sub.As.sup.d.sbsp.B (mod n.sub.B) transforming said signed message block word signals to said signed message word signal M As , transforming said signed message word signal to said message word signal M A , whereby M.sub.A ≡M.sub.As.sup.e.sbsp.A (mod n.sub.A).
Claim 38
Independent Claim
236 words
A method for transferring a message signal M i in a communications system having k terminals, wherein each terminal is characterized by an encoding key E i =(e i , n i ) and decoding key D i =(e i , n i ), where i=1,2, . . . , k, and wherein M i corresponds to a number representative of a message-to-be-transmitted from the i th terminal, n i is a composite number of the form n.sub.i =p.sub.i ·q.sub.i p i and q i are prime numbers, e i is relatively prime to 1 cm(p i -1,q i -1), d i is a multiplicative inverse of e.sub.i (mod(1 cm((p.sub.i -1),(q.sub.i -1))) comprising the step of: encoding a digital message word signal M A for transmission from a first terminal (i=A) to a second terminal (i=B), said encoding step including the sub-step of: transforming said message word signal M A to one or more message block word signals M A ", each block word signal M A " corresponding to a number representative of a portion of said message word signal M A in the range 0≦M A "≦n B -1, transforming each of said message block word signals M A " to a ciphertext word signal C A , C A corresponding to a number representative of an encoded form of said message block word signal M A ", whereby: C.sub.A ≡M.sub.A ".sup.e.sbsp.B (mod n.sub.B).
Claim 39
Independent Claim
236 words
A method for transferring a message signal M i in a communications system having k terminals, wherein each terminal is characterized by an encoding key E i =(e i , n i ) and decoding key D i =(e i , n i ), where i=1,2, . . . , k, and wherein M i corresponds to a number representative of a message-to-be-transmitted from the i th terminal, n i is a composite number of the form n.sub.i =p.sub.i ·q.sub.i p i and q i are prime numbers, e i is relatively prime to 1 cm(p i -1,q i -1), d i is a multiplicative inverse of e.sub.i (mod(1 cm((p.sub.i -1),(q.sub.i -1))) comprising the step of: encoding a digital message word signal M A for transmission from a first terminal (i=A) to a second terminal (i=B), said encoding step including the sub-step of: transforming said message word signal M A to one or more message block word signals M A ", each block word signal M A " corresponding to a number representative of a portion of said message word signal M A in the range 0≦M A "≦n B -1, transforming each of said message block word signals M A " to a ciphertext word signal C A , C A corresponding to a number representative of an encoded form of said message block word signal M A ", whereby: C.sub.A ≡M.sub.A ".sup.e.sbsp.B (mod n.sub.B).
Claim 40
Dependent Claim
82 words
The method of claim 29 comprising the further steps of: transmitting said ciphertext word signals to said second terminal, and decoding said ciphertext word signals to said message word signal M A , said decoding step including the sub-steps of: transforming each of said ciphertext word signals C A to one or said message block word signals M A ", whereby M.sub.A "≡C.sub.A.sup.d.sbsp.B (mod n.sub.B) transforming said message block word signals M A " to said message word signal M A .
Claim 41
Dependent Claim
108 words
The method of claim 29 wherein said encoding step comprises the further step of: transforming said ciphertext word signal C A to one or more ciphertext block word signals C A , each block word signal C A " corresponding to a number representative of a portion of said ciphertext word signal C A in the range 0≦C A "≦n A -1, transforming each of said ciphertext block word signals C A " to a signed ciphertext word signal C As , C As corresponding to a number representative of an encoded form of said ciphertext block word signal C A ", whereby C.sub.As ≡C.sub.A ".sup.d.sbsp.A (mod n.sub.A).
Claim 42
Dependent Claim
99 words
The method of claim 31 comprising the further steps of: transmitting said signed ciphertext word signals to said second terminal, decoding said signed ciphertext word signals to said message word signal M A , said decoding step including the sub-steps of: transforming each of said signed ciphertext word signals C As to one of said ciphertext block word signals C A ", whereby C.sub.A "≡C.sub.As.sup.e.sbsp.A (mod n.sub.A) transforming said ciphertext block word signals to said message block word signals, whereby M.sub.A "≡C.sub.A ".sup.d.sbsp.B (mod n.sub.B) transforming said message block word signals to said message word signal M A .
Claim 43
Dependent Claim
84 words
In a communications system, an encoding means for transforming a transmit message word signal M to a ciphertext word signal C where M corresponds to a number representative of a message and 0≦M≦n-1 where n is a composite number, and where C corresponds to a number representative of an enciphered form of said message and corresponds to C≡a.sub.e M.sup.e +a.sub.e-1 M.sup.e-1 + . . . +a.sub.0 (mod n) where e and a e , a e-1 , . . . a 0 are numbers.
Claim 44
Dependent Claim
84 words
In a communications system, an encoding means for transforming a transmit message word signal M to a ciphertext word signal C where M corresponds to a number representative of a message and 0≦M≦n-1 where n is a composite number, and where C corresponds to a number representative of an enciphered form of said message and corresponds to C≡a.sub.e M.sup.e +a.sub.e-1 M.sup.e-1 + . . . +a.sub.0 (mod n) where e and a e , a e-1 , . . . a 0 are numbers.
Claim 45
Dependent Claim
292 words
A system according to claim 28 wherein at least one of said transforming means comprises: a first register means for receiving and storing a first digital signal representative of said signal-to-be-transformed, a second register means for receiving and storing a second digital signal representative of the exponent of the equivalence relation defining said transformation, a third register means for receiving and storing a third digital signal representative of the modulus of the equivalency relation defining said transformation, and an exponentiation by repeated squaring and multiplication network coupled to said first, second and third register means, said network including: A. an output register means for receiving and storing a first multiplier signal and for applying said first multiplier signal to a first multiplier input line, B. selector means for successively selecting each of the bits of said second digital signal as a multiplier selector signal, C. means operative for each of said multiplier selector signals for selecting as a second multiplier signal either the contents of said output register means or the contents of said first register means, and for said second applying multiplier signal to a second multiplier input line, said selection being dependent on the binary value of the successive bits of said second digital signal, and D. modulo multiplier means operative in step with said selector means and responsive to said first and second multiplier signals on said first and second multiplier input lines for successively generating first multiplier signals and for transferring said first multiplier signals to said output register means, said first multiplier signal initially being representative of binary 1, and thereafter being representative of the modulo product of said first and second multiplier signals, where the modulus of said modulo product corresponds to said third digital signal.
Claim 46
Dependent Claim
103 words
In the communications system according to claim 33 where e is relatively prime to the Euler totient function of n, .0.(n), and where a e =1 and a e-1 , . . . , a 0 equal zero, a decoding means adapted for receiving C and for transforming C to a receive message word signal M', where M' corresponds to a number representative of a deciphered form of C and corresponds to M'≡C.sup.d (mod n) where d is a multiplicative inverse of e(mod(λ(n))) where λ(n) is the least positive integer such that S.sup.λ(n) =1(mod n) for all integers S relatively prime to n.
Claim 47
Dependent Claim
108 words
In the communications system according to claim 33 where said encoding means is adapted to transform M to C by the performance of a first ordered succession of invertible operations on M, at least one of said operations being exponentiation, a decoding means adapted to transform C to M by the performance of a second ordered succession of invertible operations on C, wherein each of the invertible operations of said second succession is the inverse of a corresponding one of said first succession, and wherein the order of said operations in said second succession is reversed with respect to the order of corresponding operations in said first succession.
Claim 48
Independent Claim
105 words
A method for establishing cryptographic communications comprising the step of: encoding a digital message word signal M to a ciphertext word signal C, where M corresponds to a number representative of a message and 0≦M≦n-1 where n is a composite number and where C corresponds to a number representative of an encoded form of message word M, wherein said encoding step comprises the step of: transforming said message word signal M to said ciphertext word signal C whereby C≡a.sub.e M.sup.e +a.sub.e-1 M.sup.e-1 + . . . +a.sub.0 (mod n) where e and a e , a e-1 , . . . a 0 are numbers.
Claim 49
Independent Claim
105 words
A method for establishing cryptographic communications comprising the step of: encoding a digital message word signal M to a ciphertext word signal C, where M corresponds to a number representative of a message and 0≦M≦n-1 where n is a composite number and where C corresponds to a number representative of an encoded form of message word M, wherein said encoding step comprises the step of: transforming said message word signal M to said ciphertext word signal C whereby C≡a.sub.e M.sup.e +a.sub.e-1 M.sup.e-1 + . . . +a.sub.0 (mod n) where e and a e , a e-1 , . . . a 0 are numbers.
Claim 50
Dependent Claim
98 words
In the method according to claim 37 where e is relatively prime to the Euler totient function of n,.0.n), and where a e =1 and a e-1 , . . . , a 0 equal zero, the further step of: decoding said ciphertext word signal C to said message word signal M, wherein said decoding step comprises the step of: transforming said ciphertext word signal C, whereby: M≡C.sup.d (mod n) where d is a multiplicative inverse of e(mod(λ(n)) where λ(n) is the least positive integer such that S.sup.λ (.sup.n)=1(mod n) for all integers S relatively prime to n.
Claim 51
Dependent Claim
99 words
In the method according to claim 37 where said encoding step includes the step of transforming M to C by the performance of a first ordered succession of invertible operations on M, the further step of: decoding C to M by the performance of a second ordered succession of invertible operations on C, where each of the invertible operations of said second succession is the inverse of a corresponding one of said first succession, and wherein the order of said operations in said second succession is reversed with respect to the order of corresponding operations in said first succession.
Claim 52
Independent Claim
321 words
A method according to claims 23 or 24 or 25 or 26 or 27 or 28 or 29 or 30 or 31 or 32 or 37 or 38 or 39 wherein at least one of said transforming means comprises the steps of: receiving and storing a first digital signal in a first register, said first digital signal being representative of said word-to-be-transformed, receiving and storing a second digital signal in a second register, said second digital signal being representative of the exponent of the equivalence relation defining said transformation, receiving and storing a third digital signal in a third register, said third digital signal being representative of the modulus of the equivalency relation defining said transformation, and exponentiating said first digital signal by repeated squaring and multiplication using said second and third digital signals, said exponentiating step including the substeps of: A. receiving and storing a first multiplier signal in an output register, and applying said first multiplier signal to a first multiplier input line, B. successively selecting each of the bits of said second digital signal as a multiplier selector, and C. for each of said multiplier selectors, selecting as a second multiplier signal either the contents of said output register or the contents of said first register, and for applying said second multiplier signal to a second multiplier output line, said selection being dependent on the binary value of the successive bits of said second digital signal, D. for each of said multiplier selectors, generating said first multiplier signal in a modulo multiplier in response to the first and second multiplier signals on said first and second multiplier input lines, and for transferring said generated first multiplier signal to said output register, said first multiplier signal initially being representative of binary 1 and thereafter being representative of the modulo product of said first and second multipliers, where the modulus of said modulo product corresponds to said third digital signal.
References Cited (Backward Citations)
US3657476A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1986-09-19 | 1987-03-21 | 1987-09-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1990-09-19 | 1991-03-21 | 1991-09-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1994-09-19 | 1995-03-21 | 1995-09-20 | $7700.00 | Window Closed / Lapsed |