Leak-resistant cryptographic method and apparatus

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.

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.

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.

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.

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.

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.