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

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 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) choosing a value e i from the values of the set E;

b) if Φ(p)=Φ(q), where Φ(n), Φ(p), and Φ(q) are functions giving the number of bits encoding respectively the number n, the number p, and the number q, testing, in a processor of the microprocessor-based system, whether the chosen e i value satisfies the relationship:

(1 −e i ·d )modulo n<e i ·2 (Φ(n)/2)+1

or said relationship as simplified:

(− e i ·d )modulo n<e i ·2 (Φ(n)/2)+1

c) if the test relationship applied in the preceding step is satisfied, defining e=e i , and storing e in a memory of the microprocessor-based system;

otherwise, reiterating the preceding steps while choosing another value for e i from the set E until an e i value can be attributed to e and, if no e i value can be attributed to e, then indicating that the computations of said cryptography algorithm using the value of e cannot be performed; and

d) performing a cryptographic operation on data using the stored value for e.

2. The method of securely implementing a public-key cryptography algorithm according to claim 1 , wherein step b is performed in the following manner when Φ(p)≠Φ(q), i.e. when p and q are unbalanced, testing whether the chosen e i value satisfies the following relationship:

(1 −e i ·d )modulo n<e i ·2 g+1

or said relationship as simplified:

(− e i ·d )modulo n<e i ·2 g+1

with g=max Φ(p), Φ(q)), if Φ(p) and Φ(q) are known, or, otherwise, with g=Φ(n)/2+t, where t designates the imbalance factor or a limit on that factor.

3. The method according to claim 2 , wherein, for all values of i, e i ≦2 16 +1, step b) is replaced by another test step comprising:

b) if Φ(p)=Φ(q), testing whether the chosen e i value satisfies the relationship:

(1 −e i ·d )modulo n<e i ·2 (Φ(n)/2)+17

or said relationship as simplified:

(− e i ·d )modulo n<e i ·2 (Φ(n)/2)+17

where Φ(p), Φ(q), and Φ(n) are functions giving the numbers of bits respectively encoding the number p, the number q, and the number n;

otherwise, when p and q are unbalanced, testing whether the chosen e i value satisfies the following relationship:

(1 −e i ·d )modulo n<e i ·2 g+17

or said relationship as simplified:

(− e i ·d )modulo n<e i ·2 g+17

with g=max Φ(p), Φ(q)), if Φ(p) and Φ(q) are known, or, otherwise, with g=Φ(n)/2+t, where t designates the imbalance factor or a limit on that factor.

4. The method according to claim 2 , wherein step b) is replaced with another test step comprising:

testing whether the chosen e i value satisfies the relationship whereby:

a predetermined number of the first most significant bits of (1−e i ·d) modulo n are zero;

or said relationship as simplified whereby:

said predetermined number of the first most significant bits of (−e i ·d) modulo n are zero.

5. The method according to claim 4 , wherein the test is performed on the first 128 most significant bits.

6. The method according to claim 1 , wherein the cryptography algorithm is based on an RSA-type algorithm in standard mode.

7. The method according to claim 1 wherein, when an e i value has been attributed to e, the computations using the value e comprise:

choosing a random integer r;

computing a value d* such that d*=d+r·(e·d−1);

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.

8. The method according to claim 1 wherein, when an e i value has been attributed to e, after a private operation of the algorithm, a value x is obtained from a value y and the computations using the value e comprise checking whether x e =y modulo n.

9. The method according to claim 1 , wherein the set E comprises at least the following e i values: 3, 17, 2 16 +1.

10. The method according to claim 9 , wherein the preferred choice of the values e i from the values of the set E is made in the following order: 2 16 +1, 3, 17.

11. The method according to claim 1 , wherein, for all values of i, e i ≦2 16 +1, step b) is replaced by another test step comprising:

b) if Φ(p)=Φ(q), testing whether the chosen e i value satisfies the relationship:

(1 −e i ·d )modulo n<e i ·2 (Φ(n)/2)+17

or said relationship as simplified:

(− e i ·d )modulo n<e i ·2 (Φ(n)/2)+17

where Φ(p), Φ(q), and Φ(n) are functions giving the numbers of bits respectively encoding the number p, the number q, and the number n;

otherwise, when p and q are unbalanced, testing whether the chosen e i value satisfies the following relationship:

(1 −e i ·d )modulo n<e i ·2 g+17

or said relationship as simplified:

(− e i ·d )modulo n<e i ·2 g+17

with g=max Φ(p), Φ(q)), if Φ(p) and Φ(q) are known, or, otherwise, with g=Φ(n)/2+t, where t designates the imbalance factor or a limit on that factor.

12. The method according to claim 1 , wherein step b) is replaced with another test step comprising:

testing whether the chosen e i value satisfies the relationship whereby:

a predetermined number of the first most significant bits of (1−e i ·d) modulo n are zero;

or said relationship as simplified whereby:

said predetermined number of the first most significant bits of (−e i ·d) modulo n are zero.

13. The 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.

14. An electronic component comprising a processor that is configured to execute the following steps:

a) choosing a value e i from the values of the set E;

b) if Φ(p)=Φ(q), where Φ(n), Φ(p), and Φ(q) are functions giving the number of bits encoding respectively the number n, the number p, and the number q, where n is an integer that is a product of two large prime numbers p and q, testing, in the processor of the electronic component, whether the chosen e i value satisfies the relationship:

(1 −e i ·d )modulo n<e i ·2 (Φ(n)/2)+1

or said relationship as simplified:

(− e i ·d )modulo n<e i ·2 (Φ(n)/2)+1

c) if the test relationship applied in the preceding step is satisfied, defining e=e i , and storing e in a memory of the electronic component;

otherwise, reiterating the preceding steps while choosing another value for e i from the set E until an e i value can be attributed to e and, if no e i value can be attributed to e, then indicating that the computations of said cryptography algorithm using the value of 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 .