Patent ID: 8290149

Claim:
A method of 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 comprising: picking a random number between one and a modulus minus one, the modulus comprising a product of two prime numbers; determining an intermediate value based at least in part on the random number, the modulus, and a message; determining a first obscuring factor and a second obscuring factor using the message, the random number, the modulus, and the inverse of the random number; for each bit i in the exponent, setting the intermediate value to the intermediate value multiplied by the intermediate value mod the modulus, determining a third obscuring factor using the i'th bit of the exponent and the first and second obscuring factors, and setting the intermediate value to the intermediate value multiplied by the third obscuring factor mod the modulus; and setting a new message to the intermediate value multiplied by the second obscuring factor mod the modulus, wherein performing the modular exponentiation is to comprise replacing a conditional multiplication operation, during decryption processing, with an unconditional multiplication operation based on the first, second, and third obscuring factors without performing any multiplication by ones or zeros to be detected.