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

[0002] This Application claims benefit of U.S. Provisional Application No. 60/065,053, filed Nov. 10, 1997.

[0003] This invention relates to cryptographic communications methods and systems that use a public key protocol, and more particularly to verifying the cryptographic security of a selected public and private key pair without knowing the private key.

[0004] Cryptographic systems are adapted to transfer securely messages between remote locations over unsecured communication networks. Such systems include at least one encoding device at a first location and at least one decoding device at a second location, with the encoding and decoding devices all being coupled to the network. The encoding device accepts, as inputs, a message-to-be-encoded (M) and an encoding key or encryption operator (E). The encoding device transforms the message M in accordance with the encryption operator to produce an encoded version (C) of the message (which is denoted as the ciphertext), where C=E(M). The decoding device accepts, as inputs, a ciphertext-to-be-decoded C and a decoding key or operator (D). The decoding device transforms the ciphertext in accordance with the decryption operator to produce a decoded version (M′) of the ciphertext, wherein M′=D(C) or M′=D(E(M)) and M′=M for all messages. Like the encoding key, the decoding key and decoded message M′ are digital sequences.

[0005] In a public-key cryptosystem, each user (e.g., user A) publishes an enciphering operator, or a public key, E_A. User A keeps private the details of the corresponding deciphering private key D_Awhich satisfies the equation D_A(E_A(M)=M for any message M. In order for the public key system to be practical, both E_Aand D_Amust be efficiently computable. Furthermore, user A must not compromise the cryptographic security of D_Awhen revealing E_A. That is, it should not be computationally feasible for an eavesdropper to find an efficient way of computing D_Agiven only a specification of the enciphering key E_A. In a public key system, a cryptographically secure selection of keys ensures that only user A is able to compute D_Aefficiently. Whenever another user (e.g., user B) wishes to send a message M to A, that user encodes M using the publicly-available E_Aand then sends the enciphered message E_A(M) to user A. User A deciphers the message by computing (D_A(E_A(M))=M. Since D_Ais not derivable from E_Ain a practical way, only user A can decipher the message E_A(M). If user A wants to send a response to user B, user A enciphers the message using user B's encryption key E_B, also available in publicly.

[0006] The public key approach is also used to provide signed digital messages that are both message-dependent and signer-dependent. The recipient of a “signed” message not only knows the message substance, but is also assured that the message originated from the identified sender. A signed message precludes the possibility that a recipient could modify the received message by changing a few characters or that the recipient could attach the received signature to any message whatsoever.

[0007] When user A wants to send user B a “signed” document M, user A first uses his own decryption key D_Ato transform M into a signed message word M_s, where M_S=D_A(M). User A then uses user B's publicly-available encryption key E_Bto generate a signed ciphertext word C_S=E_B(M_S)=E_B(D_A(M)), which is sent to user B. User B initially uses his secret decryption key D_Bto reduce the signed ciphertext C_Sto a signed message word in accordance with D_B(C_S)=D_B(E_B(M_S))=M_S. Now using user A's publicly-available encoding key E_A, user B decodes the signed message word in accordance With E_A(M_S)=E_A=M. User A cannot deny having sent user B this message, since no one but A could have created M_S=D_A(M), provided that D_Ais not Computable from E_A, i.e. provided that D_Ais cryptographically secure. Furthermore, user B can show that the public key E_Ais necessary to extract the message M so that user B has “proof” that user A has signed the document. User B cannot modify M to a different version M′, since then user B would have to create the corresponding signature D_A(M′) as well. Therefore user B must have received a document “signed” by A, which he can “prove” that A sent, but which B cannot modify in any detail.

[0008] In a communication system which is adapted to pro)vide digital signatures, each transmitting and receiving terminal is provided with both an encoding and decoding device, each device being functionally equivalent to the devices described above but operating on a different set of input words with a different key. The transmitting terminal decoding device transforms a message M using its own decoding key to generate a signed message M_S. Then the encoding device transforms the resultant signed message M_Swith the intended receiving terminal's encoding key to generate signed ciphertext word C_S. The receiving terminal's decoding device then transforms the received C_Swith its own decoding key to obtain the signed message M_S, and then the encoding device transforms the resultant signed message with the transmitting terminal's encoding key to obtain the original message. For example, in a system for transmitting signed messages from user A to user B, the terminal for user A includes at least one encoding device characterized by an encoding key E_B=(e_B, N_B) and at least one decoding device, characterized by a decoding key D_A=(d_A, N_A). Similarly, the terminal for user B includes an encoding device characterized by an encoding key E_A=(e_A, N_A) and a decoding device characterized by a decoding key D_B=(d_B, N_B). The encoding and decoding devices of terminals A and B are described above.

[0009] In operation, to provide a signed message, user A first generates a ciphertext signed message word M_S

[0010] M_s≡M^d(mod N_A)

[0011] and then transforms that signed message word to a signed ciphertext word C_S: which is then transferred to user B. User A may readily use D_Aand N_Afrom his own

[0012] C_S=M_S^e(mod N_B)

[0013] decoding key to reduce the signed ciphertext word to a signed message word, and then perform the encoding transformations using E_Band N_Bfrom the publicly available file.

[0014] User B deciphers the received C_Sinto the signed message word M_Sin accordance with

[0015] M_S≡(C_S)^d(mod N_B)

[0016] User B then transforms M_Sto M in accordance with

[0017] M≡M_S^e(mod N_A)

[0018] User B may readily perform his decoding transformations since D_Band N_Bare part of his decoding key and E_Aand N_Aare readily available on the public file.

[0019] Because public key cryptography can be used for authentication of transactions, a cryptographically strong key pair (i.e. a public key and a corresponding private key) is desirable to prevent a party to a transaction from subsequently repudiating it. If a transaction is authenticated with a weak key pair, it is easier for a party to the transaction to subsequently repudiate it by arguing that the private key had succumbed to a cryptanalytic attack.

[0020] When business transactions are conducted over an unsecured network there is a critical need to assure the cryptographic security of the private key. The integrity of the transactions are assured not only by preventing an unauthorized party to decipher or alter the transmitted message, or by uniquely identifying the sender, but also by preventing the sender from repudiating the transaction later. That is, the author should be the constructor of the private key and the only party having access to the private key. On the other hand, a certifying authority (i.e., a verifier) should be able to verify the cryptographic security of the private key without receiving information sufficient to calculate the private key. In a certifying process, the constructor (i.e., the prover) would prove the cryptographic security of the selected private key to the verifier while interacting over the unsecured network. Certification authorities validate key pairs. This validation usually involves the assumption of liability. It is desirable for a certification authority to verify the cryptographic security of a key pair before validating it and thus assuming liability on its behalf.

[0021] The best known factoring algorithms which can be used for cryptanalytic attacks are the Elliptic Curve Method (ECM), the Quadratic Sieve (QS), and the Number Field Sieve (NFS). The computational run-time required by the Number Field Sieve does not depend on the size of the factors. The Number Field Sieve is described in Lenstra, A. K., and Lenstra, Jr., H. W., eds., Lecture Notes in Mathematics 1554: The Development of the Number Field Sieve, Springer-Verlag, 1993. The run-time necessary for ECM to find a factor p of a larger integer N depends on the size of p. Finding factors greater than 60 decimal digits is regarded as impractical with current computer technology. To make the factoring of N as difficult as possible means making p too large for ECM. This is accomplished by taking p to be just slightly smaller than {square root over (N)}.

[0022] Two other cryptanalytic attacks known in the art are the Pollard P−1 factoring algorithm and the Williams P+1 factoring algorithm. These algorithms can succeed in factoring N=pq if either p±1 or q±1 has only small prime factors. To make the factoring of N as difficult as possible means selecting p and q such that p−1, p+1, q−1, and q+1 all have large prime factors.

[0023] Another cryptanalytic attack is described in E. Bach & J. Shallit, Factoring with Cyclotomic Polynomials, Math. Comp. 52 (1989), 201-219. The Bach-Shallit algorithm can succeed in factoring N=pq if cyclotomic polynomials in either p or q have only small prime factors. To make the factoring of N as difficult as possible means selecting p and q such that cyclotomic polynomials in p and q all have large prime factors.

[0024] Another cryptanalytic attack is the weighted difference of squares algorithm. This algorithm can succeed in factoring N=pq if p and q are too close together, which allows N to be represented as x²-y². To make the factoring of N as difficult as possible means selecting p and q such that the ratio p/q is not approximated by a ratio a/b, where a and b are two reasonably small integers.

[0025] As can be seen from above, the underlying cryptographic security of the public key cryptographic protocols rests upon the difficulty of factoring large composite integers. The systems and methods described herein enable an entity to prove to a verifying entity that the constructed private key is cryptographically secure without revealing sufficient information to factor the private key.

[0026] In one aspect, this invention provides methods and systems for demonstrating that a number N is the product of two large prime factors without revealing any information about its factors.

[0027] In another aspect, this invention provides methods and systems for demonstrating that a number N is resistant to Pollard P−1 factoring attacks without revealing any information about its factors. In yet another aspect, this invention provides methods and systems for demonstrating that a number N is resistant to Williams P+1 factoring attacks without revealing any information about its factors.

[0028] In another aspect, this invention provides methods and systems for demonstrating that a number N is resistant to Bach-Shallit cyclotomic polynomial factoring attacks without revealing any information about its factors.

[0029] In another aspect, this invention provides methods and systems for demonstrating that a number N is resistant to weighted difference of squares factoring attacks without revealing any information about its factors.

[0030] FIG. 1 is a flow chart illustrating a protocol for executing a proof protocol over an open channel.

[0031] FIG. 2 is a diagram illustrating the components of a general purpose computer.

[0032] FIG. 3 is a flow chart illustrating a protocol for demonstrating that a number N is the product of two large primes.

[0033] FIG. 4 is a flow chart illustrating a protocol for demonstrating that a number N is resistant to Pollard P−1 factoring attacks and Williams P+1 factoring attacks.

[0034] FIG. 5 is a flow chart illustrating a protocol for demonstrating that a number N is resistant to Bach-Shallit cyclotomic polynomial factoring attacks.

[0035] FIG. 6 is a flow chart illustrating a protocol for demonstrating that a number N is resistant to weighted difference of squares factoring attacks.

[0036] Overview

[0037] There are several public key cryptographic protocols. The Diffie-Hellman cryptographic protocol was described in U.S. Pat. Nos. 4,200,770 and 4,218,582. As summarized in U.S. Pat. No. 5,313,521, the Diffie-Hellman protocol uses a prime number p and an integer a that is between 0 and p−1. For user A and user B to obtain a shared secret number, user A randomly generates a secret number X_Aand computes a corresponding public number Y_A, where Y_A=a^Xmod p. User B also randomgly generates a secret number X_Band computes a corresponding public number Y_B, where Y_B=a^Xmod p. When p is large, it is computationally infeasible to obtain the secret numbers from the public numbers.

[0038] User A and user B publish only their non-secret public numbers Y_Aand Y_B. By the commutative property, user A computes

[0039] E=Y_B^Xmod p

[0040] while user B computes the same number by

[0041] E=Y_A^Xmod p.

[0042] The RSA communication system also uses the public key protocol, wherein each user has at least one encoding device and at least one decoding device. The encoding device is responsive to an applied message-to-be-transmitted (M) and an encoding key to provide a ciphertext word (C) for transmission to a particular decoding device. The encoding key (E) is a pair of positive integers e and N, which are related to the particular decoding device. The message M is a number representative of a message-to-be-transmitted and is in the range:

[0043] 1<M≦N−1

[0044] where N is a composite number of the form

[0045] N=p·q

[0046] where p and q are odd prime numbers.

[0047] For messages represented by numbers outside the range 0 to N−1, a conventional blocking means is utilized to break the message into message block words before encoding, where each block word is representative of a number within the specified range. Following subsequent decoding, the recovered block words may be transformed back to the original message.

[0048] The transformation provided by the encoding device is described by the relation

[0049] C≡M^e(mod N)

[0050] where e is a number relatively prime to (p−1)·(q−1).

[0051] The particular decoding device is also coupled to the channel and is adapted to receive the ciphertext C from the channel. The decoding device is responsive to the received ciphertext word C and a decoding key to transform that ciphertext to a received message word M′. The decoding key D is a pair of positive integers d and N. M′ is a number representative of a deciphered form of C (i.e. reconstituted plaintext) and corresponds to the relation

[0052] M¹≡C^d(mod N)

[0053] where d is a multiplicative inverse of e modulo the least common multiple of p−1 and q−1 so that

[0054] e·d=1 mod(lcm((p−1),(q−1)))

[0055] where lcm((p−1), (q−1)) is the least common multiple of p−1 and q−1.

[0056] With these encoding and decoding devices, a message sent from the encoding device to the decoding device is transformed from M to C by the encoding device, and then back from C to M′ by the decoding device, where M′=M (mod N).

[0057] The invention also applies to public key cryptographic protocols with elliptic curves as described by Victor Miller in “Uses of Elliptic Curves in Cryptography”, Advances in Cryptology, Crypto '85, pages 417-426, or in U.S. Pat. Nos. 5,272,755 and 5,351,297.

[0058] In a preferred embodiment of the invention, a prover generates a key pair and wishes to demonstrate to a verifier the cryptographic strength of the key pair without revealing any information about the key pair's private key.

[0059] There are several aspects of cryptographic strength that the prover may wish to demonstrate. First, the prover may wish to demonstrate that an integer N, which is the product of prime numbers p and q, is difficult to factor. Specifically, the prover may wish to demonstrate that the factors p and q are two large, nearly equal primes. Second, the prover may wish to demonstrate that the prime factors p and q are resistant to Pollard and Williams factoring attacks. Specifically, the prover may wish to demonstrate that the numbers p±1 and q±1 have large prime factors. In a preferred embodiment, the prover may wish to demonstrate the key pair's compliance with the ANSI X9.31 and X9.44 standards by demonstrating that prime factors of p±1 and q+1 are greater than a security parameter. Third, the prover may wish to demonstrate that the prime factors p and q are resistant to Bach-Shallit factoring attacks. Specifically, the prover may wish to demonstrate that cyclotomic polynomials in p and q have large prime factors. Fourth, the prover may wish to demonstrate that the product N is resistant to a factoring attack which represents N as a weighted difference of squares. Specifically, the prover may wish to demonstrate that for any given small integers a and b, the size of |ap-bq| is large.

[0060] The protocols demonstrating these elements of cryptographic strength require that certain ancillary properties also be demonstrated. First, the prover will need to demonstrate from public information g^amod S, g^bmod S, and g^cmod S that c=ab. (For the purposes of this invention, a very large prime number S, and a generator g of (Z/SZ)* are public information which may be known a priori by both the prover and the verifier.) Second, the prover will need to bound the size of b given g^bmod S. Third, the prover will need to demonstrate that p is prime given g^pmod S.

[0061] Referring now to FIG. 1, a system according to the present invention includes a proving node 12 (referred to throughout as a “proving node” or a “prover”) and a verifying node 14 (referred to throughout as a “verifying node” or a “verifier”). The verifying node 14 and the proving node 12 communicate over a communications channel 16. Communications channel 16 may be any form of physical cabling or, alternatively, communications channel 16 may be a wireless communication medium such as a infrared. Further, communications channel 16 may support any of a number of communications protocols, including but not limited to Ethernet, IP, ATM, Frame Relay, X.25, or any other suitable communication protocols known in the art.

[0062] In one embodiment, a prover 12 and a verifier 14 may be special-purpose hardware designed and implemented specifically for the purpose of performing encryption and decryption functions. In another embodiment, a prover 12 and a verifier 14 may be implemented in smartcards and smarteard readers. In this embodiment, a smartcard generates a key pair and demonstrates that the key pair is cryptographically strong without revealing any information about the private key. A typical smart card is designed to be tamper-proof in order to defeat physical attacks on the information thereon, such as x-ray photography and power-use monitoring. In yet another embodiment, a prover 12 and a verifier 14 may be implemented in a handheld computing device such as a 3Com Palm Pilot. In yet another embodiment, a prover 12 and a verifier 14 may be implemented as a programmed general-purpose computer.

[0063] The computer can be any personal-type computer or workstation such as a PC or PC-compatible machine, an Apple Macintosh, a Sun workstation, etc. In general, any device could be used as long as it is able to perform all of the functions and capabilities described herein. The particular type of computer or workstation is not central to the invention.

[0064] Referring to FIG. 2, the computer 214 typically will include a central processor 220, a main memory unit 222 for storing programs and/or data, an input/output (I/O) controller 224, a display device 226, and a data bus 228 coupling these components to allow communication therebetween. The memory 222 includes random access memory (RAM) and read only memory (ROM) chips. The computer 214 typically also has one or more input devices 230 such as a keyboard 232 (e.g., an alphanumeric keyboard and/or a musical keyboard), a mouse 234, and the joystick 212. In a preferred embodiment, the system 210 includes the single joystick 212, the alphanumeric keyboard 232, and the mouse 234.

[0065] The computer 214 typically also has a hard drive 236 with hard disks therein and a floppy drive 238 for receiving floppy disks such as 3.5 inch disks. Other devices 240 also can be part of the computer 214 including output devices (e.g., printer or plotter) and/or optical disk drives for receiving and reading digital data on a CD-ROM. In the disclosed embodiment, one or more computer programs define the operational capabilities of the system 210, as mentioned previously. These programs can be loaded onto the hard drive 236 and/or into the memory 222 of the computer 214 via the floppy drive 238. In general, the controlling software program(s) and all of the data utilized by the program(s) are stored on one or more of the computer's storage mediums such as the hard drive 236, CD-ROM 240, etc. In general, the programs implement the invention on the computer 214, and the programs either contain or access the data needed to implement all of the functionality of the invention on the computer 214.

[0066] Demonstrating that N is the Product of Two Large Primes

[0067] In one embodiment, a prover 12 has generated an RSA key pair and wishes to demonstrate its cryptographic strength to a verifier 14. The prover 12 wishes to demonstrate that N, which is a known component of the public key, is the product of two relatively large prime factors p and q without revealing any information about the prime factors p and q themselves.

[0068] The protocol of this embodiment, designated the two_large_prime_factors protocol for the purposes of this invention, allows the prover 12 to demonstrate this property. The protocol stems from Euler's theorem, which states that if an r and N are relatively prime—that is, their greatest common divisor is 1—and if φ(N) is the Euler totient function, φ(N)=(p−1)(q−1)=N−p−q+1, then:

[0069] r^φ(N)≡1 mod N.

[0070] From Euler's theorem, it follows that:

[0071] r^p+q≡r^N−1mod N

[0072] where r and N are relatively prime.

[0073] In the protocol of this embodiment, r is a random variable drawn from a random distribution. In a preferred embodiment, this distribution is a uniform distribution. In a more preferred embodiment, this uniform distribution has a minimum of 2 and a maximum of N−1.

[0074] In one embodiment, the prover 12 and the verifier 14 agree upon an r. In an alternative embodiment, the verifier 14 may generate the r and send it to the prover 12.

[0075] For the purposes of this invention, when one party executing a protocol sends information to another party executing the protocol, it is viewed as the functional equivalent of publishing the information. Similarly, when one party executing a protocol publishes information, it is viewed as the functional equivalent sending the information to another party executing the protocol.

[0076] When determining the r, it must be checked to make sure that it is relatively prime to N. One of ordinary skill in the art will recognize that this can be accomplished by taking the gcd of r with N and verifying that the result is 1.

[0077] Referring now to FIG. 3, the prover 12 and the verifier 14 next execute 302, 304 the Gennaro, Micciancio, & Rabin protocol to demonstrate that N is the product of exactly two primes. This protocol is described below.

[0078] The prover 12 then generates 306 two blinding numbers, k1 and k2. The blinding numbers are two independent random variables drawn from a random distribution. In a preferred embodiment, this distribution is a uniform distribution. In a more preferred embodiment, this uniform distribution has a minimum of 0 and a maximum of N^½+ε, where ε is a very small positive number relative to 1.

[0079] The prover 12 then calculates 308 commitment numbers h1 and h2, where h1≡r^p+k1mod N, and h2≡r^q+k2mod N. The prover 12 also calculates 308 the sum k=k1+k2. The prover 12 then sends 308 h1, h2, and k to the verifier 14.

[0080] The verifier 14 then examines 310 h1, h2, , and k. Specifically, the verifier 14 verifies 310 that h1×h2≡r^N+1+kmod N, and that k is less than twice the maximum value of the random distribution from which k1 and k2 were drawn.

[0081] The verifier 14 then sends 312 the prover 12 an indicator with a randomly chosen state. This indicator can be in either a first or second state. In one embodiment, the first and second state are equally probable.

[0082] The prover 12 then sends 322 and exponent E to verifier 14. The value of E varies in response to the state of the indicator. If the indicator is in the first state, then E is set 320 to p+k1. If the indicator is in the second state, then E is set 318 to q+k2.

[0083] The verifier 14 then evaluates 324 E. Specifically, if the indicator is in the first state, the verifier 14 verifies 330 that h1=r^p+k1, and if the indicator is in the second state, the verifier 14 verifies 328 that h2=r^q+k2. The verifier 14 also verifies 332 that E is within an upper and lower bound. In one embodiment, the lower bound is N^{{fraction (1/2−ε)}}, and the upper bound is 2N^{{fraction (1/2+ε)}}, where ε is a very small positive number relative to 1.

[0084] If any of the verifications are unsuccessful, the prover 12 has failed to demonstrate that N is the product of two large primes. If this outcome occurs, the verifier 14 may refuse to assume any liability on the behalf of the prover 12. In this case, the prover 12 may choose to generate another key pair for certification by the verifier 14.

[0085] Alternate Embodiment for Demonstrating that N is the Product of Two Large Primes

[0086] In another embodiment of the invention, the r is selected in a manner similar to the previous embodiment. The prover 12 generates a random blinding number k in a manner similar to the previous embodiment. In this embodiment, k is a random variable drawn from a random distribution. In a preferred embodiment, this distribution is a uniform distribution. In a more preferred embodiment, this uniform distribution has a minimum of 0 and a maximum of N^{{fraction (1/4+ε)}}, where ε is a very small positive number relative to 1.

[0087] In this embodiment, the prover 12 generates r^kand sends this number to the verifier 14.

[0088] The verifier 14 then generates a number m and sends it to the prover 12. In this embodiment, m is a random variable drawn from a random distribution. In a preferred embodiment, this distribution is a uniform distribution. In a more preferred embodiment, this uniform distribution has a minimum of 0 and a maximum of N^{{fraction (1/4+ε)}}, where ε is a very small positive number relative to 1.

[0089] The prover 12 then calculates p+q+(mk) and sends this result to the verifier 14. The verifier 14 then verifies that r^p+q+mk≡r^N+1(r^k)^mmod N and that

[0090] 0<p+q+(mk)<2N^½+2ε.

[0091] Demonstrating Resistance to Pollard and Williams Factoring Attacks

[0092] In one embodiment, a prover 12 has generated an RSA key pair and wishes to demonstrate its cryptographic strength to a verifier 14. The prover 12 wishes to demonstrate that the prime factors of N—p and q—are resistant to Pollard P−1 factoring attack and the Willliams P+1 factoring attack. Specifically, the prover 12 wishes to demonstrate strength against the Pollard P−1 factoring attack by demonstrating that (p−1) and (q−1) have large prime factors. Similarly, the prover 12 wishes to demonstrate strength against the Williams P+1 factoring attack by demonstrating that (p+1) and (q+1) have large prime factors.

[0093] For the purposes of this invention, a very large prime number S, and a generator g of (Z/SZ)* are public information which are known by both the prover 12 and the verifier 14. In one embodiment, S and g are jointly generated by the prover 12 and the verifier 14.

[0094] Referring now to FIG. 4, the prover 12 first publishes 404 N, g^pmod S, and g^qmod S. The prover 12 and verifier 14 then perform 406, 408 the zkp_product protocol, described below, to demonstrate that N is the product of p and q without revealing any information about p and q.

[0095] The prover 12 then selects 410 four large prime factors p1, p2, p3 and p4 from each of the four quantities (p−1), (p+1), (q−1), and (q+1) respectively. The prover 12 then determines 410 four coefficients a1, a2, a3, and a4 such that a1×p1=(p−1), a2×p2=(p+1), a3×p3=(q−1),and a4×p4=(q+1). The prover 12 then publishes 414 g^p1mod S, g^p2mod S, g^p3mod S, g^p4mod S, g^a1mod S, g^a2mod S, g^a3mod S, and g^a4mod S. The quantities g^p+1mod S, g^p1mod S, g^q+1mod S, and g^q−1mod S are readily computed 412 from the published values g^pmod S, and g^qmod S.

[0096] The prover 12 and the verifier 14 then perform 416, 418 the zkp_product protocol, described below, four times to demonstrate that a1×p1=(p−1), a2×p2=(p+1), a3×p3=(q−1), and a4×p4=(q+1), all without revealing any additional information about p1, p2, p3, p4, a1, a2, a3, a4, p or q.

[0097] The prover 12 and the verifier 14 then perform 420, 422 the zkp_prime protocol, described below, four times to demonstrate that p1, p2, p3, and p4 are prime, all without revealing any additional information about p1, p2, p3, or p4.

[0098] The prover 12 and the verifier 14 then perform 424, 426 the zkp_size protocol, described below, four times to demonstrate that p1, p2, p3, and p4 are larger than a specified security parameter, all without revealing any additional information about p1, p2, p3, or p4.

[0099] Demonstrating Resistance to Bach-Shallit Factoring Attacks

[0100] In one embodiment, a prover 12 has generated an RSA key pair and wishes to demonstrate its cryptographic strength to a verifier 14. The prover 12 wishes to demonstrate that the prime factors of N—p and q—are resistant to a Bach-Shallit attack, as described in E. Bach & J. Shallit, Factoring with Cyclotomic Polynomials, Math. Comp. 52 (1989), 201-219. Specifically, the prover 12 wishes to demonstrate that cyclotomic polynomials in p and q have large prime factors.

[0101] For the purposes of this invention, a very large prime number S, and a generator g of (Z/SZ)* are public information which are known by both the prover 12 and the verifier 14. In one embodiment, S and g are jointly generated by the prover 12 and the verifier 14.

[0102] In one embodiment, illustrated in FIG. 5, the prover 12 wishes to demonstrate that the cyclotomic polynomial p²+p+1 has a large prime factor. The prover 12 publishes 502 g^pmod S and g^pmod S. The prover 12 also selects 506 a large prime factor p5 of the cyclotomic polynomial and calculates 506 a coefficient a5 such that a5×p5=p2+p+1. The prover 12 then publishes 508 g^p5mod S, and g^a5mod S. The prover 12 and verifier 14 then perform 510, 512 the zkp_product protocol, described below, to demonstrate that a5×p5=p2+p+1, without revealing any information about p5, a5, or p.

[0103] The prover 12 and the verifier 14 then perform 514, 516 the zkp_prime protocol, described below, to demonstrate that p5 is prime without revealing any additional information about p5.

[0104] The prover 12 and the verifier 14 then perform 518, 520 the zkp_size protocol, described below, to demonstrate that p5 is larger than a specified security parameter without revealing any additional information about p5.

[0105] This technique can be extended to other cyclotomic polynomials, including, but not limited to, p²+1, p⁴+p³+p²+p+1, p²−p+1, p⁶+p⁵+p⁴+p³+p²+p+1, and p⁴+1. This technique can also be applied to cyclotomic polynomials in q.

[0106] Demonstrating Resistance to Weighted Difference of Squares Attacks

[0107] In one embodiment, a prover 12 wishes to demonstrate that a private key is resistant to weighted difference of squares attacks. The weighted difference of squares attack is predicated on the property that if p and q are too close together, then N may be easily factored by representing it as x²−y².

[0108] In one embodiment, a prover 12 publishes g^pmod S, g^pmod S, and two reasonably small integers, a and b. In an alternate embodiment, the verifier 14 publishes a and b. In yet another embodiment, illustrated in FIG. 6, the prover 12 and verifier 14 agree on a and b before starting the protocol.

[0109] The verifier 14 then calculates 604 g^−qmod S via the Euclidean Algorithm. The verifier 14 also calculates 604 g^apmod S, g^−bqmod S, and thus g^ap−bqmod S. The prover 12 and verifier 14 then conduct 608, 610 a zkp_size protocol to demonstrate that the magnitude of ap-bq is large.

[0110] The Multi-Prime Protocol $\mathrm{If}N=\prod _{i=0}^{n-1}{p}_i,$

[0111] for n a known fixed number, there is an extension of this protocol that proves that each of the prime factors p_iare less than N^1/n+ε. In the two prime case, we have φ(N)=N−p−q+1, but in the general case, this becomes more complicated. Provided the p_iare distinct, we get $\begin{array}{cc}\phi \left(N\right)=\prod _{i=0}^{n-1}\left(p_i-1\right)& \text{(Equation 1)}\end{array}$

[0112] Which yields $\begin{array}{cc}\phi \left(N\right)=N+{\left(-1\right)}^n-\sum _{i=0}^{n-1}N/p_i+M& \text{(Equation 2)}\end{array}$

[0113] where M is the sum of all the lower nonconstant terms in the expansion of the polynomial given in Equation 1. M is not necessarily divisible by n, but nonetheless, M can be divided into n nearly equal parts {M₀, . . . M_n−1}.

[0114] The prover 12 and the verifier 14 either jointly agree on a base 2≦r≦N−2 or the verifier 14 selects one and sends it to the prover 12. Then, the prover 12 generates random variables k_ifor each i from 0 to k−1. In one embodiment the random variables k_iare drawn from a uniform distribution. In a further embodiment, the uniform distribution has a minimum of zero and a maximum of N^1/k+ε. The prover 12 then publishes $k=\sum k_i\mathrm{and}{r}^{k_i+N/p_i+M_i}$

[0115] for each i.

[0116] The verifier 14 then confirms that $\prod _{i=0}^{n-1}{r}^{k_i+N/p_i+M_i}=r^{N+{\left(-1\right)}^k}$

[0117] and chooses i at random in 0≦i≦n−1, and transmits i to the prover 12.

[0118] The prover 12 then publishes k_j+N/p_j+M_jfor each j≠i.

[0119] The verifier 14 verifies that the previously given r^k+N/p+Mis correct and that N^(k−1)/k<k_j+N/p_j+M_j<N^(k−1)/k+ε.

[0120] In an illustrative embodiment, n=3, with N=stu. In this embodiment, the prover 12 computes k₁+k₂+k₃=k, and sends r^st−u+kr^su−t+kand r^tu−s+kto the verifier 14. The verifier 14 checks that their product is r^N−1and randomly demands any two of the exponents back, checking that they are less than 2N^⅓+εwhere ε is a small number relative to 1.

[0121] Demonstrating that a Number is Greater than a Minimum Size

[0122] In one embodiment of the invention, a prover 12 wishes to demonstrate that a number is larger than a minimum size. For the purposes of this invention, a protocol that demonstrates the size of a number is referred to herein as a zkp_size protocol.

[0123] In one embodiment, the prover 12 wishes to demonstrate that a discrete logarithm key is large. Specifically, the prover 12 wishes to demonstrate that a quantity m is larger than a quantity p^a. The prover 12 publishes p, a quantity P₁, and a quantity P₂, wherein P₂≡P₁^mmod p. The verifier 14 then generates and publishes a random variable k. In a preferred embodiment, k is in the range p^a/2≦k≦p^a. The prover 12 then randomly generates k1 and k2 such that k1+k2=k and publishes P₁^k1+mand P₁^k2. The verifier 14 then checks that P₁^k1+m×P₁^k2=P₂P₁^kand randomly requests either k1+m or k2. The prover 12 then publishes either k1+m or k2, depending on which was requested. The verifier 14 then checks that the returned value is in accord with the earlier sent value P₁^k1+mor P₁^k2, and that either k1+m>p^aor k2>0.

[0124] In an alternative embodiment, the prover 12 wishes to demonstrate that an elliptic curve discrete logarithm key is large. Specifically, given an elliptic curve E over the field Z/pZ, the prover 12 wishes to demonstrate that a quantity m is larger than a quantity p^aThe prover 12 publishes p, a quantity P₁, and a quantity P₂, wherein P₂=mP₁. The verifier 14 then generates and publishes a random variable k. In a preferred embodiment, k is in the range p^a/2≦k≦p^a. The prover 12 then randomly generates k1 and k2 such that k1+k2=k and publishes (k1+m)P₁and (k2)P₁. The verifier 14 then checks that (k1+m)P₁+(k2)P₁=P₂+kP₁and randomly requests either k1+m or k2. The prover 12 then publishes either k1+m or k2, depending on which was requested. The verifier 14 then checks that the returned value is in accord with the earlier sent value (k1+m) P₁or (k2)P₁, and that either k1+m>p^aor k2>0.

[0125] In another alternative embodiment, the prover 12 demonstrates the bounds of the size of a given g^amod S as described in Damgard, Practical and Provably Secure Release of a Secret and Exchange of Signatures, Advances in Cryptology—Eurocrypt '93 LNCS 765 (1993), 200-217.

[0126] Mao's zkp_product Protocol

[0127] In one embodiment, a prover 12 wishes to demonstrate from public information g^amod S, g^bmod S, and g^cmod S that c=ab. A protocol that demonstrates such a property is referred to herein as a zkp_product protocol. A zkp_product protocol is given in Mao, Verifiable Partial Sharing of the Factors of an Integer, Proceedings of the SAC '98, Queen's University 95-109.

[0128] In this protocol, the prover 12 generates a large prime number P and a prime quantity Q, such that $Q=\frac{\left(P-1\right)}{2}.$

[0129] The prover 12 then selects a base f such that 0≦f<P and publishes f, f^p, f^q, f^N, P, and the bit lengths of p, q, and N.

[0130] The prover 12 then demonstrates that log_f(f^p)mod P=log_fq(f^pq)mod P, and log_f(f^q)mod P=log_fp(f^pq)mod P. In a preferred embodiment, these properties are demonstrated by the prover 12 and verifier 14 performing the Chaum-Pedersen protocol, as described in Chaum, D. and Pedersen, T. P., Wallet databases with observers, Advances in Cryptology—Proceedings of CRYPTO '92 (LNCS 740), pages 89-105, Springer-Verlag, 1993.

[0131] Finally, the prover 12 demonstrates that the bit length of N is greater than or equal to the sum of the bit lengths of p and q, and less than the bit length of Q−2. In a preferred embodiment, these properties are demonstrated by the prover 12 and verifier 14 engaging in a zkp_size protocol.

[0132] Gennero, Micciancio & Rabin Protocol

[0133] In one embodiment, a prover 12 wishes to demonstrate that a quantity N is the product of exactly two prime factors without revealing any other information about these factors. One method of demonstrating that a quantity N is the product of exactly two prime factors is described in R. Gennaro, D. Micciancio, & T. Rabin, An Efficient, Non-Interactive Statistical Zero-Knowledge Proof System for Quasi-Safe Prime Products, preprint.

[0134] In one embodiment, a prover 12 demonstrates that a quantity N is the product of exactly two prime factors in three steps. In the first step, the prover 12 demonstrates that N is square-free, that is, there is no m>1 such that m²divides N. In the second step, the prover 12 demonstrates that N is a prime power product, that is, N has at most two distinct prime factors. In the third and final step, the prover 12 demonstrates that N is a disjoint prime product, that is, N is the product of two prime numbers P and Q such that (P−1) and (Q−1) have no odd common factors.

[0135] In one embodiment, a prover 12 demonstrates that a quantity N is square-free according to the following protocol. The prover 12 publishes N. Next a random number x is determined and published. In one embodiment, the verifier 14 determines x. In an alternate embodiment, the prover 12 and verifier 14 agree on an x. In one embodiment x is chosen from the set of integers from zero to N. The prover 12 then determines M such that M=N⁻¹mod φ (N), where φ (N) is the Euler totient function. The prover 12 next determines and publishes y such that y=x^Mmod N. The verifier 14 then verifies that y^N=x mod N.

[0136] In one embodiment, a prover 12 demonstrates that a quantity N is a prime power product according to the following protocol. The prover 12 publishes N. Next a random number x is determined and published. In one embodiment, the verifier 14 determines x. In an alternate embodiment, the prover 12 and verifier 14 agree on an x. In one embodiment x is chosen from the set of integers from zero to N. The prover 12 then determines and publishes a root r, where r is selected from a group consisting of: {square root over (x)} mod N, −{square root over (x)} mod N, {square root over (2)} mod N, and −{square root over (2+L x)} mod N. The verifier 14 then verifies that r²is congruent to ±x or ±2x modulo N.

[0137] In one embodiment, a prover 12 demonstrates that a quantity N is a disjoint prime product according to the following protocol. The prover 12 publishes N. Next a random number x is determined and published. In one embodiment, the verifier 14 determines x. In an alternate embodiment, the prover 12 and verifier 14 agree on an x. In one embodiment x is chosen from the set of integers from zero to N. The prover 12 then determines M, such that M is the inverse of odd(N−1)⁻¹mod φ(N), where the function odd(N−1) is the greatest odd number that divides (N−1) and the function φ(N) is the Euler totient function. The prover 12 then determines and publishes y, such that y=x^Mmod N. The verifier 14 then verifies that N is not a Fermat prime, and that y^odd(N−1)=x mod N.

[0138] Security Parameters

[0139] The protocols in several embodiments of this invention demonstrate that elements of a key pair are large enough to be considered secure. In general, an element is considered large relative to a security parameter if it is large enough to render factoring attacks infeasible. For example, the ANSI X9.31 and X9.44 standards require the size of factors of p±1 and q±1 to be greater than 2¹⁰⁰. The standards further require the magnitude of the difference between 512-bit factors be greater than 2⁴¹². However, the protocols and systems of this invention do not require a fixed security parameter.

[0140] In one embodiment, the security parameter can be agreed upon by the prover 12 and verifier 14 before executing a protocol according to the parties' desired level of security, as well as the current state of the cryptanalytic art and available computing power. In another embodiment, the verifier 14 sets the security parameter to a desired level for the prover 12 to demonstrate. In a further embodiment, the verifier 14 sets the security parameter based on the amount of liability the verifier 14 assumes for certifying the cryptographic security of a prover 12's key pair.

[0141] Prove_prime Protocol

[0142] In one embodiment, a number p is shown to be prime without revealing p using a protocol designated the prove_prime protocol. In this protocol, a prover 12 generates another prime q such that N=pq is too difficult to factor, and jointly proves that p and q are prime.

[0143] Having generated q, the prover 12 publishes g^pmod S, g^qmod S, and N. In one embodiment, the prover 12 and verifier 14 then jointly execute the Disjoint Prime Protocol disclosed in R. Gennaro, D. Micciancio, & T. Rabin, An Efficient, Non-Interactive Statistical Zero-Knowledge Proof System for Quasi-Safe Prime Products, preprint. In an alternate embodiment, the prover 12 and verifier engage in the two_large_prime_factors protocol taught above for demonstrating that N is the product of two large primes.

[0144] Hardware

[0145] In one embodiment, electronic hardware is employed to perform the protocols described above. In one embodiment, the hardware performing these protocols comprises a number generator. In one embodiment, the number generator is a pseudo-random number generator. In an alternate embodiment, the number generator is a random number generator. In a further embodiment, the random number generator measures entropy for its input. In yet a further embodiment, the random number generator measures the space between a user's keystrokes as a source of entropy. In an alternate embodiment, the random number generator measures radioactive decay as a source of entropy.

[0146] In one embodiment, the hardware performing these protocols further comprises a transmitter for sending information from one device to another device. In a further embodiment, this transmitter is a component of a standard PC network interface card connecting a general purpose computer to a computer network. In a further embodiment, the computer network is an Ethernet network. In an alternate embodiment, the transmitter is a radio frequency transmitter. In yet another alternate embodiment, the transmitter is an infrared transmitter. In yet another alternate embodiment, the transmitter comprises the interface hardware on a smartcard.

[0147] In one embodiment, the hardware performing these protocols further comprises a receiver for a device to obtain information from another device. In a further embodiment, this receiver is a component of a standard PC network interface card connecting a general purpose computer to a computer network. In a further embodiment, the computer network is an Ethernet network. In an alternate embodiment, the receiver is an antenna for receiving radio frequency signals. In yet another alternate embodiment, the receiver is an infrared sensor. In yet another alternate embodiment, the receiver comprises the interface hardware on a smartcard.

[0148] In one embodiment, the hardware performing these protocols further comprises modules for performing mathematical operations. In a further embodiment, the hardware comprises modules for performing basic arithmetic such as addition, subtraction, multiplication, and division. In another further embodiment, the hardware comprises a module for performing modulo arithmetic. In another further embodiment, the hardware comprises a module for performing exponentiation. In one embodiment, these modules are interconnected so that the hardware is capable of performing mathematical functions that employ combinations of these modules.

[0149] In one embodiment, the hardware performing these protocols further comprises modules for comparing quantities. In a further embodiment, the hardware comprises a comparison module for determining whether two quantities are equal. In a further embodiment, the hardware comprises a comparison module for determining whether one quantity is greater than or less than another quantity.

[0150] The protocols described in the above examples are directed to demonstrate the cryptographic strength of RSA key pairs, but they may also be used to demonstrate the cryptographic strength of key pairs in other public key cryptography systems.

[0151] The invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. The foregoing embodiments are therefore to be considered in all respects illustrative rather than limiting on the invention described herein. Scope of the invention is thus indicated by the appended claims rather than by the foregoing description, and all changes which come within the meaning and range of equivalency of the claims are therefore intended to be embraced therein.