| |
 |
Public key cryptographic apparatus and method |
| RE40530 |
Public key cryptographic apparatus and method
|
|
| Patent Drawings: | |
| Inventor: |
Collins, et al. |
| Date Issued: |
October 7, 2008 |
| Application: |
09/694,416 |
| Filed: |
October 20, 2000 |
| Inventors: |
Collins; Thomas (Saratoga, CA)
Hopkins; Dale (Gilroy, CA)
Langford; Susan (Sunnyvale, CA)
Sabin; Michael (Sunnyvale, CA)
|
| Assignee: |
Hewlett-Packard Development Company, L.P. (Houston, TX) |
| Primary Examiner: |
Smithers; Matthew B |
| Assistant Examiner: |
|
| Attorney Or Agent: |
|
| U.S. Class: |
380/30; 380/29 |
| Field Of Search: |
380/28; 380/30 |
| International Class: |
H04L 9/30; H04L 9/00 |
| U.S Patent Documents: |
|
| Foreign Patent Documents: |
|
| Other References: |
Rivest, et. al. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, kACM 1979. cited by examiner.
Knuth, The Art of Computer Programming vol. 2, 1969. cited by examiner.
Itakura and Nakamura, A Public-Key Cryptosystem Suitable for Digital Multisignatures, NEC Res. & Develop. No. 71 Oct. 1983. cited by examiner.
S. A. Vanstone and R. J. Zuccherato, Using four-prime RSA in which some of the bits are specified. cited by examiner.
Rivest, Shamir, and Aldeman, A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of th ACM, 21(2), Feb. 1978. cited by examiner.
Captain Nemo, RSA Moduli Should Have 3 Prime factors, Aug. 1996. cited by examiner.
Donald Knuth, The Art of Computer Programming, vol. 2, Addison-Wesley Publishing Company 1969. cited by examiner.
S.A. Vanstone et al., "Using Four-Prime RSA in Which Some of the Bits are Specified," Dec. 8, 1994, Electronics Letter, vol. 30, No. 25. pp. 2118-2119. cited by other.
C. Couvruer et al., "An Introduction to Fast Generation of Large Prime Numbers," 1982, Philips Journal of Research, vol. 37, Nos. 5-6, pp. 231-264. cited by other.
Y. Desmedt et al., "Public-Key Systems Based on the Difficulty of Tampering (Is There a Difference Between DES and RSA?)," 1986, Lecture Notes in Computer Science, Advances in Cryptology--Crypto '86 Proceedings. cited by other.
J. J. Quisquater et al., "Fast Decipherment Algorithm for RSA Public-Key Cryptosystem" Oct. 1982, Electronic Letters, vol. 19, No. 21. cited by other.
Cetin Kaya Koc, "High-Speed RSA Implementation (Version 2.0)," Nov. 1994, RSA White Paper, RSA Laboratories. cited by other.
Rivest et al., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Feb. 1978, Communications of the ACM, vol. 21. cited by other.
PKCS #1: RSA Encryption Standard (Version 1.5), Nov. 1993, RSA Laboratories Technical Note. cited by other.
M.O. Rabin, "Digitalized Signatures and Public-Key Functions as Intractable as Factorization," Jan. 1979, MIT Laboratory for Computer Science. cited by other.
R. Lidl et al., "Permutation Polynomials in RSA-Cryptosystems," 1984, Advances in Cryptology--Crypto '83, pp. 293-301. cited by other.
D. Boneh et al., "Generating a Product of Three Primes with an Unknown Factorization," Computer Science Department, Stanford University, date unknown. cited by other.
J. J. Quisquater et al., "Fast Generation of Large Prime Numbers" Jun. 1982, Library of Congress, Catalog No. 72-179437, IEEE Catalog No. 92CH1767-3 IT, pp. 114-115. cited by other.
A. J. Menezes et al., "Handbook of Applied Cryptography", 1997, Library of Congress catalog No. 96-27609, pp. 89, 612-613. cited by other.
Kenneth H. Rosen, "Elementary Number Theory and Its Applications," 2nd Edition, Copyright 1988 by Bell Telephone Laboratories and Kenneth H. Rosen, p. 97 (4 p.). cited by other.
Micali et al., "Accountable-Subgroup Multisignatures", CCS '01, Proceedings of the Eighth ACM Conference on Computer and Communications Security, @ACM 2001, Aug. 15, 2001, pp. 1-18. cited by other.
Menezes et al., Handbook of Applied Cryptography, CRC Press, 1997, Chapter 8, "Public-Key Encryption", pp. 283-319. cited by other.
Bruce Schneier: "Applied Cryptography" Second Edition, Jan. 1, 1996, John Wiley & sons, USA, XP002283138, pp. 466-474. cited by other.
European Search Report, dated Oct. 11, 2004; App No. EP 95 3075. cited by other.
P. J. Flinn et al. Using the RSA Algorithm for Encryption and Digital Signatures: Can you Encrypt, Decrypt, Sign and Verify without Infringing the RSA Patent? Jul. 9, 1997, Alston & Bird LLP, http://www.cyberlaw.com/rsa.html. cited by other.
International Search Report (PCT), ISA/US; Apr. 6, 1998. cited by examiner. |
|
| Abstract: |
A method and apparatus are disclosed for improving public key encryption and decryption schemes that employ a composite number formed from three or more distinct primes. The encryption or decryption tasks may be broken down into sub-tasks to obtain encrypted or decrypted sub-parts that are then combined using a form of the Chinese Remainder Theorem to obtain the encrypted or decrypted value. A parallel encryption/decryption architecture is disclosed to take advantage of the inventive method.REEXAMINATION RESULTS.Iadd.The questions raised in reexamination request No. 90/005,733, filed May 18, 2000 and reexamination request No. 90/005,776, filed on Jul. 28, 2000, have been considered and the results thereof are reflected in this reissue patent which constitutes the reexamination certificate required by 35 U.S.C. 307 as provided in 37 CFR 1.570(e). .Iaddend. |
| Claim: |
What is claimed:
1. A method for .[.establishing cryptographic.]. communications .Iadd.of a message cryptographically processed with RSA (Rivest, Shamir & Adleman) public key encryption,.Iaddend.comprising the .[.step.]. .Iadd.steps .Iaddend.of: .Iadd.developing k distinct random prime numbers p.sub.1, p.sub.2, . . . , p.sub.k, wherein k is an integer greater than 2; providing a number e relatively prime to (p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1); providing a composite number n equaling the product p.sub.1p.sub.2 . . . p.sub.k; receiving a ciphertext word signal C which is formed by .Iaddend.encoding a plaintext message word .Iadd.signal .Iaddend.M to a ciphertext word signalC, where M corresponds to a number representative of .[.a.]. .Iadd.the .Iaddend.message and 0.ltoreq.M.ltoreq.n-1 .[.n being a composite number formed from the product of p.sub.1p.sub.2. . . p.sub.k where k is an integer greater than 2, p.sub.1,p.sub.2, . . . p.sub.k are distinct prime numbers, and.]. where C is a number representative of an encoded form of .Iadd.the plaintext .Iaddend.message word .Iadd.signal .Iaddend.M .Iadd.such that C.ident.M.sup.e(mod n) and where e is associated withan intended recipient of the ciphertext word signal C; and.Iaddend..[., 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) where e is a number relativelyprime to (p.sub.1-1)(p.sub.2-1)..]. .Iadd.deciphering the received ciphertext word signal C at the intended recipient having available to it the k distinct random prime number p.sub.1, p.sub.2, . . . p.sub.k; wherein p and q are a pair of prime numbersthat product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein the deciphering step is divided intosub-steps, one sub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the deciphering step if the k distinct random prime numbersare used, relative to the number of computational cycles for performing a deciphering step if the pair of prime numbers p and q is used instead.Iaddend..
2. The method according to claim 1, .[.comprising the further step of:.]. .Iadd.wherein the deciphering step includes establishing a number, d, as a multiplicative inverse of e(mod(lcm((p.sub.1-1), (p.sub.2-1), . . . (p.sub.k-1)))), and.Iaddend. decoding the ciphertext word signal C to the .Iadd.plaintext .Iaddend.message word signal M.[., wherein said decoding step comprises the step of: transforming said ciphertext word signal C,.]. where.[.by: M=C.sup.d(mod n).]..Iadd.M.ident.C.sup.d(mod n). .Iaddend. .[.where d is a multiplicative inverse of e(mod(lcm((p.sub.1-1), (p.sub.2-1), . . . , (p.sub.k-1)))).
3. A method for .[.transferring a message signal M.sub.i in a.]. communications .Iadd.of a message signal M.sub.i cryptographically processed with RSA public key encryption in a .Iaddend.system having j terminals, .[.wherein.]. each terminal.[.is.]. .Iadd.being .Iaddend.characterized by an encoding key E.sub.i=(e.sub.i, n.sub.i) and .Iadd.a .Iaddend.decoding key D.sub.i=(d.sub.i, n.sub.i), where i=1, 2, . . . , j, and .[.wherein.]. .Iadd.the message signal .Iaddend.M.sub.i corresponds toa number representative of a message-to-be-.[.transmitted.]. .Iadd.received .Iaddend.from the i.sup.th terminal, .Iadd.the method comprising the steps of: establishing n.sub.i where .Iaddend.n.sub.i is a composite number of the form.[.n.sub.i=P.sub.i,1p.sub.i,2, . . . , p.sub.i,k.]. .Iadd.n.sub.i=p.sub.i,1p.sub.i,2 . . . p.sub.i,k .Iaddend. where k is an integer greater than 2, p.sub.i,1, p.sub.i,2, . . . , p.sub.i,k are distinct .Iadd.random .Iaddend.prime numbers, e.sub.i isrelatively prime to .[.lcm(p.sub.i,1-1, p.sub.i,2-1, p.sub.i,kd-1).]. .Iadd.lcm(p.sub.i,1-1, p.sub.i,2-1, . . . , p.sub.i,k-1), and .Iaddend. d.sub.i is selected from the group consisting of .[.the.]. .Iadd.a .Iaddend.class of numbers equivalent to amultiplicative inverse of e.sub.i(mod(lcm((p.sub.i,1-1), (p.sub.i,2-1), . . . , (p.sub.i,k-1)))).[.,.]. .Iadd.; .Iaddend. .[.comprising the steps of:.]. .Iadd.receiving by a recipient terminal (i=y) from a sender terminal (i=x, x.noteq.y) aciphertext signal C.sub.x formed by .Iaddend.encoding a digital message word signal .[.M.sub.A for transmission from a first terminal (i=A) to a second terminal (i=B), said encoding step including the sub-step of:.]. .Iadd.M.sub.x, wherein the encodingincludes .Iaddend. transforming said message word signal M.sub.A to one or more message block word signals .[.M.sub.A''.]. .Iadd.M.sub.X''.Iaddend., each block word signal .[.M.sub.A''.]. .Iadd.M.sub.X'' .Iaddend.corresponding to a numberrepresentative of a portion of said message word signal .[.M.sub.A.]. .Iadd.M.sub.X .Iaddend. in the range .[.0.ltoreq.M.sub.A''.ltoreq.n.sub.B-1.]. .Iadd.0.ltoreq.M.sub.X''.ltoreq.n.sub.y-1.Iaddend., .Iadd.and .Iaddend. transforming each of saidmessage block word signals .[.M.sub.A''.]. .Iadd.M.sub.X'' .Iaddend.to a ciphertext word signal .[.C.sub.A, C.sub.A corresponding.]. .Iadd.C.sub.X that corresponds .Iaddend.to a number representative of an encoded form of said message block word signal.[.M.sub.A'',.]. .Iadd.M.sub.X'' .Iaddend.where.[.by.]. : .[.C.sub.A.ident.M.sub.A.sup.''eB(mod n.sub.B.).]. .Iadd.C.sub.x.ident.M.sub.x.sup.''ey(mod n.sub.y); and deciphering the received ciphertext word signal C.sub.x at the recipient terminalhaving available to it the k distinct random prime numbers p.sub.y,1, p.sub.y,2, . . . , p.sub.y,k for establishing its d.sub.y; wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random primenumbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein the deciphering step is divided into sub-steps, one sub-step for each of the k distinct random prime numbers; and whereinfor a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the deciphering step if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a decipheringstep if the pair of prime numbers p and q is used instead.Iaddend..
4. A .[.cryptographic communications.]. system .Iadd.for communications of a message cryptographically processed with an RSA public key encryption, .Iaddend.comprising: a communication .[.medium.]. .Iadd.channel for transmitting a ciphertextword signal C.Iaddend.; .[.an.]. encoding means coupled to said channel and adapted for transforming a transmit message word signal M to .[.a.]. .Iadd.the .Iaddend.ciphertext word signal C .Iadd.using a composite number, n, where n is a product of theform n=p.sub.1p.sub.2 . . . p.sub.k, where k is an integer greater than 2, and p.sub.1, p.sub.2, . . . p.sub.k are distinct random prime numbers, .Iaddend..[.and for transmitting C on said channel,.]. where .Iadd.the transmit message word signal.Iaddend.M corresponds to a number representative of .[.a.]. .Iadd.the .Iaddend.message and 0.ltoreq.M.ltoreq.n-1.Iadd., .Iaddend..[.where n is a composite number of the form n=p.sub.1p.sub.2. . . p.sub.k where k is an integer greater than 2 andp.sub.1, p.sub.2, . . . , p.sub.k are distinct prime numbers, and.]. where .Iadd.the ciphertext word signal .Iaddend.C corresponds to a number representative of an .[.enciphered.]. .Iadd.encoded .Iaddend.form of said message .[.and corresponds to.]. .Iadd.through a relationship of the form .Iaddend. C.ident.M.sup.e(mod n).Iadd., and .Iaddend. where e is a number relatively prime to lcm(p.sub.1-1, p.sub.2-1, . . . , p.sub.k-1); and .[.a.]. decoding means coupled to said channel and adapted forreceiving .Iadd.the ciphertext word signal .Iaddend.C from said channel and.Iadd., having available to it the k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k, .Iaddend.for transforming .Iadd.the ciphertext word signal .Iaddend.C to areceive message word signal M' where M' corresponds to a number representative of a .[.deciphered.]. .Iadd.decoded .Iaddend.form of .Iadd.the ciphertext word signal .Iaddend.C .[.and corresponds to.]. .Iadd.through a relationship of the form .Iaddend. M'.ident.C.sup.d(mod n) where d is selected from the group consisting of .[.the.]. .Iadd.a .Iaddend.class of numbers equivalent to a multiplicative inverse of e(mod(lcm((p.sub.1-1), (p.sub.2-1), . . . , (p.sub.k-1)))).Iadd.; wherein p and q are a pairof prime numbers that product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein transforming the ciphertextword signal C to a receive message word signal M' is divided into sub-steps, one sub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles toperform the transforming of the ciphertext word signal C if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a transforming of the ciphertext word signal C if the pair of prime numbers p and q isused instead.Iaddend..
5. A .[.cryptographic communications.]. system .Iadd.for communications of a message cryptographically processed with an RSA public key encryption, the system .Iaddend.having a plurality of terminals coupled by a communications channel,.[.including.]. .Iadd.comprising: .Iaddend. a first terminal .Iadd.of the plurality of terminals .Iaddend.characterized by an .[.associated.]. encoding key E.sub.A=(e.sub.A, n.sub.A) and .Iadd.a .Iaddend.decoding key D.sub.A=(d.sub.A, n.sub.A),where.[.in.]. n.sub.A is a composite number of the form n.sub.A=p.sub.A,1p.sub.A,2. . . P.sub.A,k where k is an integer greater than 2, p.sub.A,1, p.sub.A,2, . . . , p.sub.A,k are distinct .Iadd.random .Iaddend.prime numbers, e.sub.A is relativelyprime to lcm(p.sub.A,1-1, p.sub.A,2-1, . . . , p.sub.A,k-1), .Iadd.and .Iaddend. d.sub.A is selected from the group consisting of .[.the.]. .Iadd.a .Iaddend.class of numbers equivalent to a multiplicative inverse of e.sub.A(mod(lcm((p.sub.A,1-1),(p.sub.A,2-1), . . . , (p.sub.A,k-1)))).[.,.]. .Iadd.; and .Iaddend. .[.and including.]. a second terminal.[., comprising:.]. .Iadd.of the plurality of terminals having .Iaddend. blocking means for transforming a .Iadd.first.Iaddend.message.[.-to-be-transmitted.]. .Iadd., which is to be transmitted on said communications channel .Iaddend.from said second terminal to said first terminal.Iadd., in.Iaddend.to one or more transmit message word signals M.sub.B, where .Iadd.each.Iaddend.M.sub.B corresponds to a number representative of said .Iadd.first .Iaddend.message in the range 0.ltoreq.M.sub.B.ltoreq.n.sub.A-1, .Iadd.and .Iaddend. encoding means coupled to said channel and adapted for transforming each transmit messageword signal M.sub.B to a ciphertext word signal C.sub.B .Iadd.that .Iaddend..[.and for transmitting C.sub.B on said channel, where C.sub.B.]. corresponds to a number representative of an .[.enciphered.]. .Iadd.encoded .Iaddend.form of said .Iadd.first.Iaddend.message .[.and corresponds to.]. .Iadd.through a relationship of the form .Iaddend. .[.C.sub.B=M.sub.B.sup.eA(mod n.sub.A).]. .Iadd.C.sub.B.ident.M.sub.B.sup.e.sup.A(mod n.sub.A), .Iaddend. .[.wherein.]. said first terminal .[.comprises:.]..Iadd.having .Iaddend. decoding means coupled to said channel and adapted for receiving .Iadd.each of .Iaddend.said ciphertext word signals C.sub.B from said channel and.Iadd., having available to it the k distinct random prime numbers p.sub.A,1,p.sub.A,2, . . . , p.sub.A,k, .Iaddend.for transforming each of said ciphertext word signals .Iadd.C.sub.B .Iaddend.to a receive message word signal .[.M.sub.B.]. .Iadd.M.sub.B'.Iaddend., and means for transforming said receive message word signal.[.sM'.]. .Iadd.M.sub.B' .Iaddend.to said .Iadd.first .Iaddend.message, where .[.M' is.]. .Iadd.M.sub.B' corresponds to .Iaddend.a number representative of a .[.deciphered.]. .Iadd.decoded .Iaddend.form of C.sub.B .[.and corresponds to.]. .Iadd.through arelationship of the form .Iaddend. .[.M.sub.B'=C.sub.B.sup.d.sup.A(mod n.sub.A).]. .Iadd.M.sub.B'.ident.C.sub.B.sup.d.sup.A(mod n.sub.A); .Iaddend. wherein p and q are a pair of prime numbers that product of which equals a composite number m, the kdistinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein transforming said receive message word signal M.sub.B' to said first message is divided intosub-steps, one sub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the transforming of said receive message word signal M.sub.B'if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a transforming of said receive message word signal M.sub.B' if the pair of prime numbers p and q is used instead.Iaddend..
6. The system according to claim 5 wherein said second terminal is characterized by an .[.associated.]. encoding key E.sub.B=(e.sub.B, n.sub.B) and .Iadd.a .Iaddend.decoding key .[.DB=(D.sub.B, d.sub.B).]. .Iadd.D.sub.B=(d.sub.B,n.sub.B).Iaddend., where.[.:.]. n.sub.B is a composite number of the form n.sub.B=p.sub.B,1p.sub.B,2. . . p.sub.B,k.Iadd., .Iaddend. where k is an integer greater than 2, p.sub.B,1, p.sub.B,2, . . . , p.sub.B,k are distinct .Iadd.random .Iaddend.primenumbers, e.sub.B is relatively prime to lcm(p.sub.B,1-1, p.sub.B,2-1, . . . , p.sub.B,k-1), .Iadd.and .Iaddend. d.sub.B is selected from the group consisting of .[.the.]. .Iadd.a .Iaddend.class of numbers equivalent to a multiplicative inverse ofe.sub.B(mod(lcm((p.sub.B,1), (p.sub.B,2-1), . . . , (p.sub.B,k-1)))), .[.wherein.]. said first terminal .[.comprises:.]. .Iadd.further having .Iaddend. blocking means for transforming a .Iadd.second .Iaddend.message.[.-to-be-transmitted.]. .Iadd.,which is to be transmitted on said communications channel .Iaddend.from said first terminal to said second terminal, to one or more transmit message word signals M.sub.A, where .Iadd.each .Iaddend.M.sub.A corresponds to a number representative of saidmessage in the range .[.0.ltoreq.M.sub.A.sup.eB(mod n.sub.B),.]. .Iadd.0.ltoreq.M.sub.A.ltoreq.n.sub.B-1, and .Iaddend. encoding means coupled to said channel and adapted for transforming each transmit message word signal M.sub.A to a ciphertext wordsignal C.sub.A and for transmitting C.sub.A on said channel, where C.sub.A corresponds to a number representative of an .[.enciphered.]. .Iadd.encoded .Iaddend.form of said .Iadd.second .Iaddend.message .[.and corresponds to.]. .Iadd.through arelationship of the form .Iaddend. .[.C.sub.A=M.sub.A.sup.eB(mod n.sub.B).]. .Iadd.C.sub.A.ident.M.sub.A.sup.e.sup.B(mod n.sub.B); and .Iaddend. .[.wherein.]. said second terminal .[.comprises;.]. .Iadd.further having .Iaddend. decoding meanscoupled to said channel and adapted for receiving .Iadd.each of .Iaddend.said ciphertext word signals C.sub.A from said channel and.Iadd., having available to it the k distinct random prime numbers p.sub.B1, p.sub.B,2, . . . , p.sub.B,k, .Iaddend.fortransforming each of said ciphertext word signals to a receive message word signal M.sub.A', and means for transforming said receive message word signals .[.M.sub.A.]. .Iadd.M.sub.A' .Iaddend.to said .Iadd.second .Iaddend.message, where .[.M'.]. .Iadd.M.sub.A' .Iaddend.corresponds to a number representative of a .[.deciphered.]. .Iadd.decoded .Iaddend.form of .[.and corresponds to.]. .Iadd.C.sub.A through a relationship of the form .Iaddend. .[.M.sub.A'.ident.C.sub.A.sup.dB(mod n.sub.B).]..Iadd.M.sub.A'.ident.C.sub.A.sup.d.sup.B(mod n.sub.B).Iaddend..
.[.7. A method for establishing cryptographic communications comprising the step of: encoding a digital message word signal M to a cipher text word signal C, where M corresponds to a number representative of a message and 0.ltoreq.M.ltoreq.n-1,where n is a composite number having at least 3 whole number factors greater than one, the factors being distinct prime numbers, and where C corresponds to a number representative of an encoded form of message word M, wherein said encoding step comprisesthe step of: transforming said message word signal M to said ciphertext word signal C whereby C.ident.a.sub.eM.sup.e+a.sub.e-1M.sup.e-1+. . . +a.sub.o(mod n) where e and a.sub.e, a.sub.e-1, . . . , a.sub.o are numbers..].
.[.8. In the method according to claim 7 wherein 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 performanceof 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 secondsuccession is reversed with respect to the order of corresponding operations in said first succession..].
9. A .[.communication.]. system for .[.transferring.]. .Iadd.communications of .Iaddend.message signals .[.M.sub.i.]. .Iadd.cryptographically processed with RSA public key signing.Iaddend., comprising: j .[.stations,.]. .Iadd.terminalsincluding first and second terminals, .Iaddend.each of the j .[.stations.]. .Iadd.terminals .Iaddend.being characterized by an encoding key E.sub.i=(e.sub.i, n.sub.i) and decoding key D.sub.i=(d.sub.i, n.sub.i), where i=1,2, . . . ,j, .[.and whereinM.sub.i corresponds to a number representative of a message signal to be transmitted from the i.sup.th terminal,.]. .Iadd.each of the j terminals being adapted to transmit a particular one of the message signals where an i.sup.th message signals M.sub.iis transmitted from an i.sup.th terminal .Iaddend.and 0.ltoreq.M.sub.i.ltoreq.n.sub.i-1, n.sub.i .[.is.]. .Iadd.being .Iaddend.a composite number of the form .[.n.sub.i=pi.sub.i,1p.sub.i,2. . . p.sub.i,k.]. .Iadd.n.sub.i=p.sub.i,1p.sub.i,2. . .p.sub.i,k .Iaddend. where k is an integer greater than 2, p.sub.i,1, p.sub.i,2, . . . , p.sub.i,k are distinct .Iadd.random .Iaddend.prime numbers, e.sub.i is relatively prime to lcm(p.sub.i,1-1,p.sub.i,2-1, . . . , p.sub.i,k-1), .Iadd.and .Iaddend. d.sub.i is selected from the group consisting of .[.the.]. .Iadd.a .Iaddend.class of numbers equivalent to a multiplicative inverse of e.sub.i(mod(lcm((p.sub.i,1-1), (p.sub.i,2-1), . . . , (p.sub.i,k-1)))); .[.a.]. .Iadd.said .Iaddend.first .[.one ofthe j terminals.]. .Iadd.terminal .Iaddend.including means for encoding a digital message word signal .[.M.sub.A for transmission.]. .Iadd.M.sub.1 to be transmitted .Iaddend.from said first terminal (i=.[.A.]. .Iadd.1.Iaddend.) to .[.a.]. .Iadd.said.Iaddend.second .[.one of the j terminals.]. .Iadd.terminal .Iaddend.(i=.[.B.]. .Iadd.2.Iaddend.), .[.and.]. .Iadd.said encoding .Iaddend.means .[.for.]. transforming said .Iadd.digital .Iaddend.message word signal .[.M.sub.AS, M.sub.AS correspondingto a number representative of an encoded form of said message word signal M.sub.A, whereby:.]. .Iadd.M.sub.1S using a relationship of the form .Iaddend. .[.M.sub.AS.ident.M.sub.A.sup.dA(mod n.sub.A).]. .Iadd.M.sub.1S.ident.M.sub.1.sup.d.sup.1(modn.sub.1); and means for transmitting said signed message word signal M.sub.1S from said first terminal to said second terminal, wherein said second terminal includes means for decoding said signed message word signal M.sub.1S to said digital messageword signal M.sub.1; wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random prime number each smaller than p and q, and the composite number m having the same number of digits as thecomposite number n; wherein encoding a digital message word signal M.sub.1 is divided into sub-steps, on sub-step for each of the k distinct random prime numbers; and wherein for a give number of digits for composite numbers n and m, it takes fewercomputational cycles to perform the encoding of the digital message word signal M.sub.i if the k distinct random prime numbers are used, relative to the number of computational cycles for performing an encoding of the digital message word signal M.sub.1if the pair of prime numbers p and q is used instead.Iaddend..
10. The system of claim 9.Iadd., wherein the means for decoding signed message word signal M.sub.1S includes means for .Iaddend..[.further comprising: means for transmitting said signal message word signal M.sub.AS from said first terminal tosaid second terminal, and wherein said second terminal includes means for decoding said signed message word signal M.sub.AS to said message word signal M.sub.A, said second terminal including: means for.]. transforming said signed message word signal.[.M.sub.AS.]. .Iadd.M.sub.1S .Iaddend.to said .Iadd.digital .Iaddend.message word signal .[.M.sub.A, whereby.]. .Iadd.M.sub.1 using a relationship of the form .Iaddend. .[.M.sub.A.ident.M.sub.AS.sup.eA(mod n.sub.A).]..Iadd.M.sub.i.ident.M.sub.1S.sup.e.sup.1 (mod n.sub.1).Iaddend..
11. A communication system for transferring a message signal .[.M.sub.i.]. .Iadd.cryptographically processed with RSA public key encryption.Iaddend., the communications system comprising.Iadd.: .Iaddend. j communication stations.Iadd.including first and second stations, .Iaddend.each .Iadd.of the j communication stations being .Iaddend.characterized by an encoding key E.sub.i=(e.sub.i, n.sub.i) and .Iadd.a .Iaddend.decoding key D.sub.i=(d.sub.i, n.sub.i), where i=1, 2, . . . ,j, .[.and wherein M.sub.i corresponds to a number representative of a message signal to be transmitted from the i.sup.th terminal,.]. .Iadd.each of the j communication stations being adapted to transmit a particular one of the message signals where ani.sup.th message signal M.sub.i is received from an i.sup.th communication station, and 0.ltoreq.M.sub.i.ltoreq.n.sub.i-1 n.sub.i .[.is.]. .Iadd.being .Iaddend.a composite number of the form n.sub.i=p.sub.i,1p.sub.i,2. . . p.sub.i,k where k is aninteger greater than 2, p.sub.i,1, p.sub.i,2, . . . , p.sub.i,k are distinct .Iadd.random .Iaddend.prime numbers, e.sub.i is relatively prime to lcm(p.sub.i,1-1,p.sub.i,2-1, . . . ,p.sub.i,k-1), .Iadd.and .Iaddend. d.sub.i is selected from the groupconsisting of .[.the.]. .Iadd.a .Iaddend.class of numbers equivalent to a multiplicative inverse of e.sub.i(mod(lcm((p.sub.i,1-1), (p.sub.i,2-1), . . . , (p.sub.i,k-1)))).Iadd., .Iaddend. .[.a.]. .Iadd.said .Iaddend.first .[.one of the jcommunication stations.]. .Iadd.station .Iaddend.including means for encoding a digital message word signal .[.M.sub.A for transmission.]. .Iadd.M.sub.1 to be transmitted .Iaddend.from said first .[.one of the j communication stations.]. .Iadd.station.Iaddend.(l=.[.A.]. .Iadd.1.Iaddend.) to .[.a.]. .Iadd.said .Iaddend.second .[.one of the j communication stations.]. .Iadd.station .Iaddend.(l=.[.B.]. .Iadd.2.Iaddend.), means for transforming said .Iadd.digital .Iaddend.message word signal.[.M.sub.A.]. .Iadd.M.sub.1 .Iaddend.to one or more message block word signals .[.M.sub.A''.]. .Iadd.M.sub.1''.Iaddend., each block word signal .[.M.sub.A'.]. .Iadd.M.sub.1''.Iaddend. being a number representative of a portion of said .Iadd.digital.Iaddend.message word signal .[.M.sub.A'.]. .Iadd.M.sub.1 .Iaddend.in the range .[.0.ltoreq.M.sub.A.ltoreq.n.sub.B-1,.]. .Iadd.0.ltoreq.M.sub.1''.ltoreq.n.sub.2-1, .Iaddend.and means for transforming each of said message block word signals.[.M.sub.A''.]. .Iadd.M.sub.1'' .Iaddend.to a ciphertext word signal .[.C.sub.A, C.sub.A corresponding to a number representative of an encoded form of said message block word signal M.sub.A'', whereby:.]. .Iadd.C.sub.1 using a relationship of the form.Iaddend. .[.C.sub.A=M.sub.A''.sup.Eb(mod n.sub.B).]. .Iadd.C.sub.1.ident.M.sub.1''.sup.e.sup.2(mod n.sub.2); and means for transmitting said ciphertext signals C.sub.1 from said first station to said second station, wherein said second stationincludes means for deciphering said ciphertext signals C.sub.1 using p.sub.2,1, p.sub.2,2, . . . p.sub.2,k to produce said digital message word signal M.sub.1; wherein p and q are a pair of prime numbers that product of which equals a composite numberm, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein deciphering said ciphertext signals C.sub.1 is divided into sub-steps, one sub-step for eachof the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the deciphering of said ciphertext signals C.sub.1 if the k distinct random prime numbers areused, relative to the number of computational cycles for performing a deciphering of said ciphertext signals C.sub.1 if the pair of prime numbers p and q is used instead.Iaddend..
12. The .Iadd.communications .Iaddend.system of claim 11 .[.further comprising: means for transmitting said ciphertext word signals from said first terminal to said second terminal, and.]. wherein .[.said second terminal.]. .Iadd.thedeciphering means .Iaddend.includes means for decoding said cyphertext word signals .Iadd.C.sub.1 .Iaddend.to said message .Iadd.block .Iaddend.word signal.Iadd.s .Iaddend..[.MA.]. .Iadd.M.sub.1'' using a relationship of the form.Iaddend..[., saidsecond terminal including: means for transforming each of said ciphertext word signals C.sub.A to one of said message block word signals M.sub.A'', whereby.]. .[.M.sub.A''.ident.C.sub.A.sup.Db(mod n.sub.B).]..Iadd.M.sub.1''.ident.C.sub.1.sup.d.sup.2(mod n.sub.2), and .Iaddend. means for transforming said message block word signals .[.M.sub.A''.]. .Iadd.M.sub.1'' .Iaddend.to said message word signal .[.M.sub.A.]. .Iadd.M.sub.1.Iaddend..
.[.13. In a communications system, including first and second communicating stations interconnected for communication therebetween, the first communicating station having encoding means for transforming a transmit message word signal M to aciphertext word signal C where M corresponds to a number representative of a message and 0.ltoreq.M.ltoreq.n-1 where n is a composite number having at least 3 whole number factors greater than one, the factors being distinct prime numbers, and where Ccorresponds to a number representative of an enciphered form of said message and corresponds to C.ident.a.sub.eM.sup.e+a.sub.e-1M.sup.e-1+. . . +a.sub.o(mod n) where e and a.sub.e, a.sub.e-1, . . . , a.sub.o are numbers; and means for transmitting theciphertext word signal C to the second communicating station..].
.Iadd.14. The method according to claim 9, wherein the signed message word signal M.sub.1S, formed from the digital message word signal M.sub.1 being cryptographically processed at the first terminal with multi-prime (k>2) RSA public keysigning which is characterized by the composite number n being computed as the product of the k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k, is decipherable at the second terminal with two-prime RSA public key signing characterized bythe composite number m being computed as the product of the pair of prime numbers p and q. .Iaddend.
.Iadd.15. A method of communicating a message cryptographically processed with an RSA public key encryption, comprising the steps of: selecting a public key portion e associated with a recipient intended for receiving the message; developing kdistinct random prime numbers, p.sub.1, p.sub.2, . . . p.sub.k, where k.gtoreq.3, and checking that each of the k distinct random prime numbers minus 1, p.sub.1-1, p.sub.2-1, . . . , p.sub.k-1, is relatively prime to the public key portion e; computing a composite number, n, as a product of the k distinct random prime numbers; receiving a ciphertext message formed by encoding a plaintext message data M to the ciphertext message data C using a relationship of the form C.ident.M.sup.e(mod n)where M represents the message, where 0.ltoreq.M.ltoreq.n-1, and where the sender knows n and the public key portion e but has no access to the k distinct random prime numbers, p.sub.1, p.sub.2, . . . p.sub.k; and deciphering at the recipient thereceived ciphertext message data C to produce the message, the recipient having access to the k distinct random prime numbers, p.sub.1, p.sub.2, . . . p.sub.k; wherein p and q are a pair of prime numbers that product of which equals a composite numberm, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein the deciphering step is divided into sub-steps, one sub-step for each of the k distinctrandom prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the deciphering step if the k distinct random prime numbers are used, relative to the number of computationalcycles for performing a deciphering step if the pair of prime numbers p and q is used instead. .Iaddend.
.Iadd.16. The method according to claim 15, comprising the further step of: establishing a private key portion d by a relationship to the public key portion e in the form of d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))),wherein the deciphering step includes decoding the ciphertext message data C to the plaintext message data M using a relationship of the form M.ident.C.sup.d(mod n). .Iaddend.
.Iadd.17. The method according to claim 15, wherein a message cryptographically processed by the sender with two-prime RSA public key encryption characterized by the composite number m being computed as the product of the pair of prime numbersp and q, is decipherable with multi-prime (k>2) RSA public key encryption characterized by the composite number n being computed as the product of the k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k. .Iaddend.
.Iadd.18. The method according to claim 15, wherein n and m include values that are more than 600 digits long. .Iaddend.
.Iadd.19. A method of communicating a message cryptographically processed with RSA public key encryption, comprising the steps of: selecting a public key portion e; developing k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k,where k.gtoreq.3, and checking that each of the k distinct random prime numbers minus 1, p.sub.1-1, p.sub.2-1, . . . p.sub.k-1, is relatively prime to the public key portion e; establishing a private key portion d by a relationship to the public keyportion e in the form of d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))); computing a composite number, n, as a product of the k distinct random prime numbers; receiving a ciphertext message data C representing an encoded form of aplaintext message data M; and decoding the received ciphertext message data C to the plaintext message data M using a relationship of the form M.ident.C.sup.d(mod n), the decoding performed by a recipient owning the private key portion d and havingaccess to the k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k; wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, and thecomposite number m having the same number of digits as the composite number n; wherein the decoding step is divided into sub-steps, one sub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for compositenumbers n and m, it takes fewer computational cycles to perform the decoding step if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a decoding step if the pair of prime numbers p and q is usedinstead. .Iaddend.
.Iadd.20. The method according to claim 19, wherein the ciphertext message data C is formed by encoding the plaintext message data M to the ciphertext message data C using a relationship of the form C.ident.M.sup.e (mod n), wherein0.ltoreq.M.ltoreq.n-1 and wherein n and the public key portion e are accessible to the sender although it has no access to the k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k. .Iaddend.
.Iadd.21. The method according to claim 19, wherein a message cryptographically processed by the sender with two-prime RSA public key encryption characterized by the composite number m being computed as the product of the pair of prime numbersp and q, is decipherable by the decoding with multi-prime (k>2) RSA public key encryption characterized by the composite number n being computed as the product of the k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k. .Iaddend.
.Iadd.22. The method according to claim 19, wherein n and m include values that are more than 600 digits long. .Iaddend.
.Iadd.23. A method of communicating a message cryptographically processed with RSA public key signing, comprising the steps of: selecting a public key portion e; developing k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k,where k.gtoreq.3, and checking that each of the k distinct random prime numbers minus 1, p.sub.1-1, p.sub.2-1, . . . p.sub.k-1, is relatively prime to the public key portion e; establishing a private key portion d of a relationship to the public keyportion e of the form d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1)))); computing a composite number, n, as product of the k distinct random prime numbers; encoding a plaintext message data M with the private key portion d to produce asigned message M.sub.S using a relationship of the form M.sub.S.ident.M.sup.d(mod n), where 0.ltoreq.M.ltoreq.n-1; receiving the signed message M.sub.S; and deciphering the signed message to produce the plaintext message data M; wherein p and q are apair of prime numbers that product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein the encoding step isdivided into sub-steps, one sub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the encoding step if the k distinct random primenumbers are used, relative to the number of computational cycles for performing an encoding step if the pair of prime numbers p and q is used instead. .Iaddend.
.Iadd.24. The method of claim 23, wherein the deciphering step includes: decoding the signed message M.sub.S with the public key portion e to produce the plaintext message data M using a relationship of the form M.ident.M.sub.S.sup.e(mod n). .Iaddend.
.Iadd.25. The method according to claim 23, wherein the signed message M.sub.S formed from the plaintext message data M being cryptographically processed at the sender with multi-prime (k>2) RSA public key signing which is characterized bythe composite number n being computed as the product of the k distinct random prime numbers p.sub.1, p.sub.2, . . . p.sub.k, is decipherable by the decoding at the recipient with two-prime RSA public key signing characterized by the composite number mbeing computed as the product of the pair of prime numbers p and q. .Iaddend.
.Iadd.26. The method according to claim 23, wherein n and m include values that are more than 600 digits long. .Iaddend.
.Iadd.27. A method for communicating a message cryptographically processed with RSA public key encryption, comprising the steps of: sending to a recipient a cryptographically processed message formed by assigning a number M to represent themessage in plaintext message form, and cryptographically transforming the assigned number M from the plaintext message form to a number C that represents the message in an encoded form, wherein the number C is a function of the assigned number M, anumber n that is a composite number equaling the product of at least three distinct random prime numbers, wherein 0.ltoreq.M.ltoreq.n-1, and an exponent e that is a number relatively prime to a lowest common multiplier of the at least three distinctrandom prime numbers, wherein the number n and exponent e having been obtained by the sender are associated with the recipient to which the message is intended; and receiving the cryptographically processed message which is decipherable by the recipientbased on the number n, another exponent d, and the number C, wherein the exponent d is a function of the exponent e and the at least three distinct random prime numbers; wherein p and q are a pair of prime numbers that product of which equals acomposite number m, the at least three distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein deciphering the cryptographically processed message is dividedinto sub-steps, one sub-step for each of the at least three distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the deciphering if the at least threedistinct random prime numbers are used, relative to the number of computational cycles for performing a deciphering if the pair of prime numbers p and q is used instead. .Iaddend.
.Iadd.28. The method according to claim 27, wherein the cryptographically transforming step includes using a relationship of the form C.ident.M.sup.e (mod n), wherein the exponent d is established based on the at least three distinct randomprime numbers p.sub.1, p.sub.2, . . . p.sub.k, using a relationship of the form d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))), and wherein the cryptographically processed message is deciphered using a relationship of the formM.ident.C.sup.d(mod n). .Iaddend.
.Iadd.29. The method according to claim 27, wherein a message cryptographically processed by the sender with two-prime RSA public key encryption characterized by the composite number m being computed as the product of the pair of prime numbersp and q, is decipherable at the recipient with multi-prime RSA public key encryption characterized by the composite number n being computed as the product of the at least three distinct random prime numbers. .Iaddend.
.Iadd.30. The method according to claim 27, wherein n and m include values that are more than 600 digits long. .Iaddend.
.Iadd.31. A method for communicating a message cryptographically processed with RSA public key encryption, comprising the steps of: receiving from a sender a cryptographically processed message, in the form of a number C, which is decipherableby the recipient based on a number n, an exponent d, and the number C; and deciphering the cryptographically processed message, wherein a number M represents a plaintext form of the message, wherein the number C represents a cryptographically encodedform of the message and is a function of the number M, the number n that is a composite number equaling the product of at least three distinct random prime numbers, wherein 0.ltoreq.M.ltoreq.n-1, and an exponent e that is a number relatively prime to alowest common multiplier of the at least three distinct random prime numbers, wherein the number n and exponent e are associated with the recipient to which the message is intended, and wherein the exponent d is a function of the exponent e and the atleast three distinct random prime numbers; wherein p and q are a pair of prime numbers that product of which equals a composite number m, the at least three distinct random prime numbers each smaller than p and q, the composite number m having the samenumber of digits as the composite number n; wherein deciphering the cryptographically processed message is divided into sub-steps, one sub-step for each of the at least three distinct random prime numbers; and wherein for a given number of digits forcomposite numbers n and m, it takes fewer computational cycles to perform the deciphering if the at least three distinct random prime numbers are used, relative to the number of computational cycles for performing a deciphering if the pair of primenumbers p and q is used instead. .Iaddend.
.Iadd.32. The method according to claim 31, wherein the number C is formed using a relationship of the form C.ident.M.sup.e (mod n), wherein the exponent d is established based on the at least three distinct random prime numbers p.sub.1,p.sub.2, . . . p.sub.k, using a relationship of the form d.ident.e.sup.-1((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))), and wherein the number M is obtained using a relationship of the form M.ident.C.sup.d(mod n). .Iaddend.
.Iadd.33. The method according to claim 31, wherein a message cryptographically processed by the sender with two-prime RSA public key encryption characterized by the composite number m being computed as the product of the pair of prime numbersp and q, is decipherable at the recipient with multi-prime RSA public key encryption characterized by the composite number n being computed as the product of the at least three distinct random prime numbers. .Iaddend.
.Iadd.34. The method according to claim 31, wherein n and m include values that are more than 600 digits long. .Iaddend.
.Iadd.35. A cryptography method for local storage of data by a private key owner, comprising the steps of: selecting a public key portion e; developing k distinct random prime numbers, p.sub.1, p.sub.2, . . . p.sub.k, where k.gtoreq.3, andchecking that each of the k distinct random prime numbers minus 1, p.sub.1-1, p.sub.2-1, . . . , p.sub.k-1, is relatively prime to the public key portion e; establishing a private key portion d by a relationship to the public key portion e in the formof d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))); computing a composite number, n, as a product of the k distinct random prime numbers that are factors of n, where only the private key owner knows the factors of n; and encodingplaintext data M to ciphertext data C for the local storage, using a relationship of the form C.ident.M.sup.e(mod n), wherein 0.ltoreq.M.ltoreq.n-1, whereby the ciphertext data C is decipherable only by the private key owner having available to it thefactors of n; wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the compositenumber n; wherein the encoding step is divided into sub-steps, one sub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform theencoding step if the k distinct random prime numbers are used, relative to the number of computational cycles for performing an encoding step if the pair of prime numbers p and q is used instead. .Iaddend.
.Iadd.36. The cryptography method in accordance with claim 35, further comprising the steps of: decoding the ciphertext data C from the local storage to the plaintext data M using a relationship of the form M.ident.C.sup.d (mod n). .Iaddend.
.Iadd.37. A cryptographic communications system, comprising: a plurality of stations; a communications medium; and a host system adapted to communicate with the plurality of stations via the communications medium sending and receivingmessages cryptographically processed with an RSA public key encryption, the host system including at least one cryptosystem configured for developing k distinct random prime numbers p.sub.1, p.sub.2, . . . , p.sub.k, where k.gtoreq.3, checking that eachof the k distinct random prime numbers minus 1, p.sub.1-1, p.sub.2-1, . . . p.sub.k-1, is relatively prime to a public key portion e that is associated with the host system, computing a composite number, n, as a product of the k distinct random primenumbers, establishing a private key portion d by a relationship of the public key portion e in the form of d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))), in response to an encoding request from the host system, encoding a plaintextmessage data M producing therefrom a ciphertext message data C to be communicated via the host system, the encoding using a relationship of the form C.ident.M.sup.e(mod n), where 0.ltoreq.M.ltoreq.n-1, and in response to a decoding request from the hostsystem, decoding a ciphertext message data C' communicated via the host producing therefrom a plaintext message data M' using a relationship of the form M'.ident.C'.sup.d(mod n); wherein p and q are a pair of prime numbers that product of which equals acomposite number, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein decoding the ciphertext message data C' is divided into sub-steps, onesub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the decoding of the ciphertext message data C' if the k distinct randomprime numbers are used, relative to the number of computational cycles for performing a decoding of the ciphertext message data C' if the pair of prime numbers p and q is used instead. .Iaddend.
.Iadd.38. The system of claim 37, wherein the at least one cryptosystem includes a plurality of exponentiators configured to operate in parallel in developing respective subtask values corresponding to the message. .Iaddend.
.Iadd.39. The system of claim 37, wherein the at least one cryptosystem includes a processor, a data-address bus, a memory coupled to the processor via the data-address bus, a data encryption standard (DES) unit coupled to the memory and theprocessor via the data-address bus, and a plurality of exponentiator elements coupled to the processor via the DES unit, the plurality of exponentiator elements being configured to operate in parallel in developing respective subtask values correspondingto the message. .Iaddend.
.Iadd.40. The system of claim 39, wherein the memory and each of the plurality of exponentiator elements has its own DES unit that cryptographically processes message data received/returned from/to the processor. .Iaddend.
.Iadd.41. The system of claim 39, wherein the memory is partitioned into address spaces addressable by the processor, including secure, insecure and exponentiator elements address spaces, and wherein the DES unit is configured to recognize thesecure and exponentiator elements address spaces and to automatically encode message data therefrom before it is provided to the exponentiator elements, the DES unit being bypassed when the processor is accessing the insecure memory address spaces, theDES unit being further configured to decode encoded message data received from the memory before it is provided to the processor. .Iaddend.
.Iadd.42. The system of claim 39, wherein the at least one cryptosystem meets FIPS (Federal Information Processing Standard) 140-1 level 3. .Iaddend.
.Iadd.43. The system of claim 39, wherein the processor maintains in the memory the public key portion e and the composite number n with its factors p.sub.1, p.sub.2, . . . p.sub.k. .Iaddend.
.Iadd.44. A system for communications of a message cryptographically processed with RSA public key encryption, comprising: a bus; and a cryptosystem communicatively coupled to and receiving from the bus encoding and decoding requests, thecryptosystem being configured for providing a public key portion e, developing k distinct random prime numbers p.sub.1, p.sub.2, . . . , p.sub.k, where k.gtoreq.3, checking that each of the k distinct random prime numbers minus 1, p.sub.1-1, p.sub.2-1,. . . p.sub.k.sub.1, is relatively prime to the public key portion e, computing a composite number, n, as a product of the k distinct random prime numbers, establishing a private key portion d by a relationship to the public key portion e in the form ofd.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))), in response to an encoding request from the bus, encoding a plaintext form of a first message M to produce C, a ciphertext form of the first message, using a relationship of the formC.ident.M.sup.e(mod n), wherein 0.ltoreq.M.ltoreq.n-1, and in response to a decoding request from the host system, decoding C', a ciphertext form of a second message, to produce M', a plaintext form of the second message, using a relationship of the formM'.ident.C'.sup.d(mod n), the first and second messages being distinct or one and the same; wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, andthe composite number m having the same number of digits as the composite number n; wherein decoding C' is divided into sub-steps, one sub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for compositenumbers n and m, it takes fewer computational cycles to perform the decoding of C' if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a decoding of C' if the pair of prime numbers p and q isused instead. .Iaddend.
.Iadd.45. A system for communications of a message cryptographically processed with RSA public key encryption, comprising: a bus; and a cryptoplasm receiving from the system via the bus encoding and decoding requests, the cryptosystemincluding a plurality of exponentiator elements configured to develop subtask values, a memory, and a processor configured for receiving the encoding and decoding requests, each encoding request providing a plaintext message M to be encoded, obtaining apublic key that includes an exponent e and a modulus n, a representation of the modulus n existing in the memory in the form of its k distinct random prime number factors p.sub.1, p.sub.2, . . . p.sub.k, where k.gtoreq.3, constructing subtasks, onesubtask for each of the k factors, to be executed by the exponentiator elements for producing respective ones of the subtask values C.sub.1, C.sub.2, . . . C.sub.k, and forming a ciphertext message C from the subtask values C.sub.1, C.sub.2, . . .C.sub.k, wherein the ciphertext message C is decipherable using a private key that includes the modulus n and an exponent d which is a function of e; wherein p and q are a pair of prime numbers that product of which equals a modulus m, the k distinctrandom prime numbers each smaller than p and q, and the modulus m having the same number of digits as the modulus n; and wherein for a given number of digits for modulus n and modulus m, it takes fewer computational cycles to form the ciphertext messageC if the k distinct random prime numbers are used, relative to the number of computational cycles for forming a ciphertext message C' if the pair of prime numbers p and q is used instead. .Iaddend.
.Iadd.46. The system of claim 45, wherein each one of the subtask values C.sub.1, C.sub.2, . . . C.sub.k is developed using a relationship of the form C.sub.i.ident.M.sub.i.sup.e.sup.i (mod p.sub.i), where M.sub.i.ident.M(mod p.sub.i), ande.sub.i.ident.e(mod p.sub.i-1), and where i=1, 2, . . . k. .Iaddend.
.Iadd.47. A system for communications of a message cryptographically processed with RSA public key encryption, comprising: a bus; and a cryptosystem receiving from the system via the bus encoding and decoding requests, the cryptosystemincluding a plurality of exponentiator elements configured to develop subtask values, a memory, and a processor configured for receiving the encoding and decoding requests, each encoding/decoding request provided with a plaintext/ciphertext message M/Cto be encoded/decoded and with or without a public/private key that includes an exponent e/d and a modulus n representation of which exists in the memory in the form of its k distinct random prime number p.sub.1, p.sub.2, . . . p.sub.k, wherek.gtoreq.3, obtaining the public/private key from the memory if the encoding/decoding request is provided without the public/private key, constructing subtasks to be executed by the exponentiator elements for producing respective ones of the subtaskvalues M.sub.1, M.sub.2, . . . M.sub.k/C.sub.1, C.sub.2, . . . C.sub.k, and forming the ciphertext/plaintext message C/M from the subtask values C.sub.1, C.sub.2, . . . C.sub.k/M.sub.1, M.sub.2, . . . M.sub.k; wherein p and q are a pair of primenumbers that product of which equals a modulus m, the k distinct random prime numbers each smaller than p and q, and the modulus m having the same number of digits as the modulus n; and wherein for a given number of digits for modulus n and modulus m,it takes fewer computational cycles to form the ciphertext/plaintext message C/M if the k distinct random prime numbers are used, relative to the number of computational cycles for forming a ciphertext/plaintext message C'/M' if the pair of prime numbersp and q is used instead. .Iaddend.
.Iadd.48. The system of claim 47 wherein when produced each one of the subtasks C.sub.1, C.sub.2, . . . C.sub.k is developed using a relationship of the form C.sub.i.ident.M.sub.i.sup.e.sup.i (mod p.sub.i), where C.sub.i.ident.C(mod p.sub.i),and e.sub.i.ident.e(mod p.sub.i-1), and where i=1, 2, . . . , k. .Iaddend.
.Iadd.49. The system of claim 47 wherein when produced each one of the subtasks M.sub.1, M.sub.2, . . . M.sub.k is developed using a relationship of the form M.sub.i.ident.C.sub.i.sup.d.sup.i (mod p.sub.i), where M.sub.i.ident.M(mod p.sub.i),and d.sub.i=d(mod p.sub.i-1), and where i=1, 2, . . . , k. .Iaddend.
.Iadd.50. The system of claim 49, wherein the private key exponent d relates to the public key exponent e via d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))). .Iaddend.
.Iadd.51. A system for communications of a message cryptographically processed with RSA public key encryption, comprising: means for selecting a public key portion e; means for developing k distinct random prime number p.sub.1, p.sub.2, . . .p.sub.k, where k.gtoreq.3, and for checking that each of the k distinct random prime numbers minus 1, p.sub.1-1, p.sub.2-1, . . . p.sub.k-1, is relatively prime to the public key portion e; means for establishing a private key portion of d by arelationship to the public key portion e in the form of d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))); means for computing a composite number, n, as a product of the k distinct random prime numbers; means for receiving a ciphertextmessage data C; and means for decoding the ciphertext message data C to a plaintext message data M using a relationship of the form M.ident.C.sup.d(mod n); wherein p and q are a pair of prime numbers that product of which equals a composite number m,the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein decoding said ciphertext message data C is divided into sub-steps, one sub-step for each of thek distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the decoding of said ciphertext message data C if the k distinct random prime numbers are used,relative to the number of computational cycles for performing a decoding of said ciphertext message data C if the pair of prime numbers p and q is used instead. .Iaddend.
.Iadd.52. The system according to claim 51, further comprising: means for encoding the plaintext message data M to the ciphertext message data C, using a relationship of the form C.ident.M.sup.e (mod n), where 0.ltoreq.M.ltoreq.n-1. .Iaddend.
.Iadd.53. A system for communications of a message cryptographically processed with RSA public key signing, comprising: means for selecting a public key portion e; means for developing k distinct random prime numbers p.sub.1, p.sub.2, . . .p.sub.k, where k.gtoreq.3, and for checking that each of the k distinct random prime numbers minus 1, p.sub.1-1, p.sub.2-1, . . . p.sub.k-1, is relatively prime to the public key portion e; means for establishing a private key portion d by arelationship to the public key portion e of the form d.ident.e.sup.-1(mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1))); means for computing a composite number, n, as a product of the k distinct random prime numbers; and means for encoding a plaintextmessage data M with the private key portion d to produce a signed message M.sub.S, using a relationship of the form M.sub.S.ident.M.sup.d(mod n), where 0.ltoreq.M.ltoreq.n-1, the signed message M.sub.S being decipherable using the public key portion e; wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; whereinencoding said plaintext message data M is divided into sub-steps, one sub-step for each of the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform theencoding of said plaintext message data M if the k distinct random prime numbers are used, relative to the number of computational cycles for performing an encoding of said plaintext message data M if the pair of prime numbers p and q is used instead. .Iaddend.
.Iadd.54. The system of claim 53 further comprising: means for decoding the signed message M.sub.S with the public key portion e to produce the plaintext message data M using a relationship of the form M.ident.M.sub.S.sup.e(mod n). .Iaddend.
.Iadd.55. The system of claim 52, wherein the system can communicate the cryptographically processed message to another system that encodes/decodes data with RSA public key encryption using a modulus value equal to n independent of the kdistinct prime numbers. .Iaddend.
.Iadd.56. The system of claim 54, wherein the system can communicate the cryptographically processed message to another system that encodes/decodes data with RSA public key signing using a modulus value equal to n independent of the k distinctprime numbers. .Iaddend. |
| Description: |
BACKGROUND OF THE INVENTION
This invention relates generally to communicating data in a secure fashion, and more particularly to a cryptographic system and methods using public key cryptography.
Computer systems are found today in virtually every walk of life for storing, maintaining, and transferring various types of data. The integrity of large portions of this data, especially that portion relating to financial transactions, is vitalto the health and survival of numerous commercial enterprises. Indeed, as open and unsecured data communications channels for sales transactions gain popularity, such as credit card transactions over the Internet, individual consumers have an increasingstake in data security.
Thus, for obvious reasons, it is important that financial transaction communications pass from a sender to an intended receiver without intermediate parties being able to interpret the transferred message.
Cryptography, especially public key cryptography, has proven to be an effective and convenient technique of enhancing data privacy and authentication. Data to be secured, called plaintext, is transformed into encrypted data, or ciphertext, by apredetermined encryption process of one type or another. The reverse process, transforming ciphertext into plaintext, is termed decryption. Of particular importance to this invention is that the processes of encryption and decryption are controlled bya pair of related cryptographic keys. A "public" key is used for the encryption process, and a "private" key is used to decrypt ciphertext. The public key transforms plaintext to ciphertext, but cannot be used to decrypt the ciphertext to retrieve theplaintext therefrom.
As an example, suppose a Sender A wishes to send message M to a recipient B. The idea is to use public key E and related private key D for encryption and decryption of M. The public key E is public information while D is kept secret by theintended receiver. Further, and importantly, although E is determined by D, it is extremely difficult to compute D from E. Thus the receiver, by publishing the public key E, but keeping the private key D secret, can assure senders of data encryptedusing E that anyone who intercepts the data will not be able to decipher it. Examples of the public key/private key concept can be found in U.S. Pat. Nos. 4,200,770, 4,218,582, and 4,424,414.
The prior art includes a number of public key schemes, in addition to those described in the above-identified patents. Over the past decade, however, one system of public key cryptography has gained popularity. Known generally as the "RSA"scheme, it is now thought by many to be a worldwide defacto standard for public key cryptography. The RSA scheme is described in U.S. Pat. No. 4,405,829 which is fully incorporated herein by this reference.
The RSA scheme capitalizes on the relative ease of creating a composite number from the product of two prime numbers whereas the attempt to factor the composite number into its constituent primes is difficult. The RSA scheme uses a public key Ecomprising a pair of positive integers n and e, where n is a composite number of the form n=pq (1) where p and q are different prime numbers, and e is a number relatively prime to (p-1) and (q-1); that is, e is relatively prime to (p-1) or (q-1) if e hasno factors in common with either of them. Importantly, the sender has access to n and e, but not to p and q. The message M is a number representative of a message to be transmitted wherein 0.ltoreq.M<n-1. (2) The sender enciphers M to createciphertext C by computing the exponential .[.C=M.sup.e(mod n).]. .Iadd.C.ident.M.sup.e(mod n).Iaddend.. (3)
The recipient of the ciphertext C retrieves the message M using a (private) decoding key D, comprising a pair of positive integers d and n, employing the relation .[.M=C.sup.d(mod n).]. .Iadd.M.ident.C.sup.d(mod n) .Iaddend. (4)
As used in (4), above, d is a multiplicative inverse of e(mod(lcm((p-1), (q-1)))) (5) so that .[.ed=1(mod(lcm((p-1), (q-1)))).]. .Iadd.ed.ident.1(mod(lcm((p-1), (q-1)))) .Iaddend. (6) where lcm((p-1), (q-1)) is the least common multiple ofnumbers p-1 and q-1. Most commercial implementations of RSA employ a different, although equivalent, relationship for obtaining d: .[.d=e.sup.-1mod(p-1) (q-1).]. .Iadd.d.ident.e.sup.-1mod((p-1)(q-1)).Iaddend.. (7) This alternate relationship simplifiescomputer processing.
Note: Mathematically (6) defines a set of numbers and (7) defines a subset of that set. For implementation, (7) or (6) usually is interpreted to mean d is the smallest positive element in the set.)
The net effect is that the plaintext message M is encoded knowing only the public key E (i.e., e and n). The resultant ciphertext C can only decoded using decoding key D. The composite number n, which is part of the public key E, iscomputationally difficult to factor into its components, prime numbers p and q, a knowledge of which is required to decrypt C.
From the time a security scheme, such as RSA, becomes publicly known and used, it is subjected to unrelenting attempts to break it. One defense is to increase the length (i.e., size) of both p and q. Not long ago it was commonly recommended thatp and q should be large prime numbers 75 digits long (i.e., on the order of 10.sup.75). Today, it is not uncommon to find RSA schemes being proposed wherein the prime numbers p and q are on the order of 150 digits long. This makes the product of p andq a 300 digit number. (There are even a handful of schemes that employ prime numbers (p and q) that are larger, for example 300 digits long to form a 600 digit product.) Numbers of this size, however, tend to require enormous computer resources toperform the encryption and decryption operations. Consider that while computer instruction cycles are typically measured in nanoseconds (billionths of seconds), computer computations of RSA steps are typically measured in milliseconds (thousandths ofseconds). Thus millions of computer cycles are required to compute individual RSA steps resulting in noticeable delays to users.
This problem is exacerbated if the volume of ciphertext messages requiring decryption is large--such as can be expected by commercial transactions employing a mass communication medium such as the Internet. A financial institution may maintainas Internet site that could conceivably receive thousands of enciphered messages every hour that must be decrypted, and perhaps even responded to. Using larger numbers to form the keys used for an RSA scheme can impose severe limitations and restraintsupon the institution's ability to timely respond.
Many prior art techniques, while enabling the RSA scheme to utilize computers more efficiently, nonetheless have failed to keep pace with the increasing length of n, p, and q.
Accordingly, it is an object of this invention to provide a system and method for rapid encryption and decryption of data without compromising data security.
It is another object of this invention to provide a system and method that increases the computational speed of RSA encryption and decryption techniques.
It is still another object of this invention to provide a system and method for implementing an RSA scheme in which the .[.components.]. .Iadd.factors .Iaddend.of n do not increase in length as n increases in length.
It is still another object to provide a system and method for utilizing multiple (more than two), distinct prime number .[.components.]. .Iadd.factors .Iaddend.to create n.
It is a further object to provide a system and method for providing a technique for reducing the computational effort for calculating exponentiations in an RSA scheme for a given length of n.
SUMMARY OF THE INVENTION
The present invention discloses a method and apparatus for increasing the computational speed of RSA and related public key schemes by focusing on a neglected area of computation inefficiency. Instead of n=pq, as is universal in the prior art,the present invention discloses a method and apparatus wherein n is developed from three or more distinct .Iadd.random .Iaddend.prime numbers; i.e., n=p.sub.1p.sub.2. . . p.sub.k, where k is an integer greater than 2 and p.sub.1, p.sub.2, . . . p.sub.kare sufficiently large distinct .Iadd.random .Iaddend.primes. Preferably, "sufficiently large primes" are prime numbers that are numbers approximately 150 digits long or larger. The advantages of the invention over the prior art should be immediatelyapparent to those skilled in this art. If, as in the prior art, p and q are each on the order of, say, 150 digits long, then n will be on the order of 300 digits long. However, three primes p.sub.2, p.sub.1, and p.sub.3 employed in accordance with thepresent invention can each be on the order of 100 digits long and still result in n being 300 digits long. Finding and verifying 3 distinct primes, each 100 digits long, requires significantly fewer computational cycles than finding and verifying 2primes each 150 digits long.
The commercial need for longer and longer primes shows no evidence of slowing; already there are projected requirements for n of about 600 digits long to forestall incremental improvements in factoring techniques and the ever faster computersavailable to break ciphertext. The invention, allowing 4 primes each about 150 digits long to obtain a 600 digit n, instead of two primes about .[.350.]. .Iadd.300 .Iaddend.digits long, results in a marked improvement in computer performance. For, notonly are primes that are 150 digits in size easier to find and verify than ones on the order of .[.350.]. .Iadd.300 .Iaddend.digits, but by applying techniques the inventors derive from the Chinese Remainder Theorem (CRT), public key cryptographycalculations for encryption and decryption are completed much faster--even if performed serially on a single processor system. However, the inventors' techniques are particularly adapted to .[.be.]. advantageously apply .[.enable.]. .Iadd.RSA.Iaddend.public key .Iadd.cryptographic .Iaddend.operations to parallel computer processing.
The present invention is capable of .[.using.]. .Iadd.extending .Iaddend.the RSA scheme to perform encryption and decryption operation using a large (many digit) n much faster than heretofore possible. Other advantages of the invention includeits employment for decryption without the need to revise the RSA public .Iadd.key .Iaddend.encryption transformation scheme currently in use on thousands of large and small computers.
A key assumption of the present invention is that n, composed of 3 or more sufficiently large distinct prime numbers, is no easier (or not very much easier) to factor than the prior art, two prime number n. The assumption is based on theobservation that there is no indication in the prior art literature that it is "easy" to factor a product consisting of more than two sufficiently large, distinct prime numbers. This assumption may be justified given the continued effort (and failure)among experts to find a way "easily" to break large .[.component.]. .Iadd.composite .Iaddend.numbers into their large prime factors. This assumption is similar, in the inventors' view, to the assumption underlying the entire field of public keycryptography that factoring composite numbers made up of two distinct primes is not "easy." That is, the entire field of public key cryptography is based not on mathematical proof, but on the assumption that the empirical evidence of failed sustainedefforts to find a way systematically to solve NP problems in polynomial time indicates that these problems truly are "difficult."
The invention is preferably implemented in a system that employs parallel operations to perform the encryption, decryption operations required by the RSA scheme. Thus, there is also disclosed a cryptosystem that includes a central processor unit(CPU) coupled to a number of exponentiator elements. The exponentiator elements are special purpose arithmetic units designed and structured to be provided message data M, an encryption key e, and a number n (where .[.n=p.sub.1*p.sub.2* . . .p.sub.k.]. .Iadd.n=p.sub.1p.sub.2 . . . p.sub.k,.Iaddend. k being greater than 2) and return ciphertext C according to the relationship, .[.C=M.sup.e(mod(n)).]. .Iadd.C.ident.M.sup.e(mod n).Iaddend..
Alternatively, the exponentiator elements may be provided the ciphertext C, a decryption (private) key d and n to return M according to the relationship, .[.M=C.sup.d(mod(n)).]. .Iadd.M.ident.C.sup.d(mod n).Iaddend..
According to this .Iadd.decryption .Iaddend.aspect of the invention, the CPU receives a task, such as the requirement to decrypt .[.cyphertext.]. .Iadd.ciphertext .Iaddend.data C. The CPU will also be provided, or have available, a .[.public.]. .Iadd.private .Iaddend.key .[.e.]. .Iadd.d .Iaddend.and n, and the factors of n (p.sub.1, p.sub.2, . . . p.sub.k). The CPU breaks the .[.encryption.]. .Iadd.decryption .Iaddend.task down into a number of sub-tasks, and delivers the sub-tasks to theexponentiator elements. .[.When the.]. .Iadd.The .Iaddend.results of the sub-tasks are returned by the exponentiator elements to the CPU which .[.will.]. , using a form of the CRT, combine.Iadd.s .Iaddend.the results to obtain the message data M. Anencryption task may be performed essentially in the same manner by the CPU and its use of the exponentiator elements. However, usually the factors of n are not available to the sender (encryptor), only the public key, e and n, so that no sub-tasks arecreated.
In a preferred embodiment of this latter aspect of the invention, the bus structure used to couple the CPU and exponentiator elements to one another is made secure by encrypting all important information communicated thereon. Thus, data sent tothe exponentiator elements is passed through a data encryption unit that employs, preferably, the ANSI Data Encryption Standard (DES). The exponentiator elements decrypt the DES-encrypted sub-task information they receive, perform the desired task, andencrypt the result, again using DES, for return to the CPU.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a simplified block diagram of a cryptosystem architecture configured for use in the present invention.
FIG. 2 is a memory map of the address space of the cryptosystem of FIG. 1; and
FIG. 3 is an exemplary illustration of one use of the invention.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
As indicated above, the present invention is employed in the context of the RSA public key encryption/decryption scheme. As also indicated, the RSA scheme obtains its security from the difficulty of factoring large numbers, and the fact that thepublic and private keys are functions of a pair of large (100-200 digits or even larger) prime numbers. Recovering the plaintext from the public key and the ciphertext is conjectured to be equivalent to factoring the product of two primes.
According to the present invention, the public key portion e is picked. Then, three or more random large, distinct prime numbers, p.sub.1, p.sub.2, . . . , p.sub.k are developed and checked to ensure that each .Iadd.(p.sub.i-1) .Iaddend.isrelatively prime to e. Preferably, the prime numbers are of equal length. Then, the product .[.n=p.sub.1, p.sub.2, . . . , p.sub.k.]. .Iadd.n=p.sub.1p.sub.2 . . . p.sub.k, .Iaddend.is computed.
Finally, the decryption .[.key.]. .Iadd.exponent.Iaddend., d, is established by the relationship: .[.d=e.sup.-1mod ((p.sub.1-1) (p.sub.2-1)) . . . (p.sub.k-1)).]. .Iadd.d.ident.e.sup.-1mod((p.sub.1-1)(p.sub.2-1) . . . (p.sub.k-1)), orequivalently d.ident.e.sup.-1mod(lcm((p.sub.1-1), (p.sub.2-1), . . . (p.sub.k-1))) .Iaddend.
The message data, M is encrypted to ciphertext C using the relationship of (3), above, i.e., .[.C=M.sup.emod n.]. .Iadd.C.ident.M.sup.e(mod n).Iaddend..
To decrypt the ciphertext, C, the relationship of .[.(3).]. .Iadd.(4).Iaddend., above, is used: .[.M=C.sup.dmod n.]. .Iadd.M.ident.C.sup.d(mod n) .Iaddend. where n and d are those values identified above.
.Iadd.Alternatively, a message data M can be encoded with the private key to a signed message data M.sub.s using a relationship of the form M.sub.s.ident.M.sup.d(mod n).
The message data M can be reproduce from the signed message data M.sub.s by decoding the signed data with the public key, using a relationship of the form M.ident.M.sub.s.sup.e(mod n). .Iaddend.
Using the present invention involving three primes to develop the product n, RSA encryption and decryption time can be substantially less than an RSA scheme using two primes by dividing the encryption or decryption task into sub-tasks, onesub-task for each distinct prime. (However, breaking the encryption or decryption into subtasks requires knowledge of the factors of n. This knowledge is not usually available to anyone except the owner of the key, so the encryption process can beaccelerated only in special cases, such as encryption for local storage. A system encrypting data for another user performs the encryption process according to (3), independent of the number of factors of n. Decryption, on the other hand, is performedby the owner of a key, so the factors of n are generally known and can be used to accelerate the process.) For example, assume that three distinct primes, p.sub.1, p.sub.2, and p.sub.3, are used to develop the product n. Thus, decryption of theciphertext, C, using the relationship .[.M=C.sup.d(mod n).]. .Iadd.M.ident.C.sup.d(mod n) .Iaddend. is used to develop the decryption sub-tasks: .[.M.sub.1=C.sub.1.sup.d.sup.1mod p.sub.1.]. .Iadd.M.sub.1.ident.C.sub.1.sup.d.sup.1(mod p.sub.1) .Iaddend. .[.M.sub.2=C.sub.2.sup.d.sup.2mod p.sub.2.]. .Iadd.M.sub.2.ident.C.sub.2.sup.d.sup.2(mod p.sub.2) .Iaddend. .[.M.sub.3=C.sub.3.sup.d.sup.3mod p.sub.3.]. .Iadd.M.sub.3.ident.C.sub.3.sup.d.sup.3(mod p.sub.3) .Iaddend. where .[.C.sub.1=Cmod p.sub.1;.]..Iadd.C.sub.1.ident.C(mod p.sub.1); .Iaddend. .[.C.sub.2=Cmod p.sub.2;.]. .Iadd.C.sub.2.ident.C(mod p.sub.2); .Iaddend. .[.C.sub.3=Cmod p.sub.3;.]. .Iadd.C.sub.3.ident.C(mod p.sub.3); .Iaddend. .[.d.sub.1=dmod (p.sub.1-1).]..Iadd.d.sub.1.ident.d(mod(p.sub.1-1)).Iaddend.; .[.d.sub.2=dmod (p.sub.2-1).]. .Iadd.d.sub.2.ident.d(mod(p.sub.2-1)).Iaddend.; and .[.d.sub.3=dmod (p.sub.3-1).]. .Iadd.d.sub.3.ident.d(mod(p.sub.3-1)).Iaddend..
The results of each sub-task, M.sub.1, M.sub.2, and M.sub.3 can be combined to produce the plaintext, M, by a number of techniques. However, it is found that they can most expeditiously be combined by a form of the Chinese Remainder Theorem(CRT) using, preferably, a recursive scheme. Generally, the plaintext M is obtained from the combination of the individual sub-tasks by the following relationship: .[.Y.sub.i=Y.sub.i-1+[(M.sub.i-Y.sub.i-1) (w.sub.i.sup.-1mod p.sub.i)modp.sub.i]w.sub.imod n.]. .Iadd.Y.sub.i.ident.Y.sub.i-1+((M.sub.1-Y.sub.i-1)(w.sub.i.sup.-1(mod p.sub.i)))mod p.sub.i))w.sub.i(mod n).Iaddend. where .[.i.gtoreq.2.]. .Iadd.2.ltoreq.i.ltoreq.k .Iaddend. .Iadd.where k is the number of prime factors ofn.Iaddend., and .times. .times..times. .times.< .times. .times. ##EQU00001## Encryption is performed in much the same manner as that used to obtain the plaintext M, provided (as noted above) the factors of n are available. Thus, the relationship.[.C=M.sup.e(mod n).]. .Iadd.C.ident.M.sup.e(mod n).Iaddend., can be broken down into the three sub-tasks, .[.C.sub.1=M.sub.1.sup.e1mod p.sub.1.]. .Iadd.C.sub.1.ident.M.sub.1.sup.e.sup.1(mod p.sub.1), .Iaddend. .[.C.sub.2=M.sub.2.sup.e2mod p.sub.2.]. .Iadd.C.sub.2.ident.M.sub.2.sup.e.sup.2(mod p.sub.2) and .Iaddend. .[.C.sub.3=M.sub.3.sup.e3mod p.sub.3.]. .Iadd.C.sub.3.ident.M.sub.3.sup.e.sup.3(mod p.sub.3), .Iaddend. where .[.M.sub.1=M(mod p.sub.1).]. .Iadd.M.sub.1.ident.M (mod p.sub.1).Iaddend.,.[.M.sub.2=M(mod p.sub.2).]. .Iadd.M.sub.2.ident.M (mod p.sub.2).Iaddend., .[.M.sub.3=M(mod p.sub.3).]. .Iadd.M.sub.3.ident.M (mod p.sub.3).Iaddend., .[.e.sub.1=emod (p.sub.1-1).]. .Iadd.e.sub.1.ident.e (mod(p.sub.1-1)).Iaddend., .[.e.sub.2=emod(p.sub.2-1).]. .Iadd.e.sub.2.ident.e(mod(p.sub.2-1).Iaddend., and .[.e.sub.3=emod (p.sub.3-1).]. .Iadd.e.sub.3.ident.e(mod(p.sub.3-1)). .Iaddend.
In generalized form, the .[.decrypted.]. .Iadd.ciphertext C (i.e., encrypted .Iaddend.message M.Iadd.) .Iaddend.can be obtained by .[.the same summation.]. .Iadd.a recursive scheme as .Iaddend.identified above to obtain the ciphertext C fromits contiguous constituent sub-tasks C.sub.i.
Preferably, the recursive CRT method described above is used to obtain either the ciphertext.[.,.]. C.[.,.]. or the deciphered plaintext (message) M due to its speed. However, there may be .[.occasions.]. .Iadd.implementations .Iaddend.whenit is beneficial to use a non-recursive technique in which case the following relationships are used: .ident. .times. .times..function..function..times. .times..function..times. .times..times. .times. .times. .times..function..times..times. .times..times..times..times. .times..times. ##EQU00002## where .times..noteq. .times. .times..times. .times. ##EQU00003## .noteq. .times. .times. .times. ##EQU00003.2## k is the number (3 or more) of distinct primes chosen to develop theproduct n.
Thus, for example above (k=3), M is constructed from the returned sub-task values M.sub.1, M.sub.2, M.sub.3 by the relationship .[.M=M.sub.1(w.sub.1.sup.-1mod p.sub.1) w.sub.1mod/n+M.sub.2(w.sub.2.sup.-1mod p.sub.2) w.sub.2modn+M.sub.3(w.sub.3.sup.-1mod p.sub.3) w.sub.3mod n.]. .Iadd.M=M.sub.1.sup.-1(w.sub.1.sup.-1(mod p.sub.1))w.sub.1(mod n)+M.sub.2(w.sub.2.sup.-1(mod p.sub.2))w.sub.2(mod n)+M.sub.3(w.sub.3.sup.-1(mod p.sub.3))w.sub.3(mod n) .Iaddend. wherew.sub.1=p.sub.2p.sub.3, w.sub.2=p.sub.1p.sub.3, and w.sub.3=p.sub.1p.sub.2.
Employing the multiple distinct prime number technique of the present invention in the RSA scheme can realize accelerated processing over that using only two primes for the same size n. The invention can be implemented on a single processor unitor even the architecture disclosed in the above-referenced U.S. Pat. No. 4,405,829. The capability of developing sub-tasks for each prime number is particularly adapted to employing a parallel architecture such as that illustrated in FIG. 1.
Turning to FIG. 1, there is illustrated a cryptosystem architecture apparatus capable of taking particular advantage of the present invention. The cryptosystem, designated with the reference numeral 10, is structured to form a part of a largerprocessing system (not shown) that would deliver to the cryptosystem 10 encryption and/or decryption requests, receiving in return the object of the request--an encrypted or decrypted value. The host would include a bus structure 12, such as aperipheral component interface (PCI) bus for communicating with the cryptosystem 10.
As FIG. 1 shows, The cryptoprocessor 10 includes a central processor unit (CPU) 14 that connects to the bus structure 12 by a bus interface 16. The CPU 14 comprises a processor element 20, a memory unit 22, and a data encryption standard (DES)unit 24 interconnected by a data/address bus 26. The DES unit 24, in turn, connects to an input/output (I/O) bus 30 (through appropriate driver/receiver circuits--not shown).
The I/O bus 30 communicatively connects the CPU to a number of exponentiator elements .[.32.sub.a, 32.sub.b, and 32.sub.c.]. .Iadd.32a, 32b and 32c.Iaddend.. Shown here are three exponentiator elements, although as illustrated by the "other"exponentiators .[.32.sub.n.]. .Iadd.32n.Iaddend., additional exponentiator elements can be added. Each exponentiator element is a state machine controlled arithmetic circuit structured specifically to implement the relationship described above. Thus,for example, the exponentiator 32a would be provided the values M.sub.1, e.sub.1, and p.sub.1 n.]. to develop C.sub.1. Similarly, the exponentiator circuits 32b and 32c develop C.sub.2 and C.sub.3 from corresponding subtask values M.sub.2, e.sub.2,.[.P.sub.2.]. .Iadd.p.sub.2.Iaddend., M.sub.3, e.sub.3, and .[.P.sub.3.]. .Iadd.p.sub.3.Iaddend..
Preferably, the CPU 14 is formed on a single integrated circuit for security reasons. However, should there be a need for more storage space than can be provided by the "on-board" memory 22, the bus 30 may also connect the CPU 14 to an externalmemory unit 34.
In order to ensure a secure environment, it is preferable that the cryptosystem 10 meet the Federal Information .[.Protection System.]. .Iadd.Processing Standard .Iaddend.(FIPS) .Iadd.140-1 .Iaddend.level 3. Accordingly, the elements that makeup the CPU 14 would be implemented in a design that will be secure from external probing of the circuit. However, information communicated on the I/O bus 30 between the CPU 14 and the exponentiator circuits 32 (and external memory 34--if present) isexposed. Consequently, to maintain the security of that information, it is first encrypted by the DES unit 24 before it is placed on the I/O bus 30 by the CPU 14. The exponentiator circuits 32, as well as the external memory 34, will also includesimilar DES units to decrypt information received from the CPU, and later to encrypt information returned to the CPU 14.
It may be that not all information communicated on the I/O bus 30 need be secure by DES encryption. For that reason, the DES unit 24 of the CPU 14 is structured to encrypt outgoing information, and decrypt incoming information, on the basis ofwhere in the address space used by the cryptosystem the information belongs; that is, since information communicated on the I/O bus 30 is either a write operation by the CPU 14 to the memory 34, or a read operation of those elements, the addressesassigned to the secure addresses and non-secure addresses. Read or write operations conducted by the CPU 14 using secure addresses will pass through the DES unit 24 and that of the memory 34. Read or write operations involving non-secure addresses willby-pass these DES units.
FIG. 2 diagrammatically illustrates a memory map 40 of the address space of the cryptosystem 10 that is addressable by the processor 20. As the memory map 30 shows, an address range 30 provides addresses for the memory 22, and such other supportcircuitry (e.g., registers--not shown) that may form a part of the CPU 14. The addresses used to write information to, or read information from, the exponentiator elements 32 are in the address range 44 of the memory map 40. The addresses for theexternal memory 34 are in the address ranges 46, and 48. The address ranges 44 and 46 are for secure read and write operations. Information that must be kept secure, such as instructions for implementing algorithms, encryption/decryption keys, and thelike, if maintained in external memory 34, will be stored at locations having addresses in the address range 46. Information that need not be secure such as miscellaneous algorithms data, general purpose instructions, etc. are kept in memory locationsof the external memory 34 having addresses within the address range 48.
The DES unit 24 is structured to recognize addresses in the memory spaces 44, 46, and to automatically encrypt the information before it is applied to the I/O bus 30. The DES unit 24 is bypassed when the processor 20 accesses addresses in theaddress range 48. Thus, when the processor 20 initiates write operations to addresses within the memory space within the address range 46 (to the external memory 34), the DES unit 24 will automatically encrypt the information (not the addresses) andplace the encrypted information on the I/O bus 30. Conversely, when the processor 20 reads information from the external memory 34 at addresses within the address range 46 of the external memory 34, the DES unit will decrypt information received fromthe I/O bus 30 and place the decrypted information on the data/address bus 26 for the processor 20.
In similar fashion, information conveyed to or retrieved from the exponentiators 32 by the processor 20 by write or read operations at addresses within the address range 44. Consequently, writes to the exponentiators 32 will use the DES unit 24to encrypt the information. When that (encrypted) information is received by the exponentiators 32, it is decrypted by on-board DES units (of each exponentiator 32). The result.[.s.]. of the task performed by the exponentiator 32 is then encrypted bythe exponentiator's on-board DES unit, retrieved by the processor 20 in encrypted form and then decrypted by the DES unit 24.
Information that need not be maintained in secure fashion to be stored in the external memory 34, however, need only be written to addresses in the address range 48. The DES unit 24 recognizes writes to the address range 48, and bypasses theencryption circuitry, passing the information, in unencrypted form, onto the I/O bus 30 for storing in the external memory 34. Similarly, reads of the external memory 34 using addresses within the address range 48 are passed directly from the I/O bus 30to the data/address bus 26 by the DES unit 24.
In operation, the CPU 14 will receive from the host it serves (not shown), via the bus 12, an encryption request. The encryption request will include the message data M to be encrypted and, perhaps, the encryption keys e and n (in the form ofthe primes p.sub.1, p.sub.2, . . . p.sub.k). Alternatively, the keys may be kept by the CPU 14 in the memory 22. In any event, the processor 20 will construct the encryption sub-tasks C.sub.1, C.sub.2, . . . , C.sub.k for execution by theexponentiators 32.
Assume, for the purpose of the remainder of this discussion, that the encryption/decryption tasks performed by the cryptosystem 10, using the present invention, employs only three distinct primes, p.sub.1, p.sub.2, p.sub.3. The processor 20 willdevelop the sub tasks identified above, using M, e, p.sub.1 p.sub.2, p.sub.3 Thus, for example, if the exponentiator 32a were assigned the sub-task of developing C.sub.1, the processor would develop the values M.sub.1.[.,.]. .Iadd.and.Iaddend.e.sub.1.[., and (p.sub.1-1).]. and deliver .[.units.]. (write) these values, with .[.n,.]. .Iadd.p.sub.1 .Iaddend.to the exponentiator 32a. Similar values will be developed by the processor 20 for the sub-tasks that will be delivered to theexponentiators 32b and 32c.
In turn, the exponentiators 32 develop the values C.sub.1, C.sub.2, and C.sub.3 which are returned to (retrieved by) the CPU 14. The processor 20 will then combine the values C.sub.1, C.sub.2, and C.sub.3 to form C, the ciphertext encryption ofM, which is then returned to the host via the bus 12.
The encryption, decryption techniques described hereinabove, and the use of cryptosystem 10 (FIG. 1) can find use in a number of diverse environments. Illustrated in FIG. 3 is one such environment. FIG. 3 shows a host system 50, including thebus 12 connected to a plurality of cryptosystems 10 (10a, 10b, . . . , 10m) structured as illustrated in FIG. 1, and described above. In turn, the host system 50 connects to a communication medium 60 which could be, for example, an internet connectionthat is also used by a number of communicating stations 64. For example, the host system 50 may be employed by a financial institution running a web site accessible, through the communication medium, by the stations 64. Alternatively, the communicationmedium may be implemented by a local area network (LAN) or other type network. Use of the invention described herein is not limited to the particular environment in which it is used, and the illustration in FIG. 3 is not meant to limit in any way howthe invention can be used.
As an example, the host system, as indicated, may receive encrypted communication from the stations 64, via the communication medium 60. Typically, the data of the communication will be encrypted using DES, and the DES key will be encryptedusing a public key by the RSA scheme, preferably one that employs three or more distinct prime numbers for developing the public and private keys.
Continuing, the DES encrypted communication, including the DES key encrypted with the RSA scheme, would be received by the host system. Before decrypting the DES communication, it must obtain the DES key and, accordingly, the host system 50 willissue, to one of the cryptosystems 10 a decryption request instruction, containing the encrypted DES key as the cyphertext C. If the (private) decryption keys, d, n (and its component primes, p.sub.1, p.sub.2, . . . p.sub.k) are not held by thecryptosystem 10, they also will be delivered with the encryption request instruction.
In turn, the cryptosystem 10 would decrypt the received cyphertext in the manner described above (developing the sub-tasks, issuing the sub-tasks to the exponentiator 32 of the cryptosystem 10, and reassembling the results of the sub-task todevelop the message data: the DES key), and return to the host system the desired, decrypted information.
Alternatively, the .[.post.]. .Iadd.host.Iaddend.-system 50 may desire to deliver, via the communication medium 60, an encrypted communication to one of the stations 64. If the communication is to be encrypted by the DES scheme, with the DESkey encrypted by the RSA scheme, the host system would encrypt the communication, forward the DES key to one of the cryptosystems 10 for encryption via the RSA scheme. When the encrypted DES key is received back from the cryptosystem 10, the host systemcan then deliver to one or more of the stations 64 the encrypted message.
Of course, the host system 50 and the stations 64 will be using the RSA scheme of public key encryption/decryption. Encrypted communications from the stations 64 to the host system 50 require that the stations 64 have access to the public key.[.E (E, N).]. .Iadd.E=(e, n) .Iaddend.while the host system maintains the private key .[.D (D, N,.]. .Iadd.D=(d, n) .Iaddend.and the constituent primes, p.sub.1, p.sub.2, . . . , p.sub.k). Conversely, for secure communication from the host system 50to one or more of the stations 64, the host system would retain a public key E' for each station 64, while the stations retain the corresponding private keys .[.E'.]. .Iadd.D'.Iaddend..
Other techniques for encrypting the communication could used. For example, the communication could be entirely encrypted by the RSA scheme. If, however, the .Iadd.message to be .Iaddend.communicat.[.ion.]. .Iadd.ed is represented by anumerical value .Iaddend.greater than n-1, it will need to be broken up into blocks size M where .[.0.ltoreq.M.ltoreq.N-1.]. .Iadd.0.ltoreq.M.ltoreq.n-1.Iaddend..
Each block M would be separately encrypted/decrypted, using the public key/private key RSA scheme according to that described above.
* * * * * |
|
|
|
