Protection of a modular exponentiation calculation

Patent metadata

Field	Value
Publication number	US-10025559-B2
Application number	US-201715442322-A
Country	US
Kind code	B2
Filing date	Feb 24, 2017
Priority date	Aug 23, 2016
Publication date	Jul 17, 2018
Grant date	Jul 17, 2018

Abstract

A method of protecting a modular exponentiation calculation on a first number and an exponent, modulo a first modulo, executed by an electronic circuit using a first register or memory location and a second register or memory location, successively including, for each bit of the exponent: generating a random number; performing a modular multiplication of the content of the first register or memory location by that of the second register or memory location, and placing the result in one of the first and second registers or memory locations selected according to the state of the bit of the exponent; performing a modular squaring of the content of one of the first and second registers or memory locations selected according to the state of the exponent, and placing the result in this selected register or memory location, the multiplication and squaring operations being performed modulo the product of the first modulo by said random number.

First claim

The invention claimed is:

1. A method, comprising:
performing, using an electronic circuit, a modular exponentiation calculation on a first number and an exponent, modulo a first modulo by, for each bit of the exponent:
generating a random number;
performing a modular multiplication of content of a first memory location by content of a second memory location, and placing a result in one of the first and second memory locations selected according to a state of the bit of the exponent; and
performing a modular squaring of the content of one of the first and second memory locations selected according to the state of the exponent, and placing the result in this selected register or memory location,
the multiplication and squaring operations being performed modulo a product of the first modulo and said random number.

2. The method of claim 1 wherein a result of the modular exponentiation calculation is contained in said first memory location.

3. The method of claim 1 , comprising:
initializing the first memory location to value 1; and
initializing the second memory location to a value of the first number.

4. 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.

5. The method of claim 1 , comprising processing a transaction based on a result of the modular exponentiation calculation.

6. A device, comprising:
one or more memories; and
processing circuitry, which, in operation, performs a modular exponentiation calculation on a first number and an exponent, modulo a first modulo by, for each bit of the exponent:
generating a random number;
performing a modular multiplication of content of a first memory location by content of a second memory location, and placing a result in one of the first and second memory locations selected according to a state of the bit of the exponent; and
performing a modular squaring of the content of one of the first and second memory locations selected according to the state of the exponent, and placing the result in this selected register or memory location, the multiplication and squaring being performed modulo a product of the first modulo and said random number.

7. The device of claim 6 wherein a result of the modular exponentiation calculation is contained in said first memory location.

8. The device of claim 6 wherein the processing circuitry, in operation:
initializes the first memory location to value 1; and
initializes the second memory location to a value of the first number.

9. The device of claim 6 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.

10. The device of claim 6 , comprising one or more processing cores, which, in operation, process transactions based on a result of the modular exponentiation calculation.

11. 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 exponentiation calculation on a first number and an exponent, modulo a first modulo by, for each bit of the exponent:
generating a random number;
performing a modular multiplication of content of a first memory location by content of a second memory location, and placing a result in one of the first and second memory locations selected according to a state of the bit of the exponent; and
performing a modular squaring of the content of one of the first and second memory locations selected according to the state of the exponent, and placing the result in this selected register or memory location, the multiplication and squaring being performed modulo a product of the first modulo and said random number.

12. The system of claim 11 wherein a result of the modular exponentiation calculation is contained in said first memory location.

13. The system of claim 11 wherein the cryptographic circuitry, in operation:
initializes the first memory location to value 1; and
initializes the second memory location to a value of the first number.

14. The system of claim 11 wherein the first memory location is a first register of the cryptographic circuitry and the second memory location is a second register of the cryptographic circuitry.

15. The system of claim 11 wherein the one or more processing cores, in operation, process a transaction based on a result of the modular exponentiation calculation.

16. A non-transitory computer-readable medium having contents which cause one or more processing devices to perform a method, the method comprising:
performing a modular exponentiation calculation on a first number and an exponent, modulo a first modulo by, for each bit of the exponent:
generating a random number;
performing a modular multiplication of content of a first memory location by content of a second memory location, and placing a result in one of the first and second memory locations selected according to a state of the bit of the exponent; and
performing a modular squaring of the content of one of the first and second memory locations selected according to the state of the exponent, and placing the result in this selected register or memory location, the multiplication and squaring operations being performed modulo a product of the first modulo and said random number.

17. The non-transitory computer-readable medium of claim 16 wherein a result of the modular exponentiation calculation is contained in said first memory location.

18. The non-transitory computer-readable medium of claim 16 , wherein the method comprises:
initializing the first memory location to value 1; and
initializing the second memory location to a value of the first number.

19. The non-transitory computer-readable medium of claim 16 , wherein the method comprises processing a transaction based on a result of the modular exponentiation calculation.

Assignees

• St Microelectronics Rousset

Inventors

• Diop Ibrahima
• Linge Yanis
• Liardet Pierre-Yvan

Classifications

• G06F7/723 Primary

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

• G06F21/72

  in cryptographic circuits · CPC title

• G06F7/722

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

• G06F7/58

  Random or pseudo-random number generators · CPC title

• G06F2207/7247

  Modulo masking, e.g. A**e mod (n*r) · CPC title