Method of protecting cryptographic operations from side channel attacks

• US 20050152539A1
• Filed: 01/12/2004
• Published: 07/14/2005
• Est. Priority Date: 01/12/2004
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Brickell, Ernie F.
• Application Number:
  US10/756,596
• Publication Number:
  US 20050152539A1
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: G06F 2207/7238 Operand masking, i.e. message blinding, e.g. (A+r)**e mod n; k.(P+R)
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441

Abstract

Deterring side channel attacks on cryptographic computations using an exponent value e and a modulus value n to determine a result value may be accomplished by picking a first value, picking a second value, computing a third value as a product of the first and second values mod n, computing a first intermediate value as the first value to the exponent e mod n, computing a second intermediate value as the second value to the exponent e mod n, and computing a result value equal to the third value to the exponent e mod n as the product of the first intermediate value and the second intermediate value mod n. The result value y^e mod n may be determined in this manner without using a modular inverse operation.

Claims

1. A method of deterring side channel attacks on cryptographic computations using an exponent value e and a modulus value n to determine a result value comprising:

picking a first value;

picking a second value;

computing a third value as a product of the first and second values mod n;

computing a first intermediate value as the first value to the exponent e mod n;

computing a second intermediate value as the second value to the exponent e mod n; and

computing a result value equal to the third value to the exponent e mod n as the product of the first intermediate value and the second intermediate value mod n.

2. The method of claim 1, further comprising picking the first value pseudo-randomly with a substantially uniform distribution.

3. The method of claim 1, further comprising picking the second value pseudo-randomly with a substantially uniform distribution.

4. The method of claim 1, wherein the exponent e and the modulus n are publicly known values, and the third value is secret.

5. An article comprising:

a storage medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor, the instructions provide for deterring side channel attacks on cryptographic computations using an exponent value e and a modulus value n to determine a result value by picking a first value, picking a second value, computing a third value as a product of the first and second values mod n, computing a first intermediate value as the first value to the exponent e mod n, computing a second intermediate value as the second value to the exponent e mod n, and computing a result value equal to the third value to the exponent e mod n as the product of the first intermediate value and the second intermediate value mod n.

6. The article of claim 5, further comprising instructions for picking the first value pseudo-randomly with a substantially uniform distribution.

7. The article of claim 5, further comprising instructions for picking the second value pseudo-randomly with a substantially uniform distribution.

8. The article of claim 5, wherein the exponent e and the modulus n are publicly known values, and the third value is secret.

9. A method of deterring side channel attacks on cryptographic computations using an exponent value e and a modulus value n to determine a result value comprising:

picking a first value;

picking a second value;

computing a first intermediate value as the first value to the exponent e mod n;

computing a second intermediate value as the second value to the exponent e mod n; and

computing a result value as the product of the first intermediate value and the second intermediate value mod n.

10. The method of claim 9, further comprising picking the first value pseudo-randomly with a substantially uniform distribution.

11. The method of claim 9, further comprising picking the second value pseudo-randomly with a substantially uniform distribution.

12. An article comprising:

a storage medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor, the instructions provide for deterring side channel attacks on cryptographic computations using an exponent value e and a modulus value n to determine a result value by picking a first value, picking a second value, computing a first intermediate value as the first value to the exponent e mod n, computing a second intermediate value as the second value to the exponent e mod n, and computing a result value as the product of the first intermediate value and the second intermediate value mod n.

13. The article of claim 12, further comprising instructions for picking the first value pseudo-randomly with a substantially uniform distribution.

14. The article of claim 12, further comprising instructions for picking the second value pseudo-randomly with a substantially uniform distribution.