Multiprime RSA public key cryptosystem
View Patent ↗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.
1. A processor-implemented method for establishing cryptographic communications, comprising the steps of:
encoding a plaintext message word M to a ciphertext word C, wherein M corresponds to a number representative of a message and wherein
0 ≦M≦n− 1,
wherein n is a composite number formed by the product of p 1 ·p 2 · . . . ·p k , k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, C is a number representative of an encoded form of message word M, and wherein said encoding step comprises transforming said message word M to said ciphertext word C, whereby
C≡M e (mod n),
and wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
decoding said ciphertext word C to a receive message word M′, said decoding step being performed using a decryption exponent d that is defined by
d≡e −1 mod ((p 1 −1) (p 2 −1) . . . (p k −1)),
said decoding step including the further steps of,
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 d 1 (mod p 1 ),
M 2 ′≡C 2 d 2 (mod p 2 ),
. . .
M k ′≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
solving said sub-tasks to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
2. A processor-implemented method as recited in claim 1 wherein said step of combining said results of said sub-tasks includes a step of performing a recursive combining process to produce said receive message word M′.
3. A processor-implemented method as recited in claim 2 wherein said recursive combining process is performed in accordance with
Y i ≡Y i-1 +[( M i ′−Y i-1 ) ( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
M
′
=
Y
k
,
Y
1
=
M
1
′
,
and
w
i
=
∏
j
<
i
p
j
.
4. A processor-implemented method as recited in claim 1 wherein said step of combining said results of said sub-tasks includes a step of performing a summation process to produce said receive message word M′.
5. A processor-implemented method as recited in claim 4 wherein said summation process is performed in accordance with
M
′
≡
∑
i
=
1
k
M
i
′
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
6. A processor-implemented method as recited in claim 1 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
7. A processor-implemented method as recited in claim 1 wherein each of said distinct random prime numbers has the same number of bits.
8. A processor-implemented method as recited in claim 1 wherein the plurality of k sub-tasks are performed in parallel.
9. A processor-implemented method as recited in claim 8 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
10. A cryptographic communications system for establishing communications, comprising:
a communication medium;
encoding means coupled to said communication medium and adapted for transforming a transmit message word M to a ciphertext word C and for transmitting said ciphertext word C on said medium, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
wherein n is a composite number of the form,
n=p 1 ·p 2 · . . . ·p k
wherein k is an integer greater than 2 and p 1 , p 2 , . . . , and p k are distinct random prime numbers, and wherein said ciphertext word C corresponds to a number representative of an enciphered form of said message word M and corresponds to
C≡M e (mod n),
wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
decoding means communicatively coupled with said communication medium for receiving said ciphertext word C via said medium, said decoding means being operative to perform a decryption process for transforming said ciphertext word C to a receive message word M′, wherein M′ corresponds to a number representative of a deciphered form of C, said decryption process using a decryption exponent d that is defined by
d≡e −1 mod((p 1 −1)(p 2 −1) . . . (p k −1)),
said decryption process including the steps of
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 d 1 (mod p 1 ),
M 2 ′≡C 2 d 2 (mod p 2 ),
. . .
M k ′≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
solving said sub-tasks to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
11. A cryptographic communications system as recited in claim 10 , wherein said decoding means is operative to combine said results of said sub-tasks by performing a recursive combining process to produce said receive message word M′.
12. A cryptographic communications system as recited in claim 11 wherein said decoding means is operative to perform said recursive combining process in accordance with
Y i ≡Y i-1 +[( M i ′−Y i-1 )( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
M
′
=
Y
k
,
Y
1
=
M
1
′
,
and
w
i
=
∏
j
<
i
p
j
.
13. A cryptographic communications system as recited in claim 10 wherein said decoding means is operative combine said results of said sub-tasks by performing a summation process to produce said receive message word M′.
14. A cryptographic communications system as recited in claim 13 wherein said decoding means is operative to perform said summation process accordance with
M
′
≡
∑
i
=
1
k
M
i
′
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
15. A cryptographic communications system as recited in claim 10 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
16. A cryptographic communications system as recited in claim 10 wherein each of said distinct random prime numbers has the same number of bits.
17. A cryptographic communications system as recited in claim 10 wherein the plurality of k sub-tasks are performed in parallel.
18. A cryptographic communications system as recited in claim 17 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
19. A processor-implemented method for establishing cryptographic communications, comprising the steps of:
encoding a plaintext message word M to a ciphertext word C, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
n being a composite number formed from the product of p 1 ·p 2 · . . . ·p k , wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein the ciphertext word C is a number representative of an encoded form of message word M, wherein said step of encoding includes the steps of
defining a plurality of k sub-tasks in accordance with
C 1 ≡M 1 e 1 (mod p 1 ),
C 2 ≡M 2 e 2 (mod p 2 ),
. . .
C k ≡M k e k (mod p k ),
wherein
M 1 ≡M(mod p 1 ),
M 2 ≡M(mod p 2 ),
. . .
M k ≡M(mod p k ),
e 1 ≡e(mod(p 1 −1)),
e 2 ≡e(mod(p 2 −1)), and
. . .
e k ≡e(mod(p k −1)),
wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1), solving said sub-tasks to determine results C 1 , C 2 , . . . C k , and
combining said results of said sub-tasks to produce said ciphertext word C.
20. A processor-implemented method as recited in claim 19 , wherein said step of combining said results of said subtasks includes a step of performing a recursive combining process to produce said ciphertext word C.
21. A processor-implemented method as recited in claim 20 wherein said recursive combining process is performed in accordance with
Y i ≡Y i-1 +[( C i −Y i-1 ) ( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
C
=
Y
k
,
Y
1
=
C
i
,
and
w
i
=
∏
j
<
i
p
j
.
22. A processor-implemented method as recited in claim 19 wherein said step of combining said results of said sub-tasks includes a step of performing a summation process to produce said ciphertext word C.
23. A processor-implemented method as recited in claim 22 wherein said summation process is performed in accordance with
C
≡
∑
i
=
1
k
C
i
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
24. A processor-implemented method as recited in claim 19 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
25. A processor-implemented method as recited in claim 19 wherein each of said distinct random prime numbers has the same number of bits.
26. A processor-implemented method as recited in claim 19 wherein the plurality of k sub-tasks are performed in parallel.
27. A processor-implemented method as recited in claim 26 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
28. A cryptographic communications system for establishing communications, comprising:
a communication medium;
a processor coupled to said communication medium and operative to transform a transmit message word M to a ciphertext word C, and to transmit said ciphertext word C on said medium, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
n being a composite number formed from the product of p 1 ·p 2 · . . . ·p k wherein k is an integer greater than 2 and p 1 , p 2 , . . . , p k , are distinct random prime numbers, and wherein the ciphertext word C is a number representative of an encoded form of message word M, said processor being operative to transform said transmit message word M to said ciphertext word C by performing an encoding process comprising the steps of:
defining a plurality of k sub-tasks in accordance with
C 1 ≡M 1 e 1 (mod p 1 ),
C 2 ≡M 2 e 2 (mod p 2 ),
. . .
C k ≡M k e k (mod p k ),
wherein
M 1 ≡M(mod p 1 ),
M 2 ≡M(mod p 2 ),
. . .
M k ≡M(mod p k ),
e 1 ≡e(mod(p 1 −1)),
e 2 ≡e(mod(p 2 −1)), and
. . .
e k ≡e(mod(p k −1)),
wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1), solving said sub-tasks to determine results C 1 , C 2 , . . . C k , and
combining said results of said sub-tasks to produce said ciphertext word C.
29. A cryptographic communications system as recited in claim 28 , wherein said processor is operative to combine said results of said sub-tasks by performing a recursive combining process to produce said ciphertext word C.
30. A cryptographic communications system as recited in claim 29 wherein said processor is operative to perform said recursive combining process in accordance with
Y i ≡Y i-1 +[( C i −Y i-1 )( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
C
=
Y
k
,
Y
1
=
C
1
,
and
w
i
=
∏
j
<
i
p
j
.
31. A cryptographic communications system as recited in claim 28 wherein said processor is operative to combine said results of said sub-tasks by performing a summation process to produce said message word C.
32. A cryptographic communications system as recited in claim 31 wherein said processor is operative to perform said summation process in accordance with
C
≡
∑
i
=
1
k
C
i
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
33. A cryptographic communications system as recited in claim 28 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
34. A cryptographic communications system as recited in claim 28 wherein each of said distinct random prime numbers has the same number of bits.
35. A cryptographic communications system as recited in claim 28 wherein the plurality of k sub-tasks are performed in parallel.
36. A cryptographic communications system as recited in claim 35 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
37. A digital signature system, comprising:
a communication medium;
digital signature generating means coupled to said communication medium and adapted for transforming a message word M to a signed ciphertext word C and for transmitting said signed ciphertext word C on said medium, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
wherein n is a composite number of the form
n=p 1 ·p 2 · . . . p k ,
wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein said signed ciphertext word C corresponds to a number representative of a signed form of said message word M and corresponds to
C≡M d (mod n),
wherein d is defined by
d≡e −1 mod((p 1 −1)·(p 2 −1)· . . . ·(p k −1)), and
e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
digital signature verification means communicatively coupled with said communication medium for receiving said signed ciphertext word C via said medium, and being operative to verify said signed ciphertext word C by performing the steps of,
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 d 1 (mod p 1 ),
M 2 ′≡C 2 d 2 (mod p 2 ),
. . .
M k ′≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
e 1 ≡e(mod(p 1 −1)),
e 2 ≡e(mod(p 2 −1)), and
. . .
e k ≡e(mod(p k −1)),
solving said sub-tasks to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
38. A digital signature system as recited in claim 37 wherein said digital signature verification means is operative to combine said results of said sub-tasks by performing a recursive combining process to produce said receive message word M′.
39. A digital signature system as recited in claim 38 wherein said digital signature verification means is operative to perform said recursive combining process in accordance with
Y i ≡Y i-1 +[( M i ′−Y i-1 ) ( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
M
′
=
Y
k
,
Y
1
=
M
1
′
,
and
w
i
=
∏
j
<
i
p
j
.
40. A digital signature system as recited in claim 37 wherein said digital signature verification means is operative combine said results of said sub-tasks by performing a summation process to produce said receive message word M′.
41. A digital signature system as recited in claim 40 wherein said digital signature verification means is operative to perform said summation process accordance with
M
′
≡
∑
i
=
1
k
M
i
′
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
42. A digital signature system as recited in claim 37 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
43. A digital signature system as recited in claim 37 wherein each of said distinct random prime numbers has the same number of bits.
44. A digital signature system as recited in claim 37 wherein the plurality of k sub-tasks are performed in parallel.
45. A digital signature system as recited in claim 44 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
46. A processor-implemented method for establishing cryptographic communications, comprising the steps of:
decoding a ciphertext word C to a message word M, wherein M corresponds to a number representative of a message and wherein
0 ≦M≦n− 1,
wherein n is a composite number formed by the product of p 1 ·p 2 · . . . ·p k , k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, C is a number representative of an encoded form of message word M that is encoded by transforming said message word M to said ciphertext word C whereby
C≡M e (mod n),
and wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1);
said decoding step being performed using a decryption exponent d that is defined by
d≡e −1 mod((p 1 −1)(p 2 −1) . . . (p k −1)),
wherein said step of decoding includes the steps of
defining a plurality of k sub-tasks in accordance with
M 1 ≡C 1 d 1 (mod p 1 ),
M 2 ≡C 2 d 2 (mod p 2 ),
. . .
M k ≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
solving said sub-tasks to determine results M 1 , M 2 , . . . M k , and
combining said results of said sub-tasks to produce said message word M.
47. A processor-implemented method as recited in claim 46 wherein said step of combining said results of said sub-tasks includes a step of performing a recursive combining process to produce said message word M.
48. A processor-implemented method as recited in claim 47 wherein said recursive combining process is performed in accordance with
Y i ≡Y i-1 +[( M i −Y i-1 ) ( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
M
′
=
Y
k
,
Y
1
=
M
1
′
,
and
w
i
=
∏
j
<
i
p
j
.
49. A processor-implemented method as recited in claim 46 wherein said step of combining said results of said sub-tasks includes a step of performing a summation process to produce said message word M.
50. A processor-implemented method as recited in claim 49 wherein said summation process is performed in accordance with
M
≡
∑
i
=
1
k
M
i
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
51. A cryptographic communications system as recited in claim 50 wherein said processor is operative to perform said recursive combining process in accordance with
Y i ≡Y i-1 +[( M i ′−Y i-1 ) ( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
M
=
Y
k
,
Y
1
=
M
1
′
,
and
w
i
=
∏
j
<
i
p
j
.
52. A processor-implemented method as recited in claim 46 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
53. A processor-implemented method as recited in claim 46 wherein each of said distinct random prime numbers has the same number of bits.
54. A processor-implemented method as recited in claim 46 wherein the plurality of k sub-tasks are performed in parallel.
55. A processor-implemented method as recited in claim 54 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
56. A cryptographic communications system for establishing communications, comprising:
a communication medium;
a processor communicatively coupled with said communication medium for receiving a ciphertext word C via said medium, and being operative to transform said ciphertext word C to a receive message word M′, wherein a message M corresponds to a number representative of a message and wherein
0 ≦M≦n− 1,
wherein n is a composite number formed by the product of p 1 ·p 2 · . . . ·p k , k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein said ciphertext word C is a number representative of an encoded form of said message word M that is encoded by transforming M to said ciphertext word C whereby,
C≡M e (mod n),
and wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
said processor being operative to perform a decryption process using a decryption exponent d that is defined by
d≡e −1 mod((p 1 −1) (p 2 −1) . . . (p k −1)),
said decryption process including the steps of
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 d 1 (mod p 1 ),
M 2 ′≡C 2 d 2 (mod p 2 ),
. . .
M k ′≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
solving said sub-tasks to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
57. A cryptographic communications system as recited in claim 56 wherein said processor is operative to combine said results of said sub-tasks by performing a recursive combining process to produce said receive message word M′.
58. A cryptographic communications system as recited in claim 56 wherein said processor is operative to combine said results of said sub-tasks by performing a summation process to produce said receive message word M′.
59. A cryptographic communications system as recited in claim 58 wherein said processor is operative to perform said summation process in accordance with
M
′
≡
∑
i
=
1
k
M
i
′
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
60. A cryptographic communications system as recited in claim 56 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
61. A cryptographic communications system as recited in claim 56 wherein each of said distinct random prime numbers has the same number of bits.
62. A cryptographic communications system as recited in claim 56 wherein the plurality of k sub-tasks are performed in parallel.
63. A cryptographic communications system as recited in claim 62 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
64. A processor-implemented method for generating a digital signature, comprising the steps of:
signing a plaintext message word M to create a signed ciphertext word C, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
n being a composite number formed from the product of p 1 ·p 2 · . . . ·p k , wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein the signed ciphertext word C is a number representative of a signed form of message word M, wherein
C≡M d (mod n), and
wherein said step of signing includes the steps of
defining a plurality of k sub-tasks in accordance with
C 1 ≡M 1 d 1 (mod p 1 ),
C 2 ≡M 2 d 2 (mod p 2 ),
. . .
C k ≡M k d k (mod p k ),
wherein
M 1 ≡M(mod p 1 ),
M 2 ≡M(mod p 2 ),
. . .
M k ≡M(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
where d id defined by
d≡e −1 mod((p 1 −1)·(p 2 −1)· . . . ·(p k −1)), and
e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1), solving said sub-tasks to determine results C 1 , C 2 , . . . C k , and
combining said results of said sub-tasks to produce said ciphertext word C.
65. A processor-implemented method as recited in claim 64 wherein said step of combining said results of said sub-tasks includes a step of performing a recursive combining process to produce said ciphertext word C.
66. A processor-implemented method as recited in claim 65 wherein said recursive combining process is performed in accordance with
Y i ≡Y i-1 +[( C i −Y i-1 ) ( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
C
=
Y
k
,
Y
1
=
C
1
,
and
w
i
=
∏
j
<
i
p
j
.
67. A processor-implemented method as recited in claim 64 wherein said step of combining said results of said sub-tasks includes a step of performing a summation process to produce said signed ciphertext word C.
68. A processor-implemented method as recited in claim 67 wherein said summation process is performed in accordance with
C
≡
∑
i
=
1
k
C
i
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
69. A processor-implemented method as recited in claim 64 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
70. A processor-implemented method as recited in claim 64 wherein each of said distinct random prime numbers has the same number of bits.
71. A processor-implemented method as recited in claim 64 wherein the plurality of k sub-tasks are performed in parallel.
72. A processor-implemented method as recited in claim 71 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
73. A digital signature generation system, comprising:
a communication medium;
a processor coupled to said communication medium and operative to transform a transmit message word M to a signed ciphertext word C, and to transmit said signed ciphertext word C on said medium, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
n being a composite number formed from the product of p 1 ·p 2 · . . . ·p k , k wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein the signed ciphertext word C is a number representative of a signed form of said message word M, wherein
C≡M d (mod n),
said processor being operative to transform said transmit message word M to said signal ciphertext word C by performing a digital signature generating process comprising the steps of,
defining a plurality of k sub-tasks in accordance with
C 1 ≡M 1 d 1 (mod p 1 ),
C 2 ≡M 2 d 2 (mod p 2 ),
. . .
C k ≡M k d k (mod p k ),
wherein
M 1 ≡M(mod p 1 ),
M 2 ≡M(mod p 2 ),
. . .
M k ≡M(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
where d id defined by
d≡e −1 mod(p 1 −1)·(p 2 −1)· . . . ·(p k −1)), and
e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1), solving said sub-tasks to determine results C 1 , C 2 , . . . C k , and
combining said results of said sub-tasks to produce said ciphertext word C.
74. A digital signature generation system as recited in claim 73 wherein said processor is operative to combine said results of said sub-tasks by performing a recursive combining process to produce said signed ciphertext word C.
75. A digital signature generation system as recited in claim 74 wherein said processor is operative to perform said recursive combining process in accordance with
Y i ≡Y i-1 +[( M i ′−Y i-1 ) ( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
C
=
Y
k
,
Y
1
=
C
1
,
and
w
i
=
∏
j
<
i
p
j
.
76. A digital signature generation system as recited in claim 73 wherein said processor is operative to combine said results of said sub-tasks by performing a summation process to produce said signed message word C.
77. A digital signature system as recited in claim 76 wherein said processor is operative to perform said summation process in accordance with
C
≡
∑
i
=
1
k
C
i
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
78. A digital signature generation system as recited in claim 73 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
79. A digital signature generation system as recited in claim 73 wherein each of said distinct random prime numbers has the same number of bits.
80. A digital signature generation system as recited in claim 73 wherein the plurality of k sub-tasks are performed in parallel.
81. A digital signature generation system as recited in claim 80 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
82. A processor-implemented digital signature process, comprising the steps of:
signing a plaintext message word M to create a signed ciphertext word C, wherein M corresponds to a number representative of a message and wherein
0 ≦M≦n− 1,
wherein n is a composite number formed by the product of p 1 ·p 2 · . . . ·p k , k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, C is a number representative of a signed form of message word M, and wherein said encoding step comprises transforming said message word M to said ciphertext word C, whereby
C≡M d (mod n),
wherein d is defined by
d≡e −1 mod(p 1 −1)·(p 2 −1)· . . . ·(p k −1)), and
e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
verifying said ciphertext word C to a receive message word M′ by performing the steps of,
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 d 1 (mod p 1 ),
M 2 ′≡C 2 d 2 (mod p 2 ),
. . .
M k ′≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
e 1 ≡e(mod(p 1 −1)),
e 2 ≡e(mod(p 2 −1)), and
. . .
e k ≡e(mod(p k −1)),
solving said sub-tasks to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
83. A processor-implemented digital signature process as recited in claim 82 wherein said step of combining said results of said sub-tasks includes a step of performing a recursive combining process to produce said receive message word M′.
84. A processor-implemented digital signature process as recited in claim 83 wherein said recursive combining process is performed in accordance with
Y i ≡Y i-1 +[( M i ′−Y i-1 ) ( w i −1 mod p i ) mod p i ]·w i mod n,
wherein 2≦i≦k, and
M
′
=
Y
k
,
Y
1
=
M
1
′
,
and
w
i
=
∏
j
<
i
p
j
.
85. A processor-implemented digital signature process as recited in claim 83 wherein said step of combining said results of said sub-tasks includes a step of performing a summation process to produce said receive message word M′.
86. A processor-implemented digital signature process as recited in claim 85 wherein said summation process is performed in accordance with
M
′
≡
∑
i
=
1
k
M
i
′
(
w
i
-
1
mod
p
i
)
w
i
mod
n
,
where
w
i
=
∏
j
≠
i
p
j
.
87. A digital signature process as recited in claim 82 wherein said step of solving said sub-tasks includes processing each of said sub-tasks by an associated one of a plurality of exponentiator units operating substantially simultaneously.
88. A digital signature process as recited in claim 82 wherein each of said distinct random prime numbers has the same number of bits.
89. A digital signature process as recited in claim 82 wherein the plurality of k sub-tasks are performed in parallel.
90. A digital signature process as recited in claim 89 wherein said step of combining uses a form of the Chinese Remainder Theorem (CRT).
91. A processor-implemented method for establishing cryptographic communications, comprising the steps of:
encoding a plaintext message word M to a ciphertext word C, wherein M corresponds to a number representative of a message and wherein
0 ≦M≦n− 1,
wherein n is a composite number formed by the product of p 1 ·p 2 · . . . ·p k , k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, C is a number representative of an encoded form of message word M, and wherein said encoding step comprises transforming said message word M to said ciphertext word C, whereby
C≡M e (mod n),
and wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
decoding said ciphertext word C to a receive message word M′, said decoding step being performed using a decryption exponent d that is defined by
d≡e −1 mod ((p 1 −1) (p 2 −1) . . . (p k −1)),
said decoding step including the further steps of,
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 d 1 (mod p 1 ),
M 2 ′≡C 2 d 2 (mod p 2 ),
. . .
M k ′≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
92. A cryptographic communications system for establishing communications, comprising:
a communication medium;
encoding means coupled to said communication medium and adapted for transforming a transmit message word M to a ciphertext word C and for transmitting said ciphertext word C on said medium, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
wherein n is a composite number of the form,
n=p 1 ·p 2 · . . . ·p k
wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein said ciphertext word C corresponds to a number representative of an enciphered form of said message word M and corresponds to
C≡M e (mod n),
wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
decoding means communicatively coupled with said communication medium for receiving said ciphertext word C via said medium, said decoding means being operative to perform a decryption process for transforming said ciphertext word C to a receive message word M′, wherein M′ corresponds to a number representative of a deciphered form of C, said decryption process using a decryption exponent d that is defined by
d≡e −1 mod((p 1 −1)(p 2 −1) . . . (p k −1)),
said decryption process including the steps of
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 d 1 (mod p 1 ),
M 2 ′≡C 2 d 2 (mod p 2 ),
. . .
M k ′≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
93. A processor-implemented method for establishing cryptographic communications, comprising the steps of:
encoding a plaintext message word M to a ciphertext word C, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
n being a composite number formed from the product of p 1 ·p 2 · . . . ·p k , wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein the ciphertext word C is a number representative of an encoded form of message word M, wherein said step of encoding includes the steps of
defining a plurality of k sub-tasks in accordance with
C 1 ≡M 1 e 1 (mod p 1 ),
C 2 ≡M 2 e 2 (mod p 2 ),
. . .
C k ≡M k e k (mod p k ),
wherein
M 1 ≡M(mod p 1 ),
M 2 ≡M(mod p 2 ),
. . .
M k ≡M(mod p k ),
e 1 ≡e(mod(p 1 −1)),
e 2 ≡e(mod(p 2 −1)), and
. . .
e k ≡e(mod(p k −1)),
wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1), solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results C 1 , C 2 , . . . C k , and
combining said results of said sub-tasks to produce said ciphertext word C.
94. A cryptographic communications system for establishing communications, comprising:
a communication medium;
processor coupled to said communication medium and operative to transform a transmit message word M to a ciphertext word C and to transmit said ciphertext word C on said medium, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
n being a composite number formed from the product of p 1 ·p 2 · . . . ·p k wherein k is an integer greater than 2 and p 1 , p 2 , . . . , and p k are distinct random prime numbers, and wherein the ciphertext word C is a number representative of an encoded form of message word M, said processor being operative to transform said transmit message word M to said ciphertext word C by performing an encoding process comprising the steps of
defining a plurality of k sub-tasks in accordance with
C 1 ≡M 1 e 1 (mod p 1 ),
C 2 ≡M 2 e 2 (mod p 2 ),
. . .
C k ≡M k e k (mod p k ),
wherein
M 1 ≡M(mod p 1 ),
M 2 ≡M(mod p 2 ),
. . .
M k ≡M(mod p k ),
e 1 ≡e(mod(p 1 −1)),
e 2 ≡e(mod(p 2 −1)), and
. . .
e k ≡e(mod(p k −1)),
wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1), solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results C 1 , C 2 , . . . C k , and
combining said results of said sub-tasks to produce said ciphertext word C.
95. A processor-implemented method for establishing cryptographic communications, comprising the steps of:
decoding a ciphertext word C to a message word M, wherein M corresponds to a number representative of a message and wherein
0 ≦M≦n− 1,
wherein n is a composite number formed by the product of p 1 ·p 2 · . . . ·p k , k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, C is a number representative of an encoded form of message word M that is encoded by transforming said message word M to said ciphertext word C whereby
C≡M e (mod n),
and wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1);
said decoding step being performed using a decryption exponent d that is defined by
d≡e −1 mod((p 1 −1)(p 2 −1) . . . (p k −1)),
wherein said step of decoding includes the steps of
defining a plurality of k sub-tasks in accordance with
M 1 ≡C 1 d 1 (mod p 1 ),
M 2 ≡C 2 d 2 (mod p 2 ),
. . .
M k ≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results M 1 , M 2 , . . . M k , and
combining said results of said sub-tasks to produce said message word M.
96. A cryptographic communications system for establishing communications, comprising:
a communication medium;
processor communicatively coupled with said communication medium for receiving a ciphertext word C via said medium, and being operative to transform said ciphertext word C to a receive message word M′, wherein a message M corresponds to a number representative of a message and wherein,
0 ≦M≦n− 1,
wherein n is a composite number formed by the product of p 1 ·p 2 · . . . ·p k , k is an integer greater than 2 and p 1 , p 2 , . . . , p k are distinct random prime numbers, and wherein said ciphertext word C is a number representative of an encoded form of said message word M that is encoded by transforming M to said ciphertext word C whereby,
C≡M e (mod n),
and wherein e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1);
said decoding processor being operative to perform a decryption process using a decryption exponent d that is defined by
d≡e −1 mod((p 1 −1)(p 2 −1) . . . (p k −1)),
said decryption process including the steps of
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 d 1 (mod p 1 ),
M 2 ′≡C 2 d 2 (mod p 2 ),
. . .
M k ′≡C k d k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
97. A processor-implemented method for generating a digital signature, comprising the steps of:
signing a plaintext message word M to create a signed ciphertext word C, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
n being a composite number formed from the product of p 1 ·p 2 · . . . ·p k , wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein the signed ciphertext word C is a number representative of a signed form of message word M, wherein
C≡M d (mod n), and
wherein said step of signing includes the steps of
defining a plurality of k sub-tasks in accordance with
C 1 ≡M 1 d 1 (mod p 1 ),
C 2 ≡M 2 d 2 (mod p 2 ),
. . .
C k ≡M k d k (mod p k ),
wherein
M 1 ≡M(mod p 1 ),
M 2 ≡M(mod p 2 ),
. . .
M k ≡M(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
where d id defined by
d≡e −1 mod (( p 1 −1)·( p 2 −1)· . . . ·( p k −1)), and
e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1), solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results C 1 , C 2 , . . . C k , and
combining said results of said sub-tasks to produce said ciphertext word C.
98. A digital signature generation system, comprising:
a communication medium;
a processor coupled to said communication medium and operative to transform a transmit message word M to a signed ciphertext word C, and to transmit said signed ciphertext word C on said medium, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
n being a composite number formed from the product of p 1 ·p 2 · . . . ·p k , wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein the signed ciphertext word C is a number representative of a signed form of said message word M, wherein
C≡M d (mod n),
said processor being operative to transform said transmit message word M to said signed ciphertext word C by performing a digital signature generating process comprising the steps of;
defining a plurality of k sub-tasks in accordance with
C 1 ≡M 1 d 1 (mod p 1 ),
C 2 ≡M 2 d 2 (mod p 2 ),
. . .
C k ≡M k d k (mod p k ),
wherein
M 1 ≡M(mod p 1 ),
M 2 ≡M(mod p 2 ),
. . .
M k ≡M(mod p k ),
d 1 ≡d(mod(p 1 −1)),
d 2 ≡d(mod(p 2 −1)), and
. . .
d k ≡d(mod(p k −1)),
where d id defined by
d≡e −1 mod (( p 1 −1)·( p 2 −1)· . . . ·( p k −1)), and
e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1), solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results C 1 , C 2 , . . . C k , and
combining said results of said sub-tasks to produce said ciphertext word C.
99. A processor-implemented digital signature process, comprising the steps of:
signing a plaintext message word M to create a signed ciphertext word C, wherein M corresponds to a number representative of a message and wherein
0 ≦M≦n− 1,
wherein n is a composite number formed by the product of p 1 ·p 2 · . . . ·p k , k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, C is a number representative of a signed form of message word M, and wherein said encoding step comprises transforming said message word M to said ciphertext word C, whereby
C≡M d (mod n),
wherein d is defined by
d≡e −1 mod (( p 1 −1)·( p 2 −1)· . . . ·( p k −1)), and
e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
verifying said ciphertext word C to a receive message word M′ by performing the steps of,
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 e 1 (mod p 1 ),
M 2 ′≡C 2 e 2 (mod p 2 ),
. . .
M k ′≡C k e k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
e 1 ≡e(mod(p 1 −1)),
e 2 ≡e(mod(p 2 −1)), and
. . .
e k ≡e(mod(p k −1)),
solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem wherein each sub-task is a Chinese Remainder Theorem sub-problem to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.
100. A digital signature system, comprising:
a communication medium;
digital signature generating means coupled to said communication medium and adapted for transforming a message word M to a signed ciphertext word C and for transmitting said signed ciphertext word C on said medium, wherein M corresponds to a number representative of a message, and
0 ≦M≦n− 1,
wherein n is a composite number of the form
n=p 1 ·p 2 · . . . ·p k ,
wherein k is an integer greater than 2 and p 1 , p 2 , . . . p k are distinct random prime numbers, and wherein said signed ciphertext word C corresponds to a number representative of a signed form of said message word M and corresponds to
C≡M d (mod n),
wherein d is defined by
d≡e −1 mod(( p 1 −1)·( p 2 −1)· . . . ·( p k −1)), and
e is a number relatively prime to (p 1 −1), (p 2 −1), . . . , and (p k −1); and
digital signature verification means communicatively coupled with said communication medium for receiving said signal ciphertext word C via said medium, and being operative to verify said signed ciphertext word C by performing the steps of,
defining a plurality of k sub-tasks in accordance with
M 1 ′≡C 1 e 1 (mod p 1 ),
M 2 ′≡C 2 e 2 (mod p 2 ),
. . .
M k ′≡C k e k (mod p k ),
wherein
C 1 ≡C(mod p 1 ),
C 2 ≡C(mod p 2 ),
. . .
C k ≡C(mod p k ),
e 1 ≡e(mod(p 1 −1)),
e 2 ≡e(mod(p 2 −1)), and
. . .
e k ≡e(mod(p k −1)),
solving said sub-tasks in parallel using a form of the Chinese Remainder Theorem to determine results M 1 ′, M 2 ′, . . . M k ′, and
combining said results of said sub-tasks to produce said receive message word M′, wherein M′=M.