Cryptographic system and method with fast decryption

• US 6,081,598 A
• Filed: 10/20/1997
• Issued: 06/27/2000
• Est. Priority Date: 10/20/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dai, Wei
• Primary Examiner(s): Laufer, Pinchus M.
• Application Number:
  US08/953,911
• Time in Patent Office: 981 Days
• Field of Search: 380/28, 380/30, 380/44, 380/21
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD

Abstract

A cryptography system improves the decryption speed in the RSA algorithm by taking advantage of certain subgroups of Z_n *. The cryptography system employs a new family of trapdoor permutations based on exponentiation in subgroups of Z_n *.

Claims

1. In a system for sending messages over a network between first and second computing units, a method comprising the following steps:

(a) encrypting a message M into ciphertext C at the first computing unit, where the ciphertext C includes a value V and a value W, as follows;

(1) the value V is a function of a number x, V=x^e, where e is an integer and x is as follows;

x=g^R mod n, where;

(i) n is a number n=p₁ p₂ where p₁ and p2 are prime numbers with p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where r₁ and r₂ are random numbers, and q₁ and q₂ are prime numbers;

(ii) R is a random number selected independent of the random numbers r₁ and r₂ ; and

(iii) g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, where r₃ is a random number selected independent of the random numbers r₁, r₂, and R;

(2) the value W is a function of a value h(x) and the message M, the value h(x) being a result of a one-way function of the number x;

(b) sending the ciphertext C from the first computing unit to the second computing unit; and

(c) decrypting the ciphertext C at the second computing unit to reproduce the message M, where M is a function of the value W and the value h(x) and x is derived as x=V.sup.(1/e) mod q.sbsp.1^q.sbsp.2 mod n.

2. The method of claim 1, the encrypting step comprising the step of deriving the value W as W=h(x)⊕

M.

3. The method of claim 2, the decrypting step comprising the step of deriving the message M as M=W⊕

h(x).

4. The method of claim 1, the integer e equaling 2.

5. The method of claim 1:

the encrypting step comprising the step of computing a hash value h(x, M) from a hash function h of the number x and the message M;

the sending step comprising the step of sending the hash value h(x, M) along with the ciphertext C from the first computing unit to the second computing unit; and

the decrypting step comprising the steps of computing a test hash value h'"'"'(x, M) from the hash function h of the derived number x and the reproduced message M and comparing the bash value h(x, M) received from the first computing unit to the test hash value h'"'"'(x, M) to verify whether the message M has been altered.

6. The method of claim 1, the encrypting step comprising the following steps:

storing the number x;

generating a new number x'"'"' based on the old number x; and

using the new number x'"'"' for encrypting a next message.

7. A computer-implemented method for encrypting a message M into ciphertext C wherein:

n is a number in the form n=p₁ p₂, where p₁ and p₂ are prime numbers;

p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where r₁ and r₂ are random numbers and q₁ and q₂ are prime numbers; and

g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.3) mod n, where r₃ is a random number selected independent of the random numbers r₁, and r₂ ;

the computer-implemented method comprising the following steps;

computing a number x=g^R mod n, where R is a random number selected independent of the random numbers r₁, r₂, and r₃ ;

transforming the number x according to a one-way function h to yield a value h(x); and

encoding the message M according to a function of the value h(x).

8. The method of claim 7, the encoding step comprising the step of computing h(x)⊕

M.

9. The method of claim 7, further comprising the step of computing a hash value h(x, M) from a hash function h of the number x and the message M.

10. The method of claim 7, further comprising the following steps:

storing the number x;

generating a new number x'"'"' based on the old number x; and

using the new number x'"'"' for encrypting a next message.

11. A computer-implemented method for decrypting ciphertext C to reproduce a message M, wherein:

n is a number in the form n=p₁ p₂, where p₁ and p₂ are prime numbers;

p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where r₁ and r₂ are random numbers and q₁ and q₂ are prime numbers;

g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, where r₃ is a random number selected independent of the random numbers r₁ and r₂ ;

x is a number in the form of x=g^R mod n, where R is a random number selected independent of the random numbers r₁, r₂, and r₃ ;

e is an integer; and

V is a value in the form of V=x^e ;

the computer-implemented method comprising the following steps;

recovering the number x from the value V, where x=V.sup.(1/e) mod q.sbsp.1^q.sbsp.2 mod n;

transforming the number x according to a one-way function h to yield a value h(x); and

decoding the ciphertext C according to a function of the value h(x) to recapture the message M.

12. The method of claim 11, the decoding step comprising the step of computing C⊕

h(x).

13. The method of claim 11, further comprising the step of computing a hash value h(x, M) from a hash function h of the number x and the recaptured message M.

14. In a system for sending messages over a network between first and second computing units, a method comprising the following steps:

(a) encrypting a message M into ciphertext C at the first computing unit, where the ciphertext C includes a value V and a value W, as follows;

(1) the value V is a function of a number x, V=x^e, where e is an integer selected from the first b odd primes, and x is as follows;

x=g^R mod n, where;

(i) n is a number n=p₁ p₂ where p₁ and p₂ are prime numbers with p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where q₁ and q₂ are prime numbers and r₁ and r₂ are random numbers that are not divisible by the first b odd primes;

(ii) R is a random number selected independent of the random numbers r₁ and r₂ ; and

(iii) g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, where r₃ is a random number selected independent of the random numbers r₁, r₂, and R;

(2) the value W is a function of a value h(x) and the message M, the value b(x) being a result of a one-way function of the number x;

(b) sending the ciphertext C from the first computing unit to the second computing unit; and

(c) decrypting the ciphertext C at the second computing unit to reproduce the message M, where M is a function of the value W and the value h(x) and x is derived as x=V.sup.(1/e) mod q.sbsp.1^q.sbsp.2 mod n.

15. A system for sending messages over a communications channel, comprising:

an encoder to transform a message M into ciphertext C and transmit the ciphertext C over the communications channel, where the ciphertext C includes a value V and a value W, as follows;

(1) the value V is a function of a number x, V=x^e, where e is an integer and x is as follows;

x=g^R mod n, where;

(i) n is a number n p₁ p₂ where p₁ and p₂ are prime numbers with p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where r₁ and r₂ are random numbers, and q₁ and q₂ are prime numbers;

(ii) R is a random number selected independent of the random numbers r₁ and r₂ ; and

(iii) g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, where r₃ is a random number selected independent of the random numbers r₁, r₂, and R;

(2) the value W is a function of a value h(x) and the message M, the value h(x) being a result of a one-way function of the number x; and

a decoder coupled to receive the ciphertext C and the value V from the communications channel and to transform the ciphertext C back to the message M, where M is a function of the value W and the value h(x) and x is derived as x=V.sup.(1/e) mod q.sbsp.1^q.sbsp.2 mod n.

16. The system of claim 15, the encoder deriving the value W as W=h(x)⊕

M.

17. The system of claim 16, the decoder deriving the message M as M=W⊕

h(x).

18. The system of claim 15, the integer e equaling 2.

19. The system of claim 15:

the encoder computing a hash value h(x, M) from a hash function h of the number x and the message M and transmits the hash value h(x, M) along with the ciphertext C; and

the decoder computing a test hash value h'"'"'(x, M) from the hash function h of the derived number x and the reproduced message M and compares the hash value h(x, M) received from the first computing unit to the test hash value h'"'"'(x, M) to verify whether the message M has been altered.

20. The system of claim 15, the encoder storing the number x, generating a new number x'"'"' based on the old number x, and using the new number x'"'"' to compute the values V and W.

21. An encoder for a cryptographic system, where:

n is a number in the form n=p₁ p₂, where p₁ and p₂ are prime numbers;

p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ 30 1, where r₁ and r₂ are random numbers and q₁ and q₂ are prime numbers; and

g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, where r₃ is a random number selected independent of the random numbers r₁ and r₂ ;

the encoder comprising;

means for computing a number x=g^R mod n, where R is a random number selected independent of the random numbers r₁, r₂, and r₃ ;

means for transforming the number x according to a one-way function h to yield a value h(x); and

means for encoding a message M according to a function of the value h(x).

22. The encoder of claim 21, the encoding means encoding the message M according to the function h(x)⊕

M.

23. The encoder of claim 21, further comprising:

means for storing the number x;

means for generating a new number x'"'"' based on the old number x; and

means for using the new number x'"'"' to derive the value h(x).

24. A decoder for a cryptographic system, where:

n is a number in the form n=p₁ p₂, where p₁ and p₂ are prime numbers;

p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where r₁ and r₂ are random numbers and q₁ and q₂ are prime numbers;

g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, where r₃ is a random number selected independent of the random numbers r₁ and r₂ ;

x is a number in the form of x=g^R mod n, where R is a random number selected independent of the random numbers r₁, r₂, and r₃ ;

e is an integer;

V is a value in the form of V=x^e ; and

W is a value derived from a function of a message M and a value h(x), where h(x) is a result of a one-way function h;

the decoder comprising;

means for receiving the values V and W;

means for recovering the number x from the value V, where x=V.sup.(1/e) mod q.sbsp.1^q.sbsp.2 mod n;

means for transforming the number x according to a one-way function h to yield the value h(x); and

means for decoding the value W according to a function of the value h(x) to recapture the message M.

25. The decoder of claim 24, the decoding means computing the function W⊕

h(x) to recapture the message M.

26. The decoder of claim 24, further comprising means for computing a hash value h(x, M) from a hash function h of the number x and the recaptured message M.

27. A system for sending messages over a communications channel, comprising:

an encoder to transform a message M into ciphertext C and transmit the ciphertext C over the communications channel, where the ciphertext C includes a value V and a value W, as follows;

(1) the value V is a function of a number x, V=x^e, where e is an integer selected from the first b odd primes, and x is as follows;

x=g^R mod n, where;

(i) n is a number n=p₁ p₂ where p₁ and p₂ are prime numbers with p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where q₁ and q₂ are prime numbers and r₁ and r₂ are random numbers that are not divisible by the first b odd primes;

(ii) R is a random number selected independent of the random numbers r₁ and r₂ ; and

(iii) g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, mod n, where r₃ is a random number selected independent of the random numbers r₁, r₂, and R;

(2) the value W is a function of a value h(x) and the message M, the value h(x) being a result of a one-way function of the number x;

a decoder coupled to receive the ciphertext C and the value V from the communications channel and to transform the ciphertext C back to the message M, where M is a function of the value W and the value h(x) and x is derived as x=V.sup.(1/e) mod q₁ q₂ mod n.

28. A computer-readable medium having computer-executable instructions causing a computer to encrypt a message M to a ciphertext C, where:

n is a number in the form n=p₁ p₂, where p₁ and p₂ are prime numbers;

p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where r₁ and r₂ are random numbers and q₁ and q₂ are prime numbers; and

g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, where r₃ is a random number selected independent of the random numbers r₁ and r₂ ;

the computer-readable medium comprising;

computer-executable instructions which cause a computer to compute a number x=g^R mod n, where R is a random number selected independent of the random numbers r₁, r₂, and r₃ ;

computer-executable instructions which cause a computer to transform the number x according to a one-way function h to yield a value h(x); and

computer-executable instructions which cause a computer to encode a message M according to a function of the value h(x).

29. The computer-readable medium of claim 28, further comprising computer-executable instructions which cause a computer to encode the message M according to the function h(x)⊕

M.

30. The computer-readable medium of claim 28, further comprising computer-executable instructions which cause a computer to store the number x, generate a new number x'"'"' based on the old number x, and use the new number x'"'"' to derive the value h(x).

31. A computer-readable medium having computer-executable instructions causing a computer to decrypt ciphertext C to recover a message M, where:

n is a number in the form n=p₁ p₂, where p₁ and p₂ are prime numbers;

p₁ =r₁ q₁ +1 and p₂ =r₂ q₂ +1, where r₁ and r₂ are random numbers and q₁ and q₂ are prime numbers;

g is a number in the form of g=r₃.sup.(p.sbsp.1^-1)(p.sbsp.2^-1)/(q.sbsp.1 ^q.sbsp.2.sup.) mod n, where r₃ is a random number selected independent of the random numbers r₁ and r₂ ;

x is a number in the form of x=g^R mod n, where R is a random number selected independent of the random numbers r₁, r₂, and r₃ ;

e is an integer; and

V is a value in the form of V=x^e ;

the computer-readable medium comprising;

computer-executable instructions which cause a computer to recover the number x from the value V, where x=V.sup.(1/e) mod q.sbsp.1^q.sbsp.2 mod n;

computer-executable instructions which cause a computer to transform the number x according to a one-way function h to yield h(x); and

computer-executable instructions which cause a computer to decode the ciphertext C according to a function of h(x) to recapture the message M.

32. The computer-readable medium of claim 31, further comprising computer-executable instructions which cause a computer to decode the ciphertext C according to the function C⊕

h(x).

33. The computer-readable medium of claim 31, further comprising computer-executable instructions which cause a computer to compute a hash value h(x, M) from a hash function h of the number x and the recaptured message M.