Leak-resistant cryptographic method and apparatus
DCFirst 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) 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.
1 Assignment
Litigations
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
54 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) 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 Dependent Claims (2, 3, 4, 5, 6)
(i) said step (b) includes storing an exponent dp of said RSA private key in said memory as a plurality of parameters;
(ii) an arithmetic function of at least one of said plurality of parameters is congruent to dp, modulo (p−
1);
(iii) none of said parameters comprising said stored dp is equal to dp;
(iv) an exponent used in said step (f) is at least one of said parameters;
(v) at least one of said parameters in said memory changes with said repetitions of said steps (c) through (j).
-
-
3. The method of claim 2 where said plurality of parameters includes a first parameter equal to said dp plus a multiple of phi(p), and also includes a second parameter equal to a multiple of phi(p), where phi denotes Euler'"'"'s totient function.
-
4. The method of claim 1 where the value of said multiple of p divided by p is equal to the value of said multiple of q divided by q.
-
5. The method of claim 1 where said multiple of p and said multiple of q used in said steps (c) through (j) are updated and modified in said memory after said step (b).
-
6. The method of claim 1 performed in a smart card.
-
7. 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; and
(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) modifying said stored secret parameter to produce a new secret parameter and a new masking parameter where;
(i) said new secret parameter is derived from at least said stored masking parameter and said stored secret parameter, and (ii) said modification is performed in a manner such that an attacker with partial useful information about said stored secret parameter has less useful information about said new secret parameter;
(g) updating said memory with representations of said new secret parameter and said new masking parameter; and
(h) repeating said steps (d) through (g) a plurality of times, where the power used for each of said modular exponentiation steps (e) is different. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. 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{circumflex over ( )}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 (14, 15, 16, 17, 18)
-
-
19. 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 (20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
30. 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 (31, 32, 33, 34, 35, 36, 37, 38)
-
-
39. 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) modifying 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 (40, 41, 42, 43, 44, 45, 46)
-
-
47. 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 function 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 (48, 49, 50, 51, 52, 53, 54)
(i) explicitly erasing a region of said memory containing said stored key; and
(ii) strong said updated key in said region of memory.
-
-
54. The method of claim 47 performed within a smart card.
Specification