Efficient modular addition resistant to side channel attacks

Patent metadata

Field	Value
Publication number	US-9544131-B2
Application number	US-201414568556-A
Country	US
Kind code	B2
Filing date	Dec 12, 2014
Priority date	Dec 13, 2013
Publication date	Jan 10, 2017
Grant date	Jan 10, 2017

Abstract

A cryptographic device performs modular addition between a first integer value x and a second integer value y in a processor by: obtaining a first masked input {circumflex over (x)}, a second masked input ŷ, a first mask r x and a second mask r y , the first masked input {circumflex over (x)} resulting from the first integer value x masked by the first mask r x and the second masked input ŷ resulting from the second integer value y masked by the second mask r y ; computing a first iteration masked carry value ĉ 1 , using the first masked input {circumflex over (x)}, the second masked input ŷ, the first mask r x , the second mask r y and a carry mask value λ; recursively updating the masked carry value ĉ i to obtain a final masked carry value ĉ k−1 , wherein the masked carry value is updated using the first masked input {circumflex over (x)}, the second masked input ŷ, the first mask r x , the second mask r y , and the carry mask value λ; combining the first masked input {circumflex over (x)} and the second masked input ŷ and the final masked value ĉ k−1 to obtain an intermediate value; combining the intermediate value with the carry mask value to obtain a masked result; and outputting the masked result and a combination of the first mask r x and the second mask r y . It is preferred that the combinations use XOR.

First claim

The invention claimed is:

1. A method of performing modular addition between a first integer value x and a second integer value y, the method comprising, in a hardware processor:
obtaining a first masked input {circumflex over (x)}, a second masked input ŷ, a first mask r x and a second mask r y , the first masked input {circumflex over (x)} resulting from the first integer value x masked by the first mask r x and the second masked input ŷ resulting from the second integer value y masked by the second mask r y ;
computing a first iteration carry value c 1 , using the first masked input {circumflex over (x)}, the second masked input ŷ, the first mask r x , and the second mask r y ;
recursively updating intermediate carry values c i , to obtain a final carry value c k−1 , wherein an intermediate carry value is updated using the first masked input {circumflex over (x)}, the second masked input ŷ, the first mask r x and the second mask r y ;
combining the first masked input {circumflex over (x)} and the second masked input ŷ and the final carry value c k−1 to obtain a masked result; and
outputting the masked result.

2. The method of claim 1 , wherein the first iteration carry value, the intermediate carry values and the final carry value are masked and:
the first iteration carry value c 1 is computed using also a carry mask value λ; and
the intermediate carry values c i are updated using also the carry mask value λ; and

wherein the masked result is obtained by:
combining the first masked input {circumflex over (x)} and the second masked input ŷ and the final masked carry value to obtain an intermediate value; and
combining the intermediate value with the carry mask value to obtain a masked result.

3. The method of claim 2 , wherein the intermediate value and the masked result are obtained using XOR between the combined values.

4. The method of claim 2 , further comprising outputting a combination of the first mask r x and the second mask r y .

5. The method of claim 4 , wherein the combination of the first mask r x and the second mask r y is obtained using XOR.

6. The method of claim 1 , wherein the modular addition is used to subtract the second integer value y from the first integer value x, the method further comprising:
between the obtaining and the computing, setting the first masked input {circumflex over (x)} to the bitwise complementation of the first masked input {circumflex over (x)}; and
between the combining and the outputting, setting the masked result to the bitwise complementation of the masked result.

7. A device for performing modular addition between a first integer value x and a second integer value y, the device comprising a hardware processor configured to:
obtain a first masked input {circumflex over (x)}, a second masked input ŷ, a first mask r x and a second mask r y , the first masked input {circumflex over (x)} resulting from the first integer value x masked by the first mask r x and the second masked input y resulting from the second integer value y masked by the second mask r y ;
compute a first iteration carry value c 1l , using the first masked input {circumflex over (x)}, the second masked input ŷ, the first mask r x , and the second mask r y ;
recursively update intermediate carry values c i , to obtain a final carry value c k−1 wherein an intermediate carry value is updated using the first masked input {circumflex over (x)}, the second masked input ŷ, the first mask r x and the second mask r y ;
combine the first masked input {circumflex over (x)} and the second masked input ŷ and the final carry value c k−1 to obtain a masked result; and
output the masked result.

8. The device of claim 7 , wherein the first iteration carry value, the intermediate carry values and the final carry value are masked and the hardware processor is configured to:
compute the first iteration carry value c 1 using also a carry mask value λ; and
update the intermediate carry values c i using also the carry mask value λ; and

wherein the hardware processor is configured to combine the first masked input {circumflex over (x)} and the second masked input ŷ and the final masked carry value to obtain an intermediate value, and to combine the intermediate value with the carry mask value to obtain the masked result.

9. The device of claim 8 , wherein the intermediate value and the hardware processor is configured to use XOR between the combined values to obtain the masked result.

10. The device of claim 8 , wherein the hardware processor is further configured to output a combination of the first mask r x and the second mask r y .

11. The device of claim 7 , wherein the hardware processor is configured to use the modular addition to subtract the second integer value y from the first integer value x, the hardware processor being further configured to:
set the first masked input {circumflex over (x)} to the bitwise complementation of the first masked input {circumflex over (x)}; and
set the masked result to the bitwise complementation of the masked result.

Assignees

• Thomson Licensing

Inventors

• Karroumi Mohamed
• Richard Benjamin
• Joye Marc

Classifications

• H04L9/0625

  with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI · CPC title

• G06F7/727

  Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 (G06F7/728 takes precedence) · CPC title

• G06F2207/7238

  Operand masking, i.e. message blinding, e.g. (A+r)**e mod n; k.(P+R) · CPC title

• G06F7/72

  using residue arithmetic · CPC title

• H04L9/003 Primary

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title