Methods and apparatus for verifying the cryptographic security of a selected private and public key pair without knowing the private key
AssigneeRSA Security Inc.
InventorsMoses Liskov, Robert Silverman, Ari Juels
Life of this patent
Estimating the term…
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.
Claims90
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 pi, 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 pi;
- (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 ki, wherein said blinding random numbers ki are members of a second distribution;
- (d) publishing, by said proving entity, a plurality of n commitment numbers hi, each of said commitment numbers hi comprising said base r raised to an exponent Ei;
- (e) publishing, by said proving entity, a sum k, said sum k equal to the sum of said plurality of blinding random numbers ki;
- (f) determining, by said verifying entity, that the product of said plurality of commitment numbers hi 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 Ei;
- (i) publishing, by said proving entity, all of said plurality of exponents Ei except said selected exponent;
- (j) determining, by said verifying entity, that the value of said base r raised to an exponent Ei equals a commitment number hi;
- and
- (k) determining, by said verifying entity, that an exponent Ei is greater than or equal to a lower bound and less than or equal to an upper bound.
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 pi, wherein said i is an index variable ranging from 1 to n, the method comprising the steps of:
- (a) selecting n blinding random numbers ki, wherein said blinding random numbers ki are members of a first distribution;
- (b) publishing a plurality of n commitment numbers hi said commitment numbers comprising a base r raised to a plurality of exponents Ei;
- (c) publishing the sum k, wherein said sum k equals the sum of said plurality of blinding random numbers ki;
- (d) receiving a selection from said verifying entity, said selection indicating an exponent selected from the group consisting of said plurality of exponents Ei;
- and
- (e) publishing all of said plurality of exponents Ei except said selected exponent.
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 pi, 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 pi;
- (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 h1 comprising said base r raised to a plurality of n exponents Ei;
- (e) receiving from said proving entity a sum k, wherein said sum k is the sum of a plurality of n blinding random numbers ki, wherein said blinding random numbers ki are selected from a second distribution;
- (f) verifying that the product of said plurality of commitment numbers hi 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 Ei;
- (i) receiving from said proving entity all of said plurality of exponents Ei except said selected exponent;
- (j) verifying that the value of said base r raised to each of said plurality of exponents Ei equals said plurality of commitment numbers hi;
- and
- (k) verifying that each of said plurality of exponents Ei is greater than or equal to a lower bound and less than or equal to an upper bound.
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 pi, 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 rk mod N, wherein said N is the product of said plurality of n prime numbers pi;
- (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 pi plus a product mk;
- (f) verifying, by said verifying entity, that the quantity rE equals the quantity rN+1(rk)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.
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 pi, 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 rk mod N, wherein said N is the product of said n prime numbers pi, 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 pi plus a product mk, wherein said m is a random variable, wherein said m is further an element of a third distribution.
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 pi, 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 rk mod N from a proving entity, wherein said N is the product of said n prime numbers pi, 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 pi plus a product mk;
- (f) verifying, by said verifying entity, that a quantity rE equals a quantity rN+1(rk)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.
A system for demonstrating the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers pi, 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 pi;
- (c) a second random variable generator for selecting n random variables ki, wherein said n random variables ki are members of a second distribution;
- (d) a transmitter sending a plurality of commitment numbers hi to said verifying device each of said commitment numbers comprising said base r raised to an exponent Ei;
- (e) a transmitter sending a sum k to said verifying device, said sum k equal to the sum of said n random variables ki;
- and
- (f) a transmitter sending said plurality of exponents Ei 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 hi equals a verification number XrN+(−1)n+k 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 Ei;
- (k) an analyzer for determining that the value of each of said plurality of n commitment numbers hi is equal to said base r raised to said exponent Ei;
- and
- (l) an analyzer for determining that said plurality of exponents Ei is greater than or equal to a lower bound and less than or equal to an upper bound.
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 pi, 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 ki, wherein said plurality of n blinding numbers ki are members of a first distribution;
- (b) a transmitter sending to said verifying device a plurality of n commitment numbers hi, each of said commitment numbers hi comprising a base r raised to an exponent Ei;
- (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 ki;
- (d) a receiver for receiving a selection from said verifying device indicating an exponent selected from said plurality of n exponents Ei;
- and
- (e) a transmitter sending to said verifying device all of said plurality of exponents Ei except said selected exponent.
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 pi, 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 pi;
- (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 hi, each of said commitment numbers hi comprising a base r raised to an exponent Ei;
- (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 ki, wherein said plurality of n blinding numbers ki are random variables selected from a second distribution;
- (f) an analyzer to determine that the product of said plurality of n commitment numbers hi 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 Ei;
- (i) a receiver for receiving from said proving device all of said plurality of exponents Ei except said selected exponent;
- (j) an analyzer to determine that the value of each of said plurality of n commitment numbers hi is equal to said base r raised to said exponent Ei;
- and
- (k) an analyzer to determine that said plurality of exponents Ei is greater than or equal to a lower bound and less than or equal to an upper bound.
A system for demonstrating the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers pi, 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 rk mod N to said verifying device, wherein said N is the product of said n prime numbers pi;
- (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 pi 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 rE equals the quantity rN+1(rk)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.
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 pi, 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 rk mod N to said verifying device, wherein said N is the product of said n prime numbers pi, 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 pi plus a product mk, wherein said m is a random variable, wherein said m is further an element of a third distribution.
A verifying device to determine the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers pi, 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 rk mod N from a proving device, wherein said N is the product of said n prime numbers pi, 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 rE equals the quantity rN+l(rk)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.
Dependencies are inferred from the claim text.