Method for determining a modular inverse and associated cryptographic processing device

1. A method of implementing a cryptographic algorithm using a modular inverse of a number, the method comprising:

storing cryptographic data including the number at an electronic entity;

applying, at the electronic entity, successive iterations to two pairs each comprising a first variable and a second variable such that at an end of each iteration and for each pair, a product of the second variable and said number is equal to the first variable modulo a given module, the two pairs comprising a first pair and a second pair, each of the iterations including at least one division of the first variable of the first pair or of the second pair by two, or a combination of the first variable of the first pair and of the first variable of the second pair by addition or subtraction, at least some of the iterations including a combination by addition or subtraction comprising modifying the first variable of a pair determined randomly from among the first pair and the second pair by a result of the combination;

after the iterations are performed, determining the modular inverse of the number using the second variable of the first pair or the second variable of the second pair;

implementing the cryptographic algorithm using the determined modular inverse; and

one of (i) transmitting a result of the implemented cryptographic algorithm to another electronic entity, and (ii) storing the result of the implemented cryptographic algorithm in a memory of the electronic entity.

2. The method according to claim 1 , wherein, when the number of iterations performed is greater than a threshold, each of the iterations including a combination by addition or subtraction comprises modifying one of the first variable of the first pair and the first variable of the second pair having the greater absolute value by the result of the combination.

3. The method according to claim 2 , further comprising determining the threshold by random draw.

4. The method according to claim 1 , wherein, for at least one of the iterations comprising the combination by addition or subtraction, the combination is made by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign.

5. The method according to claim 1 , wherein each of the iterations comprising a division of the first variable of a given pair by two comprises, when the second variable of said given pair is even, dividing the second variable of said given pair by two, and

when the second variable of said given pair is odd,

determining a sum of the second variable of said given pair and of the module, and

dividing said sum by two.

6. The method according to claim 1 , further comprising modifying an additional variable by a random value,

wherein, in at least one iteration, when the additional variable is even, performing a division of the additional variable by two, and

when the additional variable is odd,

determining a sum of the additional variable and the module, and

performing a division of said sum by two.

7. The method according to claim 1 , wherein each of the iterations including the combination by addition or subtraction comprises a corresponding combination of the second variable of the first pair and of the second variable of the second pair.

8. The cryptographic processing device according to claim 1 , wherein the number is one of (i) a public exponent of the public key of an asymmetric encryption scheme, (ii) a secret factor of an RSA algorithm module, (iii), a scalar number, and (iv) a multiplicative mask.

9. The method according to claim 2 , wherein, for at least one of the iterations comprising the combination by addition or subtraction, the combination is made by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign.

10. The method according to claim 2 , wherein each of the iterations comprising a division of the first variable of a given pair by two comprises, when the second variable of said given pair is even, dividing the second variable of said given pair by two, and

when the second variable of said given pair is odd,

determining a sum of the second variable of said given pair and of the module, and

dividing said sum by two.

11. The method according to claim 2 , further comprising modifying an additional variable by a random value,

wherein, in at least one iteration, when the additional variable is even, performing a division of the additional variable by two, and

when the additional variable is odd,

determining a sum of the additional variable and the module, and

performing a division of said sum by two.

12. The method according to claim 2 , wherein each of the iterations including the combination by addition or subtraction comprises a corresponding combination of the second variable of the first pair and of the second variable of the second pair.

13. The method according to claim 3 , wherein, for at least one of the iterations comprising the combination by addition or subtraction, the combination is made by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign.

14. The method according to claim 3 , wherein each of the iterations comprising a division of the first variable of a given pair by two comprises, when the second variable of said given pair is even, dividing the second variable of said given pair by two, and

when the second variable of said given pair is odd,

determining a sum of the second variable of said given pair and of the module, and

dividing said sum by two.

15. The method according to claim 3 , further comprising modifying an additional variable by a random value,

wherein, in at least one iteration, when the additional variable is even, performing a division of the additional variable by two, and

when the additional variable is odd,

determining a sum of the additional variable and the module, and

performing a division of said sum by two.

16. The method according to claim 3 , wherein each of the iterations including the combination by addition or subtraction comprises a corresponding combination of the second variable of the first pair and of the second variable of the second pair.

17. A cryptographic processing device, comprising:

a memory configured to store cryptographic data including a number; and

at least one processor configured to:

determine a modular inverse of the number stored in the memory by applying successive iterations to two pairs each comprising a first variable and a second variable such that at an end of each iteration and for each pair, a product of the second variable and said number is equal to the first variable modulo a given module, the two pairs comprising a first pair and a second pair, the at least one processor being configured to activate, at each of the iterations, at least one division block for dividing by two the first variable of the first pair or of the second pair, or a combination block for combining the first variable of the first pair and the first variable of the second pair by addition or subtraction, the at least one processor being configured, for at least some of the iterations, to modify the first variable of a pair determined randomly from among the first pair and the second pair by a result of the combination,

after the iterations are performed, determine the modular inverse of the number using the second variable of the first pair or the second variable of the second pair,

implement the cryptographic algorithm using the determined modular inverse, and

one of (i) transmit a result of the implemented cryptographic algorithm to another cryptographic processing device, and (ii) store the result of the implemented cryptographic algorithm in the memory.

18. The cryptographic processing device according to claim 17 , wherein the at least one processor is configured to, when the number of iterations performed is greater than a threshold, modify one of the first variable of the first pair and the first variable of the second pair having the greater absolute value by the result of the combination.

19. The cryptographic processing device according to claim 18 , wherein the combination block performs the combination by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign.

20. The cryptographic processing device according to claim 17 , wherein the combination block performs the combination by addition when the first variable of the first pair and the first variable of the second pair have opposite signs, and by subtraction when the first variable of the first pair and the first variable of the second pair have the same sign.