Protection of an iterative calculation

Patent metadata

Field	Value
Publication number	US-11456853-B2
Application number	US-202016810434-A
Country	US
Kind code	B2
Filing date	Mar 5, 2020
Priority date	Mar 29, 2019
Publication date	Sep 27, 2022
Grant date	Sep 27, 2022

Abstract

Cryptographic circuitry, in operation, performs a calculation on a first number and a second number. The performing of the calculation is protected by breaking the second number into a plurality of third numbers, a sum of values of the third numbers being equal to a value of the second number. The calculation is performed bit by bit for each rank of the third numbers. Functional circuitry, coupled to the cryptographic circuitry, uses a result of the calculation.

First claim

The invention claimed is:

1. A method, comprising:
executing, using an electronic circuit, a calculation on a first number and a second number; and
protecting the executing of the calculating, the protecting including:
breaking the second number into a plurality of third numbers, a sum of values of the third numbers being equal to a value of the second number; and
performing the calculation bit by bit for each rank of the third numbers.

2. The method of claim 1 , wherein the calculation is a modular exponentiation of the first number by the second number.

3. The method of claim 1 , wherein the calculation is a multiplication of a point of an elliptic curve by a scalar.

4. The method of claim 1 , wherein the ranks of the bits of the third numbers are scanned by increasing order.

5. The method of claim 1 , wherein the bits of a same rank of the third numbers are processed in a same order, from one rank to the other.

6. The method of claim 1 , wherein the bits of a same rank of the third numbers are processed in a random order.

7. The method of claim 1 , wherein the processing order of the bits of a same rank of the third numbers results from a permutation.

8. The method of claim 1 , wherein processing performed on the bits of each rank comprises:
if the considered bit is equal to 1, performing a first operation with an operator on the contents of a first register and of a second register, and then placing the result in the first register; and
if the considered bit is equal to 0, keeping the contents of the two registers unchanged.

9. The method of claim 8 , wherein the first register contains the result of the calculation.

10. The method of claim 8 , wherein said operator is multiplication.

11. The method of claim 8 , wherein said operator is addition.

12. The method of claim 8 , wherein the first register is initialized with the neutral element of said operator.

13. The method of claim 8 , wherein the second register is initialized with the first number.

14. The method of claim 8 , wherein, after having processed all the bits of same rank of the third numbers, a second operation is performed with said operator on the content of the second register, the result of the second operation being placed in the second register.

15. The method of claim 8 , wherein the operation(s) are performed modulo a fourth number.

16. A device, comprising:
one or more memories;
cryptographic circuitry coupled to the one or more memories, wherein the cryptographic circuitry, in operation, performs a calculation on a first number and a second number, the performing the calculation including:
breaking the second number into a plurality of third numbers, a sum of values of the third numbers being equal to a value of the second number; and
performing the calculation bit by bit for each rank of the third numbers.

17. The device of claim 16 , wherein the calculation is a modular exponentiation of the first number by the second number.

18. The device of claim 16 , wherein the calculation is a multiplication of a point of an elliptic curve by a scalar.

19. The device of claim 16 , wherein the ranks of the bits of the third numbers are scanned by increasing order.

20. The device of claim 16 , wherein the bits of a same rank of the third numbers are processed in a same order, from one rank to the other.

21. The device of claim 16 , wherein the bits of a same rank of the third numbers are processed in a random order.

22. The device of claim 16 , wherein the processing order of the bits of a same rank of the third numbers results from a permutation.

23. The device of claim 16 , wherein the one or more memories comprises a first register and a second register and the processing performed on the bits of each rank comprises:
if the considered bit is equal to 1, performing a first operation with an operator on the contents of a first register and of a second register, and then placing the result in the first register; and
if the considered bit is equal to 0, keeping the contents of the two registers unchanged.

24. The device of claim 23 wherein the first register contains the result of the calculation.

25. The device of claim 23 , wherein said operator is multiplication.

26. The device of claim 23 , wherein said operator is addition.

27. The device of claim 23 , wherein, after having processed all the bits of same rank of the third numbers, the cryptographic circuitry, in operation, performs a second operation with said operator on the content of the second register, the result of the second operation being placed in the second register.

28. The device of claim 23 wherein the cryptographic circuitry, in operation, performs the operation modulo a fourth number.

29. A system, comprising:
cryptographic circuitry, which, in operation, performs a calculation on a first number and a second number, the performing the calculation including:
breaking the second number into a plurality of third numbers, a sum of values of the third numbers being equal to a value of the second number; and
performing the calculation bit by bit for each rank of the third numbers; and

functional circuitry, coupled to the cryptographic circuitry, wherein the functional circuitry, in operation, uses a result of the calculation.

30. The system of claim 29 , wherein the calculation is a modular exponentiation of the first number by the second number.

31. The system of claim 29 , wherein the calculation is a multiplication of a point of an elliptic curve by a scalar.

Assignees

• St Microelectronics Rousset

Inventors

• Diop Ibrahima
• Linge Yanis

Classifications

• G06F7/723 Primary

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

• G06F2207/7257

  Random modification not requiring correction · CPC title

• G06F7/72

  using residue arithmetic · CPC title

• G06F7/525

  in serial-serial fashion, i.e. both operands being entered serially (G06F7/533 takes precedence) · CPC title

• G06F7/504

  in bit-serial fashion, i.e. having a single digit-handling circuit treating all denominations after each other · CPC title