Method of obscuring cryptographic computations

• US 7,739,521 B2
• Filed: 09/18/2003
• Issued: 06/15/2010
• Est. Priority Date: 09/18/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Brickell, Ernie F.
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): KANAAN, SIMON P
• Application Number:
  US10/666,632
• Publication Number:
  US 20050084098A1
• Time in Patent Office: 2,462 Days
• Field of Search: 713/194, 713/176, 380/1, 380/30
• US Class Current: 713/194
• CPC Class Codes: G06F 2207/7233 Masking, e.g. (A**e)+r mod n
• CPC Class Codes: G06F 2207/7261 Uniform execution, e.g. avoiding jumps, or using formulae with the same power profile
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence

Abstract

Obscuring cryptographic computations may be accomplished by performing modular exponentiation of an exponent in a cryptographic computation such that memory accesses are independent of the exponent bit pattern, thereby deterring timing attacks.

Claims

1. A method comprising:

performing modular exponentiation in a cryptographic computation such that memory accesses are independent of the numerical value of the exponent, wherein said performing modular exponentiation is to comprise replacing a conditional multiplication operation with an unconditional multiplication operation and the unconditional multiplication operation is to be based on an obscuring factor; and

determining the obscuring factor for each bit of the exponent by adding one to a result of multiplying a quantity by a selected bit of the exponent, the quantity comprising a message minus one.

2. The method of claim 1, wherein the exponent comprises at least one of a signature exponent and a decryption exponent in a RSA cryptographic system, and the cryptographic computation is at least one of signature and decryption.

3. The method of claim 2, wherein the cryptographic computation comprises c^d mod n, wherein c comprises a ciphertext message, d comprises the decryption exponent, and n comprises a modulus that is a product of two prime numbers.

4. The method of claim 1, wherein the modular exponentiation is performed as part of a Diffie-Hellman key exchange process.

5. The method of claim 1, wherein the modular exponentiation is performed as part of a Digital Signature Algorithm (DSA) process.

6. The method of claim 1, further comprising applying a window method as part of performing the modular exponentiation and retrieving pre-computed powers from one to 2^v of a message from a memory, where v is the size of a window into the exponent'"'"'s bits.

7. A method comprising:

setting an intermediate value to a message; and

for each bit i in the exponent, setting the intermediate value to the intermediate value multiplied by the intermediate value mod a modulus, wherein the modulus comprises a product of two prime numbers, determining a current obscuring factor using the i'"'"'th bit of the exponent, and setting the intermediate value to the intermediate value multiplied by the current obscuring factor mod the modulus, wherein determining the current obscuring factor comprises determining the current obscuring factor by adding one to a result of multiplying a quantity by a selected bit of the exponent, the quantity comprising the message minus one.

8. The method of claim 7, wherein the exponent comprises at least one of a signature exponent and a decryption exponent in a RSA cryptographic system, and the cryptographic computation is at least one of signature and decryption.

9. The method of claim 7, further comprising applying a window method as part of performing the modular exponentiation and retrieving pre-computed powers from one to 2^v of the message from a memory, where v is the size of a window into the exponent'"'"'s bits.

10. An article comprising:

a non-transitory storage medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor, the instructions provide for obscuring cryptographic computations by performing modular exponentiation of an exponent in a cryptographic computation such that memory accesses are independent of the numerical value of the exponent, wherein a current obscuring factor is to be determined by adding one to a result of multiplying a quantity by a selected bit of the exponent, the quantity to comprise a message minus one.

11. The article of claim 10, wherein performing modular exponentiation comprises replacing a conditional multiplication operation with an unconditional multiplication operation.

12. The article of claim 10, further comprising instructions for applying a window method as part of performing the modular exponentiation and retrieving pre-computed powers from one to 2^v of a message from a memory, where v is the size of a window into the exponent'"'"'s bits.

13. An article comprising:

a non-transitory storage medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor, the instructions provide for obscuring cryptographic computations by performing modular exponentiation of an exponent in a cryptographic computation such that memory accesses are independent of the exponent bit pattern, the instructions causing setting an intermediate value to a message; and

for each bit i in the exponent, setting the intermediate value to the intermediate value multiplied by the intermediate value mod a modulus, wherein the modulus comprises a product of two prime numbers, determining a current obscuring factor using the i'"'"'th bit of the exponent, and setting the intermediate value to the intermediate value multiplied by the current obscuring factor mod the modulus, wherein determining the current obscuring factor is to comprise adding one to a result of multiplying a quantity by a selected bit of the exponent, the quantity to comprise the message minus one.

14. The article of claim 13, wherein the exponent comprises at least one of a signature exponent and a decryption exponent in a RSA cryptographic system, and the cryptographic computation is at least one of signature and decryption.

15. The article of claim 13, further comprising instructions for applying a window method as part of performing the modular exponentiation and retrieving pre-computed powers from one to 2^v of a message from a memory, where v is the size of a window into the exponent'"'"'s bits.