Patent ID: 7792287

Claim:
A computer-implemented method for implementing a RSA cryptographic operation with the Chinese remainder theorem for use in a cryptographic system, with resistance to leakage attacks against said cryptographic system, comprising the steps of: (a) obtaining at the cryptographic system a representation of an RSA private key corresponding to an RSA public key, said private key characterized by secret factors p and q; (b) storing said representation of said private key in a memory; (c) obtaining a message for use in an RSA cryptographic operation; (d) computing a first modulus, corresponding to a multiple of p, where the value of said multiple of p and the value of said multiple of p divided by p are both unknown to an attacker of said cryptographic system; (e) reducing said message modulo said first modulus; (f) performing modular exponentiation on the result of step (e); (g) computing a second modulus, corresponding to a multiple of q, where the value of said multiple of q and the value of said multiple of q divided by q are both unknown to an attacker of said cryptographic system; (h) reducing said message modulo said second modulus; (i) performing modular exponentiation on the result of step (h); (j) using the results of said steps (f) and (i) and a multiplicand to compute a result which, if operated on with an RSA public key operation using said RSA public key, yields said message; and (k) repeating steps (c) through (j) a plurality of times using different values for said multiple of p and for said multiple of q and for said multiplicand to produce differences in power consumed by the cryptographic system among said RSA private key operations: (i) said different value for said multiple of p being updated from, and replacing, the preceding value for said multiple of p; and (ii) said different value of said multiple of q being updated from, and replacing, the preceding value of said multiple of q; thereby increasing the difficulty of determining said RSA private key by collecting measurements of the power consumed by the cryptographic system performing the RSA cryptographic operation with the Chinese remainder theorem.