Protection of a modular calculation

Patent metadata

Field	Value
Publication number	US-10354063-B2
Application number	US-201715442303-A
Country	US
Kind code	B2
Filing date	Feb 24, 2017
Priority date	Aug 23, 2016
Publication date	Jul 16, 2019
Grant date	Jul 16, 2019

Abstract

A method of protecting a modular calculation on a first number and a second number, executed by an electronic circuit, including the steps of: combining the second number with a third number to obtain a fourth number; executing the modular calculation on the first and fourth numbers, the result being contained in a first register or memory location; initializing a second register or memory location to the value of the first register or to one; and successively, for each bit at state 1 of the third number: if the corresponding bit of the fourth number is at state 1, multiplying the content of the second register or memory location by the inverse of the first number and placing the result in the first register or memory location, if the corresponding bit of the fourth number is at state 0, multiplying the content of the second register or memory location by the first number and placing the result in the first register or memory location.

First claim

The invention claimed is:

1. A method, comprising:
performing, using an electronic circuit, a modular calculation on a first number and a second number, the performing the modular calculation including:
combining the second number with a third number to obtain a fourth number;
executing the modular calculation on the first and fourth numbers, the result being contained in a first memory location;
initializing a second memory location; and
successively, for each bit of the third number at a first state:
in response to a corresponding bit of the fourth number being at a first state of two states, multiplying a content of the second memory location by an inverse of the first number and placing the result in the first memory location; and
in response to the corresponding bit of the fourth number being at a second state of the two states, multiplying the content of the second memory location by the first number and placing the result in the first memory location, wherein a result of the modular calculation on the first number and the second number is based on the content of the second memory location after processing of a last bit of the third number.

2. The method of claim 1 wherein the first memory location is a first register of the electronic circuit and the second memory location is a second register of the electronic circuit.

3. The method of claim 1 , comprising:
in response to a bit of the third number being at a second state, proceeding to the next bit of the third number.

4. The method of claim 1 wherein the result of the modular calculation on the first number and the second number is, after processing of the last bit of the third number, in the second memory location.

5. The method of claim 1 wherein the third number is a random number.

6. The method of claim 1 wherein the second number is a result of a multiplication of a fifth number by an Euler totient function of a modulo of the modular calculation.

7. The method of claim 6 wherein the calculation is a modular exponentiation, the fifth number representing an exponent to be applied to the first number.

8. The method of claim 6 wherein the calculation is a scalar multiplication, the fifth number being a scalar to be multiplied by the first number.

9. The method of claim 1 wherein the calculation is a modular exponentiation, the second number representing an exponent to be applied to the first number.

10. The method of claim 1 wherein the calculation is a scalar multiplication, the second number being a scalar to be multiplied by the first number.

11. The method of claim 1 wherein the initializing the second memory location comprises initializing a value of the second memory location to one of:
a value of the first memory location; and
a value of one.

12. A device, comprising:
one or more memories; and
processing circuitry, which, in operation, performs a modular calculation on a first number and a second number, the performing the modular calculation including:
combining the second number with a third number to obtain a fourth number;
executing the modular calculation on the first and fourth numbers, storing the result in a first memory location;
initializing a second memory location; and
successively, for each bit of the third number at a first state:
in response to a corresponding bit of the fourth number being at a first state of two states, multiplying a content of the second memory location by an inverse of the first number and storing the result in the first memory location; and
in response to the corresponding bit of the fourth number being at a second state of the two states, multiplying the content of the second memory location by the first number and storing the result in the first memory location, wherein a result of the modular calculation on the first number and the second number is based on the content of the second memory location after processing of a last bit of the third number.

13. The device of claim 12 wherein the first memory location is a first register of the one or more memories and the second memory location is a second register of the one or more memories.

14. The device of claim 12 wherein the result of the modular calculation on the first number and the second number is, after processing of the last bit of the third number, in the second memory location.

15. The device of claim 12 wherein the third number is a random number.

16. The device of claim 12 wherein the second number is a result of a multiplication of a fifth number by an Euler totient function of a modulo of the modular calculation.

17. The device of claim 16 wherein the calculation is a modular exponentiation, the fifth number representing an exponent to be applied to the first number.

18. The device of claim 16 wherein the calculation is a scalar multiplication, the fifth number being a scalar to be multiplied by the first number.

19. The device of claim 12 wherein the calculation is a modular exponentiation, the second number representing an exponent to be applied to the first number.

20. The device of claim 12 wherein the calculation is a scalar multiplication, the second number being a scalar to be multiplied by the first number.

21. The device of claim 12 wherein the initializing the second memory location comprises initializing a value of the second memory location to one of:
a value of the first memory location; and
a value of one.

22. A system, comprising:
one or more processing cores, which in operation, process digital data; and
cryptographic circuitry, coupled to the one or more processing cores, wherein the cryptographic circuitry, in operation, performs a modular calculation on a first number and a second number, the performing the modular calculation including:
combining the second number with a third number, obtaining a fourth number;
executing the modular calculation on the first and fourth numbers, storing a result in a first memory location;
initializing a second memory location; and
successively, for each bit of the third number at a first state:
in response to a corresponding bit of the fourth number being at a first state of two states, multiplying a content of the second memory location by an inverse of the first number and storing the result in the first memory location; and
in response to the corresponding bit of the fourth number being at a second state, multiplying the content of the second memory location by the first number and storing the result in the first memory location, wherein a result of the modular calculation on the first number and the second number is based on the content of the second memory location after processing of a last bit of the third number.

23. The system of claim 22 wherein the first memory location is a first register and the second memory location is a second register.

24. The system of claim 22 wherein the modular calculation is one of a modular exponentiation and a scalar multiplication.

25. The system of claim 22 wherein the initializing the second memory location comprises initializing a value of the second memory location to one of:
a value of the first memory location; and
a value of one.

26. The system of claim 22 wherein the one or more processing cores, in operation, process transaction data.

27. A non-transitory computer-readable medium having contents which cause one or more processing devices to

Assignees

• St Microelectronics Rousset

Inventors

• Diop Ibrahima
• Liardet Pierre-Yvan
• Linge Yanis

Classifications

• G06F7/523

  Multiplying only · CPC title

• G06F7/72

  using residue arithmetic · CPC title

• G06F2207/7242

  Exponent masking, i.e. key masking, e.g. A**(e+r) mod n; (k+r).P · CPC title

• G06F21/52 Primary

  during program execution, e.g. stack integrity {; Preventing unwanted data erasure; Buffer overflow} · CPC title

• G06F2221/032

  Protect output to user by software means · CPC title