Method of obscuring cryptographic computations
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
216 Citations
15 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. - View Dependent Claims (2, 3, 4, 5, 6)
- 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
-
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. - View Dependent Claims (8, 9)
-
-
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.
- View Dependent Claims (11, 12)
-
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. - View Dependent Claims (14, 15)
- 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
Specification