Authenticating or signature method with reduced computations

Abstract

Authentication and signature process with reduced number of calculations. The process involves a first entity called the “prover”, which possesses a public key v and a secret key s, these keys verify the relation v=s −t (mod n), where n is an integer called modulus and t is a parameter, and a second entity called a “verifier”, which knows the public key v . This process implies exchange of information following a “zero-knowledge protocol” between the verifier and the prover and cryptographic calculations on this information, some calculations being carried out “modulo n ”. The process of the invention is characterised by the fact that the modulus n is specific to the prover that communicates this modulus to the verifier.

1. An authentication process involving a first device, which possesses a public key v and a secret key s, the public and secret keys being related by an operation modulo n, where n is an integer, the modulus n being specific to the first device, and a second device, which knows the public key v, the first and second entities devices being provided with means to exchange zero-knowledge information and to carry out cryptographic calculations on the zero-knowledge information, calculations being carried out modulo n wherein in the process the modulo n operation is of v=s −t  (mod n), t being a parameter and in that the modulo n calculations are performed according to the “Chinese remainders” method and in that the modulus n is the product of two primes of similar size. 
     
     
       2. A process according to  claim 1 , wherein the information exchanges are of zero-knowledge and wherein the cryptographic calculations are completed as follows:
 the first device selects are at least one integer r at random ranging between 1 and n−1 and calculates at least one parameter x equal to r t  (mod n), then at least one number c that is at least one function of the at least one of a parameter and a message and sends the at least one number c to the second device; 
 the second device receives the at least number c, selects at least one number e at random, and sends the at least one number e to the first device; 
 the first device receives the at least one number e, carries out at least one calculation using the at least one number e and the secret key s, the result of the at least one calculation yielding at least one answer y, and sends the at least one answer y to the second device; 
 the second device receives the at least one answer y, carries out one calculation using the public key v and the modulus n, and checks with a modulo n operation that the result of the one calculation is coherent with the received at least one number c. 
 
     
     
       3. A process according to  claim 2 , wherein a size of the number n, expressed in number of bits, is less than 1,000. 
     
     
       4. A process according to  claim 3 , wherein a size of the number n is between 700 and 800. 
     
     
       5. A message signature process configured for a device provided with a public key v and a secret key s, the public and private keys being related by a modulo n calculation, where n is an integer, which is specific to the device, the process utilizing means configured to calculate at least one number c that is a function of a message M to be signed, configured to calculate at least one number y that is a function of the secret key s, and configured to transmit the numbers y and c that are the signature of the message and the message M, wherein the modulo n operation is v=s−t (mod n), t being a parameter wherein the modulo n calculations are performed according to the “Chinese remainders” method and in that the modulus n is the product of two primes of similar size. 
     
     
       6. A message signature process according to  claim 5 , wherein the device selects an integer r at random between 1 and n−1, calculates a parameter x equal to rt (mod n), calculates at least one number e that is a function of parameter x and the message M to be signed, calculates the at least one number y using its secret key s, said at least one number y being a function of numbers r and e, and transmits the numbers c and y as the signature. 
     
     
       7. A method of authentication, the method comprising:
 generating and sending an opening c by a prover device, wherein generating an opening c comprises:
 calculating modulo n, wherein n is an integer specific to the prover device, and is a product of prime numbers; 
 selecting randomly a number r between 1 and n−1; 
 calculating a parameter x equal to r t  (mod n), where t is a parameter; and 
 calculating the opening c based at least in part on the parameter x; 
   receiving a question e by the prover device, in response to the sending of the opening c;   generating and sending a result y by the prover device to enable the prover device to be authenticated based on the result y and a public key v associated with a secret key s possessed by the prover device, wherein generating a result y is based at least in part on the question e and the secret key s, and comprises calculating modulo n;   wherein calculating modulo n comprises using a “Chinese remainders” method.   
     
     
       8. A prover device for an authentication process, the prover device comprising:
 a storage device configured to store a secret key s possessed by the prover device; and   a processor coupled to the storage device, and configured to generate an opening c, and cause the prover device to send the opening c, wherein generation of an opening c comprises:
 calculation of modulo n, wherein n is an integer specific to the prover device, and is a product of prime numbers; 
 random selection of a number r between 1 and n−1; 
 calculation of a parameter x equal to r t  (mod n), where t is a parameter; and 
 calculation of the opening c based at least in part on the parameter x; 
   control the prover device in receiving a question e, in response to the sending of the opening c;   generate and cause the prover device to send a result y to enable the prover device to be authenticated based on the result y and a public key v associated with the secret key s, wherein generation of a result y is based at least in part on the question e and the secret key s, and comprises calculation of modulo n;   wherein calculation of modulo n comprises using a “Chinese remainders” method, and at least two prime factors of n.   
     
     
       9. An article of manufacture comprising a non-transitory computer readable medium, and instructions stored in the non-transitory computer readable medium, wherein the instructions if executed on a prover device causes the prover device to perform an authentication method, the method comprising:
 generating and sending an opening c by the prover device, wherein generating an opening c comprises:
 calculating modulo n, wherein n is an integer specific to the prover device, and is a product of prime numbers; 
 selecting randomly a number r between 1 and n−1; 
 calculating a parameter x equal to r t  (mod n), where t is a parameter; and 
 calculating the opening c based at least in part on the parameter x; 
   receiving a question e by the prover device, in response to the sending of the opening c;   generating and sending a result y by the prover device to enable the prover device to be authenticated based on the result y and a public key v associated with a secret key s possessed by the prover device, wherein generating a result y is based at least in part on the question e and the secret key s, and comprises calculating modulo n;   wherein calculating modulo n comprises using a “Chinese remainders” method, and at least two prime factors of n.   
     
     
       10. The method of claim 7, wherein generating a result y comprises calculating y equal to rs e  (mod n). 
     
     
       11. The prover device of claim 8, wherein the processor is configured to calculate y by calculating rs e  (mod n). 
     
     
       12. The article of claim 9, wherein generating a result y comprises calculating y equal to rs e  (mod n).