Patent ID: 6952476
Filing Date: 2005-10-04
Classification: H04L

Abstract:
1. 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 c) said first party provides to said second party numbers A and B, where A=g 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  and provides the number h to the first party; f) said first party checks that  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 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: 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 (3) B (4) h 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, (3) B (4) h 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.