Patent Document ID: 20010002486
Application ID: 09737182
Patent Flag: 0

Claim One:
1. A method for implementing RSA 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 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) combining the results of said steps (e) and (h) to produce 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 0) a plurality of times using different values for said multiple of p and for said multiple of q.