PROTECTION OF A MODULAR EXPONENTIATION CALCULATION PERFORMED BY AN INTEGRATED CIRCUIT

• US 20100208883A1
• Filed: 06/14/2006
• Published: 08/19/2010
• 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
• Granted Patent: US 8,135,129 B2
• Time in Patent Office: Days
• 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

The invention concerns a method and a circuit for protecting a numerical quantity (d) contained in an integrated circuit (1) on a first number of bits (n), in a modular exponentiation computing of a data (M) by said numerical quantity, which consists in: selecting at least one second number (j) included between the unit and said first number minus two; dividing said numerical quantity into at least two parts, a first part (d(j−1, 0)) comprising, from the bit of rank null, a number of bits equal to said second number, a second part (d(n−1, j)) comprising the remaining bits; for each part of the quantity, computing a first modular exponentiation (23, 33) of said data by the part concerned and a second modular exponentiation (36, 34) 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 (35) 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 at least a second number ranging between unity and the first number minus two;

dividing 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, a second portion comprising the remaining bits;

for each portion of the quantity, calculating a first modular exponentiation of the data by the concerned portion and a second modular exponentiation of the result of the first one by number 2 raised to the power of the rank of the first bit of the concerned portion; and

calculating the product of the results of the second 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:

$M^d=\underset{x=1}{\overset{k}{\prod <br><br>}}<br><br>\left({\left(M^{d_x}\right)}^{2^{j_x}}\right)<br><br><br><br>\mathrm{mod}<br><br><br><br>P<br><br><br><br>\mathrm{or}<br><br><br><br>M^d=\underset{x=1}{\overset{k}{\prod <br><br>}}<br><br>\left({\left(M^{2^{j_x}}\right)}^{d_x}\right)<br><br><br><br>\mathrm{mod}<br><br><br><br>P,<br><br>\mathrm{with}<br><br><br><br>d_x=\underset{i=j_x}{\overset{j_x+1}{\sum <br><br>}}<br><br>d_i<br><br>2^i,$

where x designates the rank of number j_x in said k increasing numbers, with j₀=0 and j_k=n−

1 where n represents said first number, d_x designates the portion of rank x of said quantity, P designates the modulo, and d_i designates the bit of rank i of said quantity.

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.