Patent ID: 6952476

Claim:
A method of exchanging digital public-key verification data whereby a first party enables a second party to obtain probabilistic evidence that a given public-key number n is the product of exactly two odd primes p and q, not known to the second party, whose bit lengths (l(p), l(q)) differ by not more than d bits; the method including the following steps, all operations being to mod P unless specified mod n, the method being halted should any check fail; a) said first party provides to said second party a number P such that P is a prime number and n|(P−1); b) said second party provides to said first party a number g where g=f (P−1)/n mod P, f<P; c) said first party provides to said second party numbers A and B, where A=g P mod P and B=g q mod P; d) said second party checks that A≠B, A≠1 and B≠1; whereupon the following steps are repeated up to k times; e) said second party selects a random number h∈Z n * such that ( h n ) = - 1 and provides the number h to the first party; f) said first party checks that ( h n ) = - 1 and selects two random numbers u and v such that l(u)=l((p−1)/2), l(v)=l(q−1)/2) and provides to said second party the values U=g 2u , V=g 2v , H U =B(h u mod n) , H V =A (h v mod n) , and H UV =h u h v mod n; g) said second party sends a request to the first party that the first party provides to the second party values r and s, which the second party randomly specifies should be either: (1) r=u and s=v; or (2) r=u+(p−1)/2, s=v+(q−1)/2 h) said first party provides the requested values r and s to the second party, i) if the second party requested r=u and s=v, the second party determines whether: (1) l(r)≦└l(n)/2┘+d, l(s)≦└l(n)/2┘+d, (2) g 2r+1 ≡Ug, g 2s+1 ≡Vg, (3) B (h r mod n) ≡H U , A (h d mod n) ≡H V , and (4) h r h s ≡H UV (mod n); thereby verifying the values provided by the first party to the second party are as were required by steps a) to f); or, if the second party requested r=u+(p−1)/2, s=v+(q−1)/2, the second party determines whether: (1) l(r)≦└l(n)/2┘+d, l(s)≦└l(n)/2┘+d, (2) g 2r+1 ≡UA, g 2s+1 ≡VB, (3) B (h r mod n) ≡H U ±1 , A (h s mod n) ≡H V ∓1 (± and ∓meaning the two exponents are of opposite sign), and (4) h r h s ≡H UV h (n−1)/2 (mod n), thereby obtaining said probabilistic evidence on whether the given public-key number n is the product of exactly two odd primes p and q whose bit lengths (l(p), l(q)) differ by not more than d bits.