Method for determining a modular inverse and associated cryptographic processing device

Patent metadata

Field	Value
Publication number	US-11029922-B2
Application number	US-201916426824-A
Country	US
Kind code	B2
Filing date	May 30, 2019
Priority date	Jun 8, 2018
Publication date	Jun 8, 2021
Grant date	Jun 8, 2021

Abstract

In a method for determining the modular inverse of a number, successive iterations are applied to two pairs each including a first variable and a second variable, such that at the end of each iteration and for each pair, the product of the second variable and of the number is equal to the first variable modulo a given module. Each iteration includes at least one division by two of the first variable of a first pair or of a second pair, 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 include a step of storing the result of the combination in the first variable of a pair determined randomly from among the first pair and the second pair. An associated cryptographic processing device is also described.

First claim

The invention claimed is:

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

Assignees

• Idemia France

Inventors

• Chabrier Thomas
• Piret Gilles

Classifications

• H04L9/004 Primary

  for fault attacks · CPC title

• G06F7/727

  Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 (G06F7/728 takes precedence) · CPC title

• G06F7/723

  Modular exponentiation (G06F7/724, G06F7/727, G06F7/728 take precedence) · CPC title

• H04L9/302

  involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes · CPC title

• G06F7/721 Primary

  Modular inversion, reciprocal or quotient calculation (G06F7/724, G06F7/727, G06F7/728 take precedence) · CPC title