Method of securely implementing a cryptography algorithm of the RSA type, and a corresponding component

Abstract

A method for the secure application of a cryptographic algorithm of the RSA type in an electronic component obtains the value of a public exponent e from a given set of probable values, without a priori knowledge of that value. Having determined the value for the public exponent e, the application of countermeasures using the value of e, to block error attacks and side channel attacks, particularly of the DPA and SPA type, are carried out on the application of a private operation of the cryptographic algorithm.

1. A method of securely implementing a public-key cryptography algorithm in a microprocessor-based system, the public key being composed of an integer n that is a product of two large prime numbers p and q, and of a public exponent e, said algorithm also including a private key, said method determining a set E comprising a predetermined number of prime numbers e i  that can correspond to the value of the public exponent e, and comprising the following steps:
 a) computing a value 
 
     
       
         
           
             Φ 
             = 
             
               
                 ∏ 
                 
                   ei 
                   ∈ 
                   E 
                 
               
               ⁢ 
               ei 
             
           
         
       
     
     such that Φ/e i  is less than Φ(n) for any e i  belonging to E, where Φ is the Euler totient function;
 b) applying the value Φ to a predetermined computation involving, as a modular product, only the modular product of Φ multiplied by said private key of the algorithm; 
 c) for each e i , testing whether the result of said predetermined computation is equal to a value Φ/ i : 
 if so, then attributing the value e i  to e, and storing e; 
 otherwise, indicating that the computations of the cryptography algorithm using the value e cannot be performed; and 
 d) performing a cryptographic operation on data using the stored value for e. 
 
   
   
     2. A method according to  claim 1 , wherein the cryptography algorithm is based on an RSA-type algorithm in standard mode. 
   
   
     3. A method according to  claim 2 , wherein the predetermined computation of step b) comprises computing a value C:
 C=Φ·d modulo Φ(n), where d is the corresponding private key of the RSA algorithm such that e·d=1 modulo Φ(n) and Φ is the Euler totient function. 
 
   
   
     4. A method according to  claim 2 , wherein the predetermined computation of step b) comprises computing a value C:
 C=Φ·d modulo Φ(n), where d is the corresponding private key of the RSA algorithm such that e·d=1 modulo Φ(n), with Φ being the Carmichael function. 
 
   
   
     5. A method according to  claim 4  and in which a value e i  has been attributed to e, wherein the computations using the value ecomprise:
 choosing a random integer r; 
 computing a value d* such that d*=d+r·(e·d−1); and 
 implementing a private operation of the algorithm in which a value x is obtained from a value y by applying the relationship x=y d*  modulo n. 
 
   
   
     6. A method according to  claim 1 , wherein the cryptography algorithm is based on an RSA-type algorithm in CRT mode. 
   
   
     7. A method according to  claim 6 , wherein the predetermined computation of step b) comprises computing a value C:
 C=Φ·d p  modulo (p−1), where d p  is the corresponding private key of the RSA algorithm such that e·d p =1 modulo (p−1). 
 
   
   
     8. A method according to  claim 6 , wherein the predetermined computation of step b) comprises computing a value C:
 C=Φ·d q  modulo (q−1), where d q  is the corresponding private key of the RSA algorithm such that e·d q 32 1 modulo (q−1). 
 
   
   
     9. A method according to  claim 6 , wherein the predetermined computation of step b) comprises computing two values C 1  and C 2  such that:
 C 1 =Φ·d p  modulo (p−1), where d p  is the corresponding private key of the RSA algorithm such that e·d p =1 modulo (p−1); 
 C 2 =Φ·d q  modulo (q−1), where d q  is the corresponding private key of the RSA algorithm such that e·dq=1 modulo (q−1); 
 and wherein the test step c) comprises, for each e i , testing whether C 1  and/or C 2  is equal to the value Φ/e i : 
 if so, then attributing the value e i  to e and storing e for subsequent use in computations of said cryptography algorithm; 
 otherwise, indicating that the computations of said cryptography algorithm using the value e cannot be performed. 
 
   
   
     10. A method according to  claim 3  and in which a value e i  has been attributed to e, wherein the computations using the value e comprise:
 choosing a random integer r; 
 computing a value d* such that d*=d+r·(e·d−1); and 
 implementing a private operation of the algorithm in which a value x is obtained from a value y by applying the relationship x=y d*  modulo n. 
 
   
   
     11. A method according to  claim 2 , in which a value e i  has been attributed to e, and further including the step, after a private operation of the algorithm, of obtaining a value x from a value y, and wherein the computations using the value e comprise checking whether x e =y modulo n. 
   
   
     12. A method according to  claim 5 , in which a value e i  has been attributed to e, and further including the step, after a private operation of the algorithm, of obtaining a value x from a value y, and wherein the computations using the value e comprise checking whether x e =y modulo p and whether x e =y modulo q. 
   
   
     13. A method according to  claim 1 , wherein the set E comprises at least the following e i  values: 3, 17, 2 16 +1. 
   
   
     14. An electronic component comprising means for
 a) computing a value Φ=Π ei
   ei ∈ E 
 
 
     such that Φ/e i  is less than Φ(n) for any e i  belonging to E, where Φ is the Euler totient function;
 b) applying the value Φ to a predetermined computation involving, as a modular product, only the modular product of Φ multiplied by a private key of the algorithm; 
 c) for each e i , testing whether the result of said predetermined computation is equal to a value Φ/e i : 
 if so, then attributing the value e i  to e, and storing e; 
 otherwise, indicating that the computations of the cryptography algorithm using the value e cannot be performed; and 
 d) performing a cryptographic operation on data using the stored value for e. 
 
   
   
     15. A smart card including the electronic component of  claim 14 . 
   
   
     16. A method according to  claim 1 , wherein said cryptographic operation comprises at least one of encrypting data, decrypting data, signing a message and authenticating a message.