Patent ID: 6304658
Filing Date: 2001-10-16
Classification: G06F,G06Q,H04L

Abstract:
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) with a multiple of p.sup.-1 mod q 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 (j) a plurality of times using different values for said multiple of p and for said multiple of q and for said multiple of p.sup.-1 mod q.