Leak-resistant cryptographic method and apparatus

  • US 6,304,658 B1
  • Filed: 12/31/1998
  • Issued: 10/16/2001
  • Est. Priority Date: 01/02/1998
  • Status: Expired due to Term
First Claim
Patent Images

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) with a multiple of p

    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

    1
    mod q.

View all claims
    ×
    ×

    Thank you for your feedback

    ×
    ×