Methods and apparatus for verifying the cryptographic security of a selected private and public key pair without knowing the private key

• US 6,411,715 B1
• Filed: 11/10/1998
• Issued: 06/25/2002
• Est. Priority Date: 11/10/1997
• Status: Expired due to Fees

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: RSA Security Incorporated (Symphony Technology Group LLC)
• Inventors: Silverman, Robert, Liskov, Moses, Juels, Ari
• Primary Examiner(s): Barron, Jr., Gilberto
• Assistant Examiner(s): Darrow, Justin T.
• Application Number:
  US09/188,963
• Time in Patent Office: 1,323 Days
• Field of Search: 380/1, 380/28, 380/30, 380/44, 380/46, 380/277, 380/278, 380/283, 380/285, 380/286, 713/171
• US Class Current: 380/277
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

Methods and apparatus are disclosed for demonstrating that a public/private key pair is cryptographically strong without revealing information sufficient to compromise the private key. A key pair can be shown to be cryptographically strong by demonstrating that its modulus N is the product of two relatively large prime numbers. In addition, a key pair can be shown to be cryptographically strong by demonstrating that N is cryptographically strong against Pollard factoring attacks, Williams factoring attacks, Bach-Shallit factoring attacks, and weighted difference of squares factoring attacks.

Claims

1. A method for a proving entity to demonstrate to a verifying entity the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, the method comprising the steps of:

(a) determining, by said verifying entity, that a product N is the product of exactly n primes, wherein said product N is the product of said prime numbers p_i;

(b) selecting a base r, wherein said base r is an element of a first distribution;

(c) selecting, by said proving entity, a plurality of n blinding random numbers k_i, wherein said blinding random numbers k_i are members of a second distribution;

(d) publishing, by said proving entity, a plurality of n commitment numbers h_i, each of said commitment numbers h_i comprising said base r raised to an exponent E_i;

(e) publishing, by said proving entity, a sum k, said sum k equal to the sum of said plurality of blinding random numbers k_i;

(f) determining, by said verifying entity, that the product of said plurality of commitment numbers h_i equals a verification number X;

(g) determining, by said verifying entity, that said sum k is less than n times the largest element in said second distribution;

(h) publishing, by said verifying entity, a selection indicating an exponent selected from the group consisting of said plurality of exponents E_i;

(i) publishing, by said proving entity, all of said plurality of exponents E_i except said selected exponent;

(j) determining, by said verifying entity, that the value of said base r raised to an exponent E_i equals a commitment number h_i; and

(k) determining, by said verifying entity, that an exponent E_i is greater than or equal to a lower bound and less than or equal to an upper bound.

2. The method of claim 1 wherein said base r is jointly agreed upon by said verifying entity and said proving entity.

3. The method of claim 1 wherein said base r is generated by said verifying entity.

4. The method of claim 1 wherein said determining step (a) is performed according to the Gennaro, Micciancio, and Rabin protocol.

5. The method of claim 1 wherein said first distribution is a uniform distribution.

6. The method of claim 5 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

7. The method of claim 1 wherein said second distribution is a uniform distribution.

8. The method of claim 7 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^{{fraction (1/n+ε}

)}, wherein said ε

is a very small positive number relative to 1.

9. The method of claim 1 wherein said wherein said exponent E_i comprises the sum k_i+p_i+M_i said M_i comprising an n-way partitioning of lower order terms in the expansion of the Euler totient function of N.

10. The method of claim 1 wherein said verification number X is equal to r^N+(−

1)^n+k.

11. A method for a proving entity to demonstrate to a verifying entity the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, the method comprising the steps of:

(a) selecting n blinding random numbers k_i, wherein said blinding random numbers k_i are members of a first distribution;

(b) publishing a plurality of n commitment numbers h_i said commitment numbers comprising a base r raised to a plurality of exponents E_i;

(c) publishing the sum k, wherein said sum k equals the sum of said plurality of blinding random numbers k_i;

(d) receiving a selection from said verifying entity, said selection indicating an exponent selected from the group consisting of said plurality of exponents E_i; and

(e) publishing all of said plurality of exponents E_i except said selected exponent.

12. The method of claim 11 wherein said plurality of exponents E_i comprise said plurality of blinding random numbers k_i and said plurality of prime numbers p_i.

13. The method of claim 11 wherein said base r is an element of a second distribution, wherein said second distribution is a uniform distribution.

14. The method of claim 13 wherein said second distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

15. The method of claim 11 wherein said first distribution is a uniform distribution.

16. The method of claim 15 wherein said first distribution includes elements greater than or equal to 0 and less than or equal to N^{{fraction (1/n+ε}

)}, wherein said ε

is a very small positive number relative to 1.

17. The method of claim 11 wherein said wherein each of said plurality of exponents E_i comprises the sum k_i+p_i+M_i, said M_i comprising an n-way partitioning of lower order terms in the expansion of the Euler totient function of N, wherein said r is a random variable selected from a second distribution, wherein said N is the product of said plurality of prime numbers p_i.

18. A method for a verifying entity to verify the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, the method comprising the steps of:

(a) obtaining a product N, wherein said product N is the product of said n prime numbers p_i;

(b) verifying that said product N is the product of exactly n primes;

(c) selecting a base r, wherein said base r is an element of a first distribution;

(d) receiving from said proving entity a plurality of n commitment numbers h₁ comprising said base r raised to a plurality of n exponents E_i;

(e) receiving from said proving entity a sum k, wherein said sum k is the sum of a plurality of n blinding random numbers k_i, wherein said blinding random numbers k_i are selected from a second distribution;

(f) verifying that the product of said plurality of commitment numbers h_i equals a verification number X;

(g) verifying that said k is less than n times the largest element in said second distribution;

(h) publishing a selection indicating an exponent selected from the group consisting of said plurality of exponents E_i;

(i) receiving from said proving entity all of said plurality of exponents E_i except said selected exponent;

(j) verifying that the value of said base r raised to each of said plurality of exponents E_i equals said plurality of commitment numbers h_i; and

(k) verifying that each of said plurality of exponents E_i is greater than or equal to a lower bound and less than or equal to an upper bound.

19. The method of claim 18 wherein said verification step (b) is performed according to the Gennaro, Micciancio, and Rabin protocol.

20. The method of claim 18 wherein said first distribution is a uniform distribution.

21. The method of claim 18 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

22. The method of claim 18 wherein said verification number X is equal to r^N+(−

1)^n+k.

29. The method of claim 18 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^½

<sup>_n−

ε</sup>

, wherein said ε

is a very small positive number relative to 1.

23. A method for a proving entity to demonstrate to a verifying entity the cryptographic security of a private key and a public key, wherein said keys comprise a plurality of n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, the method comprising the steps of:

(a) selecting a base r, wherein said base r is an element of a first distribution;

(b) selecting, by said proving entity, a blinding random number k, wherein said blinding random number k is an element of a second distribution;

(c) publishing, by said proving entity, a quantity r^k mod N, wherein said N is the product of said plurality of n prime numbers p_i;

(d) publishing, by said verifying entity, a random variable m, wherein said random variable m is an element of a third distribution;

(e) publishing, by said proving entity, an exponent E, wherein said exponent E is equal to the sum of said plurality of prime factors p_i plus a product mk;

(f) verifying, by said verifying entity, that the quantity r^E equals the quantity r^N+1(r^k)^m mod N; and

(g) verifying, by said verifying entity, that said exponent E is greater than a lower bound and less than an upper bound.

24. The method of claim 23 wherein said base r is jointly agreed upon by said verifying entity and said proving entity.

25. The method of claim 23 wherein said base r generated by said verifying entity.

26. The method of claim 23 wherein said first distribution is a uniform distribution.

27. The method of claim 26 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

28. The method of claim 23 wherein said second distribution is a uniform distribution.

30. The method of claim 23 wherein said third distribution is a uniform distribution.

31. The method of claim 30 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^½

<sup>_n−

ε</sup>

, wherein said ε

is a very small positive number relative to 1.

32. The method of claim 23 wherein said lower bound comprises zero and said upper bound comprises the quantity nN^{{fraction (1/n+nε}

)}, wherein said ε

is a very small positive number relative to 1.

33. A method for a proving entity to demonstrate to a verifying entity the cryptographic security of a private key and a public key, wherein said keys comprise a plurality of n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, the method comprising the steps of:

(a) selecting, by said proving entity, a blinding random number k, wherein said blinding random number k is an element of a second distribution;

(b) publishing, by said proving entity, a quantity r^k mod N, wherein said N is the product of said n prime numbers p_i, wherein said base r is a random variable, wherein said base r is further an element of a first distribution; and

(c) publishing, by said proving entity, an exponent E, wherein said exponent E is equal to the sum of said plurality of prime factors p_i plus a product mk, wherein said m is a random variable, wherein said m is further an element of a third distribution.

34. The method of claim 33 wherein said first distribution is a uniform distribution.

35. The method of claim 34 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

36. The method of claim 33 wherein said second distribution is a uniform distribution.

37. The method of claim 36 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^½

<sup>_n−

ε</sup>

, wherein said ε

is a very small positive number relative to 1.

38. A method for a verifying entity to determine the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, the method comprising the steps of:

(a) selecting a base r, wherein said base r is an element of a first distribution;

(b) receiving, by said verifying entity, a quantity r^k mod N from a proving entity, wherein said N is the product of said n prime numbers p_i, and wherein said k is a blinding random number, and wherein said k is further an element of a second distribution;

(d) publishing, by said verifying entity, a random variable m, wherein said random variable m is an element of a third distribution;

(e) receiving, by said verifying entity, an exponent E from said proving entity, wherein said exponent E is equal to the sum of said plurality of prime factors p_i plus a product mk;

(f) verifying, by said verifying entity, that a quantity r^E equals a quantity r^N+1(r^k)^m mod N; and

(g) verifying, by said verifying entity, that said exponent E is greater than a lower bound and less than an upper bound.

39. The method of claim 38 wherein said base r is jointly agreed upon by said verifying entity and said proving entity.

40. The method of claim 38 wherein said random variable r is generated by said verifying entity.

41. The method of claim 38 wherein said first distribution is a uniform distribution.

42. The method of claim 41 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

43. The method of claim 38 wherein said third distribution is a uniform distribution.

44. The method of claim 43 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^½

^_n+ε

, wherein said ε

is a very small positive number relative to 1.

45. The method of claim 38 wherein said lower bound comprises zero and said upper bound comprises the quantity nN^{{fraction (1/n)}+nε}

, wherein said ε

is a very small positive number relative to 1.

46. A system for demonstrating the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, said system comprising a proving device and a verifying device, wherein said system further comprises:

(a) a first random variable generator for selecting a base r, wherein said base r is an element of a first distribution;

said proving device comprising;

(b) a transmitter sending a product N to said verifying device, said product N comprising the product of said n prime numbers p_i;

(c) a second random variable generator for selecting n random variables k_i, wherein said n random variables k_i are members of a second distribution;

(d) a transmitter sending a plurality of commitment numbers h_i to said verifying device each of said commitment numbers comprising said base r raised to an exponent E_i;

(e) a transmitter sending a sum k to said verifying device, said sum k equal to the sum of said n random variables k_i; and

(f) a transmitter sending said plurality of exponents E_i except for a selected exponent to said verifying device; and

said verifying device comprising;

(g) an analyzer for determining that said product N is the product of exactly n primes;

(h) an analyzer for determining that the product of said plurality of commitment numbers h_i equals a verification number Xr<sup>N+(−

1)n+k</sup> mod N;

(i) an analyzer for determining that said sum k is less than n times the largest element in said second distribution;

(j) a transmitter sending a selection to said proving device indicating an selected from the group consisting of said plurality of exponents E_i;

(k) an analyzer for determining that the value of each of said plurality of n commitment numbers h_i is equal to said base r raised to said exponent E_i; and

(l) an analyzer for determining that said plurality of exponents E_i is greater than or equal to a lower bound and less than or equal to an upper bound.

47. The system of claim 46 wherein said base r is jointly generated by said verifying device and said proving device.

48. The system of claim 46 wherein said base r is generated by said verifying device.

49. The system of claim 46 wherein said analyzer (g) executes the Gennaro, Micciancio, and Rabin protocol.

50. The system of claim 46 wherein said irst distribution is a uniform distribution.

51. The system of claim 50 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

52. The system of claim 46 wherein said second distribution is a uniform distribution.

53. The system of claim 52 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^{{fraction (1/n+ε}

+L )}, wherein said ε

is a very small positive number relative to 1.

54. The system of claim 46 wherein said lower bound comprises N^{{fraction (1/n)}−}

ε

, and said upper bound comprises nN<sup>{fraction (1/n+ε

+L )}, wherein said ε

is a very small positive number relative to</sup> 1.

55. The system of claim 46 wherein said exponent E_i comprises the sum k_i+p_i+M_i, said M_i comprising an n-way partitioning of lower order terms in the expansion of the Euler totient function of N.

56. The system of claim 46 wherein said verification number X equals r^N+(−

1)^n+k mod N.

57. A proving device to demonstrate to a verifying device the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, said proving device comprising:

(a) a second random variable generator for selecting a plurality of n blinding numbers k_i, wherein said plurality of n blinding numbers k_i are members of a first distribution;

(b) a transmitter sending to said verifying device a plurality of n commitment numbers h_i, each of said commitment numbers h_i comprising a base r raised to an exponent E_i;

(c) a transmitter sending to said verifying device a sum k, wherein said sum k equals the sum of said plurality of n blinding numbers k_i;

(d) a receiver for receiving a selection from said verifying device indicating an exponent selected from said plurality of n exponents E_i; and

(e) a transmitter sending to said verifying device all of said plurality of exponents Ei except said selected exponent.

58. The proving device of claim 57 wherein said exponent E_i comprises the sum k_i+p_i+M_i, said M_i comprising an n-way partitioning of lower order terms in the expansion of the Euler totient function of N.

59. The proving device of claim 57 wherein said base r is an element of a second distribution, wherein said second distribution is a uniform distribution.

60. The proving device of claim 59 wherein said second distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

61. The proving device of claim 57 wherein said first distribution is a uniform distribution.

62. The proving device of claim 61 wherein said first distribution includes elements greater than or equal to 0 and less than or equal to N^{{fraction (1/n)}+ε}

, wherein said ε

is a very small positive number relative to 1.

63. A verifying device for determining the cryptographic security of a private key and a public key, wherein said keys comprise a plurality of n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, said verifying device comprising:

(a) a receiver for receiving a product N, wherein said product N is the product of said plurality of n prime numbers p_i;

(b) an analyzer to determine that said N is the product of exactly n primes;

(c) a first random variable generator for selecting a base r, wherein said base r is an element of a first distribution;

(d) a receiver for receiving from a proving device a plurality of n commitment numbers h_i, each of said commitment numbers h_i comprising a base r raised to an exponent E_i;

(e) a receiver for receiving from said proving device a sum k, wherein said sum k is the sum of a plurality of n blinding numbers k_i, wherein said plurality of n blinding numbers k_i are random variables selected from a second distribution;

(f) an analyzer to determine that the product of said plurality of n commitment numbers h_i equals a verification number X;

(g) an analyzer to determine that said k is less than n times the largest element in said second distribution;

(h) a transmitter sending to said proving device a selection indicating an exponent selected from the group consisting of said plurality of exponents E_i;

(i) a receiver for receiving from said proving device all of said plurality of exponents E_i except said selected exponent;

(j) an analyzer to determine that the value of each of said plurality of n commitment numbers h_i is equal to said base r raised to said exponent E_i; and

(k) an analyzer to determine that said plurality of exponents E_i is greater than or equal to a lower bound and less than or equal to an upper bound.

64. The verifying device of claim 63 wherein said analyzer (b) executes the Gennaro, Micciancio, and Rabin protocol.

65. The verifying device of claim 63 wherein said first distribution is a uniform distribution.

66. The verifying device of claim 65 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

67. The verifying device of claim 63 wherein said verification number X equals r^N+(−

1)^n+k mod N.

68. A system for demonstrating the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, said system comprising a proving device and a verifying device, wherein said system further comprises:

(a) a first random variable generator for selecting a base r, wherein said base r is an element of a first distribution;

said proving device comprising;

(b) a second random variable generator for selecting a blinding random number k, wherein said blinding random number k is an element of a second distribution;

(c) a transmitter sending a quantity r^k mod N to said verifying device, wherein said N is the product of said n prime numbers p_i;

(d) a transmitter sending an exponent E to said verifying device, wherein said exponent E is equal to the sum of said plurality of prime factors p_i plus a product mk, wherein said m is a random variable, wherein said m is further an element of a third distribution;

said verifying device comprising;

(e) a transmitter sending a quantity m to said proving device;

(f) an analyzer for determining that the quantity r^E equals the quantity r^N+1(r^k)^m mod N; and

(g) an analyzer for determining that said exponent E is greater than a lower bound and less than an upper bound.

69. The system of claim 68 wherein said base r is jointly generated by said verifying device and said proving device.

70. The system of claim 68 wherein said base r generated by said verifying device.

71. The system of claim 68 wherein said first distribution is a uniform distribution.

72. The system of claim 71 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

73. The system of claim 68 wherein said second distribution is a uniform distribution.

74. The system of claim 73 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^{{fraction (1/2n+ε}

)}, wherein said ε

is a very small positive number relative to 1.

75. The system of claim 68 wherein said third distribution is a uniform distribution.

76. The system of claim 75 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^{{fraction (1/2n+ε}

)}, wherein said ε

is a very small positive number relative to 1.

77. The system of claim 68 wherein said lower bound comprises zero and said upper bound comprises the quantity nN^{{fraction (1/n+nε}

)}, wherein said ε

is a very small positive number relative to 1.

78. A proving device demonstrating the cryptographic security a private key and a public key to a verifying device, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, the proving device comprising:

(a) a second random variable generator for selecting a blinding random number k, wherein said blinding random number k is an element of a second distribution;

(b) a transmitter sending the quantity r^k mod N to said verifying device, wherein said N is the product of said n prime numbers p_i, wherein said base r is a random variable, wherein said base r is further an element of a first distribution; and

(c) a transmitter sending an exponent E to said verifying device, wherein said exponent E is equal to the sum of said plurality of prime factors p_i plus a product mk, wherein said m is a random variable, wherein said m is further an element of a third distribution.

79. The proving device of claim 78 wherein said first distribution is a uniform distribution.

80. The proving device of claim 79 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

81. The proving device of claim 78 wherein said second distribution is a uniform distribution.

82. The proving device of claim 81 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^{{fraction (1/2n+ε}

)}, wherein said ε

is a very small positive number relative to 1.

83. A verifying device to determine the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers p_i, wherein said i is an index variable ranging from 1 to n, the verifying device comprising:

(a) a first random variable generator for selecting a base r, wherein said base r is an element of a first distribution;

(b) a receiver obtaining the quantity r^k mod N from a proving device, wherein said N is the product of said n prime numbers p_i, and wherein said k is a blinding random number, and wherein said k is further an element of a second distribution;

(d) a transmitter sending a random variable m to said proving device, wherein said random variable m is an element of a third distribution;

(e) a receiver obtaining an exponent E from said proving device;

(f) an analyzer to determine that the quantity r^E equals the quantity r^N+l(r^k)^m mod N; and

(g) an analyzer to determine that said exponent E is greater than a lower bound and less than an upper bound.

84. The verifying device of claim 83 wherein said base r is jointly generated by said verifying device and said proving device.

85. The verifying device of claim 83 wherein said base r is generated by said verifying device.

86. The verifying device of claim 83 wherein said first distribution is a uniform distribution.

87. The verifying device of claim 86 wherein said uniform distribution includes elements greater than or equal to 2 and less than or equal to N−

1.

88. The verifying device of claim 83 wherein said third distribution is a uniform distribution.

89. The verifying device of claim 88 wherein said uniform distribution includes elements greater than or equal to 0 and less than or equal to N^½

^_n+ε

, wherein said ε

is a very small positive number relative to 1.

90. The verifying device of claim 83 wherein said lower bound comprises zero and said upper bound comprises the quantity nN^{{fraction (1/n+ε}

)}, wherein said ε

is a very small positive number relative to 1.