Leak-resistant cryptographic method and apparatus
First Claim
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.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention provides a method and apparatus for securing cryptographic devices against attacks involving external monitoring and analysis. A “self-healing” property is introduced, enabling security to be continually re-established following partial compromises. In addition to producing useful cryptographic results, a typical leak-resistant cryptographic operation modifies or updates secret key material in a manner designed to render useless any information about the secrets that may have previously leaked from the system. Exemplary leak-proof and leak-resistant implementations of the invention are shown for symmetric authentication, certified Diffie-Hellman (when either one or both users have certificates), RSA, ElGamal public key decryption, ElGamal digital signing, and the Digital Signature Algorithm.
-
Citations
71 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for implementing RSA for use in a cryptographic system, with resistance to leakage attacks against said cryptographic system, comprising the steps of:
-
(a) obtaining an RSA private key corresponding to an RSA public key, said RSA public key having an RSA modulus n;
(b) storing said private key in a memory in a form whereby a secret parameter of said key is stored as an arithmetic combination of phi(x) and a first at least one key masking parameter, where (i) an operand x in said phi(x) is an exact multiple of at least one factor of said modulus n of said RSA public key; and
(ii) said first key masking parameter is unknown to an attacker of said cryptosystem;
(iii) a representation of said first key masking parameter is stored in said memory;
(iv) phi denotes Euler'"'"'s totient function;
(c) receiving a message;
(d) deriving an RSA input from said message;
(e) performing modular exponentiation to raise said RSA input to a power dependent on said secret parameter, modulo an RSA modulus stored in said memory, to produce an RSA result such that said RSA result raised to the power of the public exponent of said RSA public key, modulo the modulus of said RSA public key, equals said RSA input;
(f) updating said secret parameter in said memory by;
(i) modifing said first key masking parameter to produce a new key masking parameter, where said modification is performed in a manner such that an attacker with partial useful information about said first key masking parameter has less useful information about said new key masking parameter; and
(ii) using said new key masking parameter to update said secret parameter in said memory;
(g) repeating steps (d) through (f) a plurality of times, where the power used for each of said modular exponentiation steps (e) is different. - View Dependent Claims (9, 10)
-
-
11. A method for implementing exponential key exchange for use in a cryptographic system, with resistance to leakage attacks against said cryptographic system, comprising the steps of:
-
(a) obtaining, and storing in a memory, exponential key exchange parameters g and p, and a plurality of secret exponent parameters on which an arithmetic relationship may be computed to produce an exponent x;
(b) using a key update transformation to produce a plurality of updated secret exponent parameters while maintaining said arithmetic relationship thereamong;
(c) receiving a public value y from a party with whom said key exchange is desired;
(d) using said updated secret exponent parameters to perform a cryptographic computation yielding an exponential key exchange result z=y x mod p;
(e) using said result z to secure an electronic communication with said party; and
(f) performing said steps (b), (c), (d), and (e) in a plurality of transactions. - View Dependent Claims (12, 13, 14, 15, 16)
-
-
17. A cryptographic token configured to perform cryptographic operations using a secret key in a secure manner, comprising:
-
(a) an interface configured to receive power from a source external to said token;
(b) a memory containing said secret key;
(c) a processor;
(i) configured to receive said power delivered via said interface;
(ii) configured to perform said processing using said secret key from said memory;
(d) said token having a power consumption characteristic;
(i) that is externally measurable; and
(ii) that varies over time in a manner measurably correlated with said cryptographic operations; and
(e) a source of unpredictable information usable in said cryptographic operations to make determination of said secret key infeasible from external measurements of said power consumption characteristic. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A method for securely managing and using a private key in a computing environment where information about said private key may leak to attackers, comprising the steps of:
-
(a) using a first private key, complementary to a public key, to perform first asymmetric cryptographic operation;
(b) reading at least a portion of said first private key from a memory;
(c) transforming said read portion of said first private key to produce a second private key;
(i) said second private key usable to perform a subsequent asymmetric cryptographic operation in a manner that remains complementary to said public key, and (ii) said transformation enabling said asymmetric cryptographic operations to be performed in a manner such that information leaked during said first asymmetric cryptographic operation does not provide incrementally useful information about said second private key;
(d) obtaining a datum;
(e) using said second private key to perform said subsequent asymmetric cryptographic operation on said datum. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46)
-
-
47. A method for performing cryptographic transactions while protecting a stored cryptographic key against compromise due to leakage attacks, comprising the steps of:
-
(a) retrieving a stored private cryptographic key stored in a memory, said stored key having been used in a previous cryptographic transaction;
(b) using a first cryptographic function to derive from said stored key an updated key, about which useful information about said stored key obtained through monitoring of leaked information is effectively uncorrelated to said updated key;
(c) replacing said stored key in said memory with said updated key;
(d) using an asymmetric cryptographic function, cryptographically processing a datum with said updated key; and
(e) sending said cryptographically processed datum to an external device having a public key corresponding to said stored key. - View Dependent Claims (48, 49, 50, 51, 52, 53, 54, 55)
-
-
56. A method for implementing a private key operation for an asymmetric cryptographic system with resistance to leakage attacks against said cryptographic system, comprising the steps of:
-
(a) encoding a portion of a private key as at least two component parts, such that an arithmetic function of said parts yields said portion;
(b) modifing said component parts to produce updated component parts, but where said arithmetic function of said updated parts still yields said private key portion;
(c) obtaining a message for use in an asymmetric private key cryptographic operation;
(d) separately applying said component parts to said message to produce an intermediate result;
(e) deriving a final result from said intermediate result such that said final result is a valid result of applying said private key to said message;
and (f) repeating steps (b) through (e) a plurality of times. - View Dependent Claims (57, 58, 59, 60, 61, 62, 63)
-
-
64. A method for performing cryptographic transactions in a cryptographic token while protecting a stored cryptographic key against compromise due to leakage attacks, including the steps of:
-
(a) retrieving said stored key from a memory;
(b) cryptographically processing said key, to derive an updated key, by executing a cryptographic update finction that;
(i) prevents partial information about said stored key from revealing useful information about said updated key, and (ii) also prevents partial information about said updated key from revealing useful information about said stored key;
(c) replacing said stored key in said memory with said updated key;
(d) performing a cryptographic operation using said updated key; and
(e) repeating steps (a) through (d) a plurality of times. - View Dependent Claims (65, 66, 67, 68, 69, 70, 71)
-
Specification