Public key cryptographic apparatus and method
First Claim
1. A method for establishing cryptographic communications of a message cryptographically processed with RSA (Rivest, Shamir &
-
Adleman) public key encryption, comprising the step steps of;
developing k distinct random prime numbers p1, p2, . . . , pk, wherein k is an integer greater than 2;
providing a number e relatively prime to (p1−
1)·
(p2−
1)·
. . . ·
(pk−
1);
providing a composite number n equaling the product p1·
p2·
. . . ·
pk;
receiving a ciphertext word signal C which is formed by encoding a plaintext message word signal M to a ciphertext word signal C, where M corresponds to a number representative of athe message and
0≦
M≦
n−
1
n being a composite number formed from the product of p1·
p2·
. . . ·
pk where k is an integer greater than 2, p1, p2, . . . pk are distinct prime numbers, and where C is a number representative of an encoded form of the plaintext message word signal M such that
C≡
Me(mod n)
and where e is associated with an intended recipient of the ciphertext word signal C; and
, wherein said encoding step comprises the step of;
transforming said message word signal M to said ciphertext word signal C whereby
C=Me(mod n)
where e is a number relatively prime to (p1−
1)·
(p2−
1). deciphering the received ciphertext word signal C at the intended recipient having available to it the k distinct random prime number p1, p2, . . . pk;
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 the deciphering 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 the deciphering step if the k distinct random prime numbers are 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.
4 Assignments
0 Petitions
Accused Products
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
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).
-
Citations
56 Claims
-
1. A method for establishing cryptographic communications of a message cryptographically processed with RSA (Rivest, Shamir &
-
Adleman) public key encryption, comprising the step steps of;
developing k distinct random prime numbers p1, p2, . . . , pk, wherein k is an integer greater than 2;
providing a number e relatively prime to (p1−
1)·
(p2−
1)·
. . . ·
(pk−
1);
providing a composite number n equaling the product p1·
p2·
. . . ·
pk;
receiving a ciphertext word signal C which is formed by encoding a plaintext message word signal M to a ciphertext word signal C, where M corresponds to a number representative of athe message and
0≦
M≦
n−
1
n being a composite number formed from the product of p1·
p2·
. . . ·
pk where k is an integer greater than 2, p1, p2, . . . pk are distinct prime numbers, and where C is a number representative of an encoded form of the plaintext message word signal M such that
C≡
Me(mod n)
and where e is associated with an intended recipient of the ciphertext word signal C; and
, wherein said encoding step comprises the step of;
transforming said message word signal M to said ciphertext word signal C whereby
C=Me(mod n)
where e is a number relatively prime to (p1−
1)·
(p2−
1).deciphering the received ciphertext word signal C at the intended recipient having available to it the k distinct random prime number p1, p2, . . . pk;
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 the deciphering 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 the deciphering step if the k distinct random prime numbers are 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. - View Dependent Claims (2)
-
Adleman) public key encryption, comprising the step steps of;
-
3. A method for transferring a message signal Mi in a communications of a message signal Mi cryptographically processed with RSA public key encryption in a system having j terminals, wherein each terminal is being characterized by an encoding key Ei=(ei, ni) and a decoding key Di=(di, ni), where i=1, 2, . . . , j, and wherein the message signal Mi corresponds to a number representative of a message-to-be-transmitted received from the ith terminal, the method comprising the steps of:
-
establishing ni where ni is a composite number of the form
ni=Pi,1·
pi,2·
, . . . , ·
pi,kni=pi,1·
pi,2·
. . . ·
pi,kwhere k is an integer greater than 2, pi,1, pi,2, . . . , pi,k are distinct random prime numbers, ei is relatively prime to lcm(pi,1−
1, pi,2−
1, pi,kd−
1) lcm(pi,1−
1, pi,2−
1, . . . , pi,k−
1), anddi is selected from the group consisting of the a class of numbers equivalent to a multiplicative inverse of
ei(mod(lcm((pi,1−
1), (pi,2−
1), . . . , (pi,k−
1)))),;
comprising the steps of; receiving by a recipient terminal (i=y) from a sender terminal (i=x, x≠
y) a ciphertext signal Cx formed by encoding a digital message word signal MA for transmission from a first terminal (i=A) to a second terminal (i=B), said encoding step including the sub-step of;
Mx, wherein the encoding includestransforming said message word signal MA to one or more message block word signals MA″
MX″
, each block word signal MA″
MX″
corresponding to a number representative of a portion of said message word signal MA MX in the range 0≦
MA″
≦
nB−
1 0≦
MX″
≦
ny−
1, andtransforming each of said message block word signals MA″
MX″
to a ciphertext word signal CA, CA corresponding CX that corresponds to a number representative of an encoded form of said message block word signal MA″
, MX″
whereby ;
CA≡
MA″
eB(mod nB.)Cx≡
Mx″
ey(mod ny); and
deciphering the received ciphertext word signal Cx at the recipient terminal having available to it the k distinct random prime numbers py,1, py,2, . . . , py,k for establishing its dy;
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 the deciphering 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 the deciphering step if the k distinct random prime numbers are 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.
-
-
4. A cryptographic communications system for communications of a message cryptographically processed with an RSA public key encryption, comprising:
-
a communication medium channel for transmitting a ciphertext word signal C;
an encoding means coupled to said channel and adapted for transforming a transmit message word signal M to athe ciphertext word signal C using a composite number, n, where n is a product of the form
n=p1·
p2·
. . . ·
pk,where k is an integer greater than 2, and p1, p2, . . . pk are distinct random prime numbers, and for transmitting C on said channel, where the transmit message word signal M corresponds to a number representative of a the message and 0≦
M≦
n−
1, where n is a composite number of the form
n=p1·
p2·
. . . ·
pkwhere k is an integer greater than 2 and p1, p2, . . . , pk are distinct prime numbers, and where the ciphertext word signal C corresponds to a number representative of an enciphered encoded form of said message and corresponds to through a relationship of the form
C≡
Me(mod n), andwhere e is a number relatively prime to lcm(p1−
1, p2−
1, . . . , pk−
1); anda decoding means coupled to said channel and adapted for receiving the ciphertext word signal C from said channel and, having available to it the k distinct random prime numbers p1, p2, . . . pk, for transforming the ciphertext word signal C to a receive message word signal M′
where M′
corresponds to a number representative of a deciphereddecoded form of the ciphertext word signal C and corresponds tothrough a relationship of the form
M′
≡
Cd(mod n)where d is selected from the group consisting of the a class of numbers equivalent to a multiplicative inverse of
e(mod(lcm((p1−
1), (p2−
1), . . . , (pk−
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 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 ciphertext word 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 to perform 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 is used instead.
-
-
5. A cryptographic communications system for communications of a message cryptographically processed with an RSA public key encryption, the system having a plurality of terminals coupled by a communications channel, including comprising:
-
a first terminal of the plurality of terminals characterized by an associated encoding key EA=(eA, nA) and a decoding key DA=(dA, nA), wherein nA is a composite number of the form
nA=pA,1·
pA,2·
. . . ·
PA,kwhere k is an integer greater than 2, pA,1, pA,2, . . . , pA,k are distinct random prime numbers, eA is relatively prime to
lcm(pA,1−
1, pA,2−
1, . . . , pA,k−
1), anddA is selected from the group consisting of the a class of numbers equivalent to a multiplicative inverse of
eA(mod(lcm((pA,1−
1), (pA,2−
1), . . . , (pA,k−
1)))),; and
and including a second terminal, comprising;
of the plurality of terminals havingblocking means for transforming a first message-to-be-transmitted , which is to be transmitted on said communications channel from said second terminal to said first terminal, into one or more transmit message word signals MB, where each MB corresponds to a number representative of said first message in the range
0≦
MB≦
nA−
1, andencoding means coupled to said channel and adapted for transforming each transmit message word signal MB to a ciphertext word signal CB that and for transmitting CB on said channel, where CB corresponds to a number representative of an enciphered encoded form of said first message and corresponds to through a relationship of the form
CB=MBeA(mod nA)CB≡
MBeA (mod nA),wherein said first terminal comprises;
havingdecoding means coupled to said channel and adapted for receiving each of said ciphertext word signals CB from said channel and, having available to it the k distinct random prime numbers pA,1, pA,2, . . . , pA,k, for transforming each of said ciphertext word signals CB to a receive message word signal MB MB′
, andmeans for transforming said receive message word signals M′
MB′
to said first message, where M′
is MB′
corresponds to a number representative of a deciphered decoded form of CB and corresponds to through a relationship of the form
MB′
=CBdA (mod nA)MB′
≡
CBdA (mod nA);
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 transforming said receive message word signal MB′
to said first message 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 the transforming of said receive message word signal MB′
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 MB′
if the pair of prime numbers p and q is used instead.- View Dependent Claims (6)
wherein said first terminal comprises;
further havingblocking means for transforming a second message-to-be-transmitted , which is to be transmitted on said communications channel from said first terminal to said second terminal, to one or more transmit message word signals MA, where each MA corresponds to a number representative of said message in the range
0≦
MAeB(mod nB),0≦
MA≦
nB−
1, andencoding means coupled to said channel and adapted for transforming each transmit message word signal MA to a ciphertext word signal CA and for transmitting CA on said channel, where CA corresponds to a number representative of an enciphered encoded form of said second message and corresponds to through a relationship of the form
CA=MAeB(mod nB)CA≡
MAeB (mod nB); and
wherein said second terminal comprises;
further havingdecoding means coupled to said channel and adapted for receiving each of said ciphertext word signals CA from said channel and, having available to it the k distinct random prime numbers pB1, pB,2, . . . , pB,k, for transforming each of said ciphertext word signals to a receive message word signal MA′
, andmeans for transforming said receive message word signals MA MA′
to said second message, where M′
MA′
corresponds to a number representative of a deciphered decoded form of and corresponds to CA through a relationship of the form
MA′
≡
CAdB(mod nB)MA′
≡
CAdB (mod nB).
-
-
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≦
M≦
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 comprises the step of;
transforming said message word signal M to said ciphertext word signal C whereby
C≡
aeMe+ae−
1Me−
1+. . . +ao(mod n)where e and ae, ae−
1, . . . , ao are numbers. - View Dependent Claims (8)
-
-
9. A communication system for transferring communications of message signals Mi cryptographically processed with RSA public key signing, comprising:
-
j stations, terminals including first and second terminals, each of the j stations terminals being characterized by an encoding key Ei=(ei, ni) and decoding key Di=(di, ni), where i=1,2, . . . ,j, and wherein Mi corresponds to a number representative of a message signal to be transmitted from the ith terminal, each of the j terminals being adapted to transmit a particular one of the message signals where an ith message signals Mi is transmitted from an ith terminal and
0≦
Mi≦
ni−
1,ni is being a composite number of the form
ni=pii,1·
pi,2·
. . . pi,k ni=pi,1·
pi,2·
. . . ·
pi,kwhere k is an integer greater than 2, pi,1, pi,2, . . . , pi,k are distinct random prime numbers, ei is relatively prime to lcm(pi,1−
1,pi,2−
1, . . . , pi,k−
1), anddi is selected from the group consisting of the a class of numbers equivalent to a multiplicative inverse of
ei(mod(lcm((pi,1−
1), (pi,2−
1), . . . , (pi,k−
1))));
asaid first one of the j terminalsterminal including means for encoding a digital message word signal MA for transmission M1 to be transmitted from said first terminal (i=A 1) to a said second one of the j terminals terminal (i=B 2), and said encoding means for transforming said digital message word signal MAS, MAS corresponding to a number representative of an encoded form of said message word signal MA, whereby;
M1S using a relationship of the form
MAS≡
MAdA(mod nA)M1S≡
M1d1 (mod n1); and
means for transmitting said signed message word signal M1S from said first terminal to said second terminal, wherein said second terminal includes means for decoding said signed message word signal M1S to said digital message word signal M1;
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 the composite number n;
wherein encoding a digital message word signal M1 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 fewer computational cycles to perform the encoding of the digital message word signal Mi 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 M1 if the pair of prime numbers p and q is used instead. - View Dependent Claims (10, 14)
-
-
11. A communication system for transferring a message signal Mi cryptographically processed with RSA public key encryption, the communications system comprising:
-
j communication stations including first and second stations, each of the j communication stations being characterized by an encoding key Ei=(ei, ni) and a decoding key Di=(di, ni), where i=1, 2, . . . , j, and wherein Mi corresponds to a number representative of a message signal to be transmitted from the ith terminal, each of the j communication stations being adapted to transmit a particular one of the message signals where an ith message signal Mi is received from an ith communication station, and
0≦
Mi≦
ni−
1ni is being a composite number of the form
ni=pi,1·
pi,2·
. . . ·
pi,kwhere k is an integer greater than 2, pi,1, pi,2, . . . , pi,k are distinct random prime numbers, ei is relatively prime to lcm(pi,1−
1,pi,2−
1, . . . ,pi,k−
1), anddi is selected from the group consisting of the a class of numbers equivalent to a multiplicative inverse of
ei(mod(lcm((pi,1−
1), (pi,2−
1), . . . , (pi,k−
1)))),asaid first one of the j communication stationsstation including means for encoding a digital message word signal MA for transmission M1 to be transmitted from said first one of the j communication stations station (l=A 1) to a said second one of the j communication stations station (l=B 2), means for transforming said digital message word signal MA M1 to one or more message block word signals MA″
M1″
, each block word signal MA′
M1″
being a number representative of a portion of said digital message word signal MA′
M1 in the range 0≦
MA≦
nB−
1, 0≦
M1″
≦
n2−
1, andmeans for transforming each of said message block word signals MA″
M1″
to a ciphertext word signal CA, CA corresponding to a number representative of an encoded form of said message block word signal MA″
, whereby;
C1 using a relationship of the form
CA=MA″
Eb(mod nB)C1≡
M1″
e2 (mod n2); and
means for transmitting said ciphertext signals C1 from said first station to said second station, wherein said second station includes means for deciphering said ciphertext signals C1 using p2,1, p2,2, . . . p2,k to produce said digital message word signal M1;
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 deciphering said ciphertext signals C1 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 the deciphering of said ciphertext signals C1 if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a deciphering of said ciphertext signals C1 if the pair of prime numbers p and q is used instead. - View Dependent Claims (12)
-
-
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 a ciphertext word signal C where M corresponds to a number representative of a message and
0≦- M≦
n−
1where 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 enciphered form of said message and corresponds to
C≡
aeMe+ae−
1Me−
1+. . . +ao(mod n)where e and ae, ae−
1, . . . , ao are numbers; and
means for transmitting the ciphertext word signal C to the second communicating station.
- M≦
-
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 k distinct random prime numbers, p1, p2, . . . pk, where k≧
3, and checking that each of the k distinct random prime numbers minus 1, p1−
1, p2−
1, . . . , pk−
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≡
Me(mod n)
where M represents the message, where 0≦
M≦
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, p1, p2, . . . pk; and
deciphering at the recipient the received ciphertext message data C to produce the message, the recipient having access to the k distinct random prime numbers, p1, p2, . . . pk;
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 the deciphering 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 the deciphering step if the k distinct random prime numbers are 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. - View Dependent Claims (16, 17, 18)
-
-
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 p1, p2, . . . pk, where k≧
3, and checking that each of the k distinct random prime numbers minus 1, p1−
1, p2−
1, . . . pk−
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 form of d≡
e−
1(mod((p1−
1)·
(p2−
1) . . . (pk−
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 a plaintext message data M; and
decoding the received ciphertext message data C to the plaintext message data M using a relationship of the form
M≡
Cd(mod n),
the decoding performed by a recipient owning the private key portion d and having access to the k distinct random prime numbers p1, p2, . . . pk;
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 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 composite numbers 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 used instead. - View Dependent Claims (20, 21, 22)
-
-
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 p1, p2, . . . pk, where k≧
3, and checking that each of the k distinct random prime numbers minus 1, p1−
1, p2−
1, . . . pk−
1, is relatively prime to the public key portion e;
establishing a private key portion d of a relationship to the public key portion e of the form d≡
e−
1(mod((p1−
1)·
(p2−
1) . . . (pk−
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 a signed message MS using a relationship of the form
MS≡
Md(mod n),
where 0≦
M≦
n−
1;
receiving the signed message MS; and
deciphering the signed message to produce the plaintext message data M;
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 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 the encoding 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. - View Dependent Claims (24, 25, 26)
-
-
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 the message 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, a number n that is a composite number equaling the product of at least three distinct random prime numbers, wherein 0≦
M≦
n−
1, andan exponent e that is a number relatively prime to a lowest common multiplier of the at least three distinct random 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 recipient based 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 a composite 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 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 for composite 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 prime numbers p and q is used instead. - View Dependent Claims (28, 29, 30)
-
-
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 decipherable by 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 encoded form 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≦
M≦
n−
1, andan exponent e that is a number relatively prime to a lowest 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 at least 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 same number 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 for composite 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 prime numbers p and q is used instead. - View Dependent Claims (32, 33, 34)
-
-
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, p1, p2, . . . pk, where k≧
3, and checking that each of the k distinct random prime numbers minus 1, p1−
1, p2−
1, . . . , pk−
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 form of d≡
e−
1(mod((p1−
1)·
(p2−
1) . . . (pk−
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
encoding plaintext data M to ciphertext data C for the local storage, using a relationship of the form
C≡
Me(mod n),wherein 0≦
M≦
n−
1, whereby the ciphertext data C is decipherable only by the private key owner having available to it the factors 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 composite number 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 the encoding 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. - View Dependent Claims (36)
-
-
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 receiving messages cryptographically processed with an RSA public key encryption, the host system including at least one cryptosystem configured for developing k distinct random prime numbers p1, p2, . . . , pk, where k≧
3,checking that each of the k distinct random prime numbers minus 1, p1−
1, p2−
1, . . . pk−
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 prime numbers, establishing a private key portion d by a relationship of the public key portion e in the form of d≡
e−
1(mod((p1−
1)·
(p2−
1) . . . (pk−
1))),in response to an encoding request from the host system, encoding a plaintext message 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≡
Me(mod n),
where 0≦
M≦
n−
1, andin response to a decoding request from the host system, decoding a ciphertext message data C′
communicated via the host producing therefrom a plaintext message data M′
using a relationship of the form
M′
≡
C′
d(mod n);
wherein p and q are a pair of prime numbers that product of which equals a composite 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, 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 decoding of the 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 the ciphertext message data C′
if the pair of prime numbers p and q is used instead. - View Dependent Claims (38, 39, 40, 41, 42, 43)
-
-
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, the cryptosystem being configured for providing a public key portion e, developing k distinct random prime numbers p1, p2, . . . , pk, where k≧
3,checking that each of the k distinct random prime numbers minus 1, p1−
1, p2−
1, . . . pk1, 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 of d≡
e−
1(mod((p1−
1)·
(p2−
1) . . . (pk−
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 form
C≡
Me(mod n),
wherein 0≦
M≦
n−
1, andin 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 form
M′
≡
C′
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, and the 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 composite numbers 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 is used instead.
-
-
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 cryptosystem including 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 a public 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 p1, p2, . . . pk, where k≧
3,constructing subtasks, one subtask for each of the k factors, to be executed by the exponentiator elements for producing respective ones of the subtask values C1, C2, . . . Ck, and forming a ciphertext message C from the subtask values C1, C2, . . . Ck, 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 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 message C 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. - View Dependent Claims (46)
-
-
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 cryptosystem including 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/C to 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 p1, p2, . . . pk, where k≧
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 subtask values M1, M2, . . . Mk/C1, C2, . . . Ck, and forming the ciphertext/plaintext message C/M from the subtask values C1, C2, . . . Ck/M1, M2, . . . Mk;
wherein p and q are a pair of prime numbers 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 numbers p and q is used instead. - View Dependent Claims (48, 49, 50)
-
-
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 p1, p2, . . . pk, where k≧
3, and for checking that each of the k distinct random prime numbers minus 1, p1−
1, p2−
1, . . . pk−
1, is relatively prime to the public key portion e;
means for establishing a private key portion of d by a relationship to the public key portion e in the form of d≡
e−
1(mod((p1−
1)·
(p2−
1) . . . (pk−
1)));
means for computing a composite number, n, as a product of the k distinct random prime numbers;
means for receiving a ciphertext message data C; and
means for decoding the ciphertext message data C to a plaintext message data M using a relationship of the form
M≡
Cd(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 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 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. - View Dependent Claims (52, 55)
-
-
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 p1, p2, . . . pk, where k≧
3, and for checking that each of the k distinct random prime numbers minus 1, p1−
1, p2−
1, . . . pk−
1, is relatively prime to the public key portion e;
means for establishing a private key portion d by a relationship to the public key portion e of the form d≡
e−
1(mod((p1−
1)·
(p2−
1) . . . (pk−
1)));
means for computing a composite number, n, as a product of the k distinct random prime numbers; and
means for encoding a plaintext message data M with the private key portion d to produce a signed message MS, using a relationship of the form
MS≡
Md(mod n), - View Dependent Claims (54, 56)
-
Specification