Protection of a modular exponentiation calculation performed by an integrated circuit

• US 8,135,129 B2
• Filed: 06/14/2006
• Issued: 03/13/2012
• Est. Priority Date: 06/16/2005
• Status: Active Grant

• Current Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Inventors: Teglia, Yannick, Liardet, Pierre-Yvan, Pomet, Alain
• Primary Examiner(s): Orgad, Edan
• Assistant Examiner(s): JACKSON, JENISE E
• Application Number:
  US11/917,347
• Publication Number:
  US 20100208883A1
• Time in Patent Office: 2,099 Days
• Field of Search: 380/28, 380/277, 726/22, 726/26, 726/36, 713/171, 713/172, 713/193, 713/194
• US Class Current: 380/28
• CPC Class Codes: G06F 2207/7252 of operation order, e.g. starting to treat the exponent at a random place, or in a randomly chosen direction
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]

Abstract

A method and a circuit for protecting a numerical quantity contained in an integrated circuit on a first number of bits, in a modular exponentiation computing of a data by the numerical quantity, including: selecting at least one second number included between the unit and said first number minus two; dividing the numerical quantity into at least two parts, a first part including, from the bit of rank null, a number of bits equal to the second number, a second part including the remaining bits; for each part of the quantity, computing a first modular exponentiation of said data by the part concerned and a second modular exponentiation of the result of the first by the FIG. 2 exponentiated to the power of the rank of the first bit of the part concerned; and computing the product of the results of the first and second modular exponentiations.

Claims

1. A method for protecting a digital quantity contained in an integrated circuit over a first number of bits, in a calculation of modular exponentiation of data by said digital quantity, comprising:

selecting, by the integrated circuit, at least a second number ranging between unity and the first number minus two;

dividing, by the integrated circuit, the digital quantity into at least two portions, a first portion comprising, from the bit of rank zero, a number of bits equal to the second number, and a second portion comprising the remaining bits;

calculating, by the integrated circuit, a first modular exponentiation of the data by the first portion of the digital quantity to provide a first result;

calculating, by the integrated circuit, a first modular exponentiation of the data by the second portion of the digital quantity to provide a second result;

calculating, by the integrated circuit, a second modular exponentiation of the second result by two raised to the power of the second number to provide a third result; and

calculating, by the integrated circuit., the product of the first and third results of the modular exponentiations.

2. The method of claim 1, wherein the second number is selected randomly.

3. The method of claim 2, wherein a new random selection is performed on each new execution of the algorithm.

4. The method of claim 1, wherein the two modular exponentiations are inverted.

5. The method of claim 1, wherein the second portion is divided into at least two portions based on at least a third number, preferably selected randomly, between the second number plus one and the first number minus two, the steps of calculation of the first and second modular exponentiations and of the product of the results of the second modular exponentiations being applied to each of the portions.

6. The method of claim 1, wherein k increasing numbers j_x are selected between unity and the first number minus two, the modular exponentiation calculation of the data noted M by the quantity noted d being obtained by the application of the following formula:

7. The method of claim 1, implemented using an algorithm selected from among the DSA, RSA, and Diffie-Hellman algorithms.

8. An integrated circuit comprising at least a central processing unit, a memory, and an input/output circuit, comprising circuitry for implementing the method of claim 1.

9. A smart card, comprising the integrated circuit of claim 8.

10. A method for protecting a digital quantity contained in an integrated circuit, the digital quantity having a first number of bits, in a modular exponentiation of data by the digital quantity, comprising:

selecting, by the integrated circuit, a second number in a range between unity and the first number minus two;

partitioning, by the integrated circuit, the digital quantity into a first portion comprising the second number of bits of the digital quantity and a second portion comprising remaining bits of the digital quantity;

calculating, by the integrated circuit, a first modular exponentiation of the data by the first portion of the digital quantity to provide a first result;

calculating, by the integrated circuit, a first modular exponentiation of the data by the second portion of the digital quantity to provide a second result;

calculating, by the integrated circuit, a second modular exponentiation of the second result by two raised to the power of the second number to provide a third result; and

calculating, by the integrated circuit, a product of the first and third results to provide a modular exponentiation of the data by the digital quantity.

11. The method of claim 10, wherein the second number is selected randomly.

12. The method of claim 10, wherein a new second number is selected randomly on each new execution of the modular exponentiation.

13. The method of claim 10, wherein the first and second modular exponentiations are inverted.

14. The method of claim 10, further comprising calculating a second modular exponentiation of the first result by two raised to the power of zero.

15. The method of claim 10, wherein the digital quantity is partitioned into three or more portions, a first modular exponentiation of the data by each of the portions of the digital quantity is calculated, and the product of each of the results is calculated.

16. The method of claim 10, wherein k increasing numbers j_x are selected between unity and the first number minus two, the modular exponentiation calculation of the data M by the quantity d being obtained by the application of the following formula:

17. The method of claim 10, wherein the first portion includes the bits of rank zero to j−

1 of the digital quantity and the second portion contains the bits of rank j to n−

1 of the digital quantity, wherein n is the first number and j is the second number.

18. An integrated circuit comprising:

a central processing unit;

a memory; and

an input/output circuit, wherein the memory is encoded with instructions that, when executed by the central processing unit, perform a method for protecting a digital quantity contained in the integrated circuit, the digital quantity having a first number of bits, in a modular exponentiation of data by the digital quantity, the method comprising;

selecting, by the integrated circuit, a second number in a range between unity and the first number minus two;

partitioning, by the integrated circuit, the digital quantity into a first portion comprising the second number of bits of the digital quantity and a second portion comprising remaining bits of the digital quantity;

calculating, by the integrated circuit, a first modular exponentiation of the data by the first portion of the digital quantity to provide a first result;

calculating, by the integrated circuit, a first modular exponentiation of the data by the second portion of the digital quantity to provide a second result;

calculating, by the integrated circuit, a second modular exponentiation of the second result by two raised to the power of the second number to provide a third result; and

calculating, by the integrated circuit, a product of the first and third results to provide a modular exponentiation of the data by the digital quantity.