Secure modular exponentiation with leak minimization for smartcards and other cryptosystems

A method of computing a modular exponentiation involving a digital message, as part of a private key operation in an asymetric cryptosystems involving a sequence of processor instructions, comprising the steps of:

• (a) obtaining a base representative of at least a portion of said message, said base to be cryptographically processed using an asymmetric cryptographic protocol involving a private key including a secret exponent and an associated modulus;
• (b) storing in a memory one or more values representing predefined positive integer powers of said base;
• (c) storing in an accumulator a value representing said base raised to an integer power;
• (d) using a portion of said secret exponent, deriving an index referencing one of said previously stored values, by executing a sequence of processor instructions having a form independent of said exponent;
• (e) multiplying, modulo said modulus, (i) a value in said accumulator and (ii) said referenced value, by executing a sequence of processor instructions having a form independent of a value of said index;
• (f) storing the result of said step (e) in said accumulator;
• (g) repeating said steps (d) through (g) until said accumulator contains a representation of said base raised to said exponent;
• thereby cryptographically processing said base in a manner resistant to detection of said exponent by monitoring of said processor instructions.

A method of computing a modular exponentiation involving a digital message, as part of a private key operation in an asymmetric cryptosystems involving a sequence of processor instructions, comprising the steps of:

• (a) obtaining a base representative of at least a portion of said message, said base to be cryptographically processed using an asymmetric cryptographic protocol involving a private key including a secret exponent and an associated modulus;
• (b) storing in a memory one or more values representing predefined positive integer powers of said base;
• (c) storing in an accumulator a representation of said base raised to an integer power;
• (d) using a portion of said secret exponent, deriving an index specifying a multiplicand, where said multiplicand is a positive value of said base raised to an integer power, by executing a sequence of processor instructions having a form independent of said exponent;
• (e) multiplying, modulo said modulus, (i) a value in said accumulator and (ii) said specified multiplicand, by executing a sequence of processor instructions having a form independent of a value of said index;
• (f) storing the result of said step (e) in said accumulator;
• (g) repeating said steps (d) through (g) until said accumulator contains a representation of said base raised to said exponent;
• thereby cryptographically processing said base in a manner resistant to detection of said exponent by monitoring of said processor instructions.

A computer-readable medium containing program logic code that, when executed, cryptographically processes a message using an asymmetric cryptographic protocol involving a private key including a secret exponent, in a manner resistant to external detection of the secret exponent, comprising:

• (a) program logic code that, when executed, obtains a digital quantity representative of at least a portion of said message, said digital quantity to be cryptographically processed using an asymmetric cryptographic protocol involving a private key including a modulus and a secret exponent;
• (b) program logic code that, when executed, transforms said exponent to an expanded representation thereof, said expanded representation including a sequence of symbols, each said symbol representing a modular multiplication;
• (c) program logic code that, when executed, loads an accumulator with a positive integer power of said digital quantity;
• (d) program logic code that, when executed, for each said symbol in at least a portion of said expanded representation:
• (i) multiplies said value in said accumulator by a positive integer power of said digital quantity, said integer power being indicated by said symbol, and
• (ii) updates said accumulator with the result of said step (i),
• (iii) where the sequence of microprocessor instructions performed by said logic code is independent of the value of said symbol;
• for cryptographically processing said digital quantity in a manner resistant to external detection of said secret exponent.

A computer-readable medium containing program logic code that, when executed, cryptographically processes a message using an asymmetric cryptographic protocol involving a private key including a secret exponent, in a manner resistant to external detection of the secret exponent, comprising:

• (a) program logic code that, when executed, obtains a base representative of at least a portion of said message, said base to be cryptographically processed using an asymmetric cryptographic protocol involving a private key including a secret exponent and an associated modulus;
• (b) program logic code that, when executed, stores in a memory one or more values representing predefined positive integer powers of said base;
• (c) program logic code that, when executed, stores in an accumulator a value representing said base raised to an integer power;
• (d) program logic code that, when executed, uses a portion of said secret exponent, deriving an index referencing one of said previously stored values, by executing a sequence of processor instructions having a form independent of said exponent;
• (e) program logic code that, when executed, multiplies, modulo said modulus, (i) a value in said accumulator and (ii) said referenced value, by executing a sequence of processor instructions having a form independent of a value of said index;
• (f) program logic code that, when executed, stores the result of said step (e) in said accumulator;
• (g) program logic code that, when executed, repeats said steps (d) through (g) until said accumulator contains a representation of said base raised to said exponent;
• for cryptographically producing said base in a manner resistant to detection of said exponent by monitoring of said processor instructions.

A computer apparatus containing logic instructions that, when performed, cryptographically process a message using an asymmetric cryptographic protocol involving a private key including a secret exponent, in a manner resistant to external detection of the secret exponent, comprising:

• (a) instructions for obtaining a digital quantity representative of at least a portion of said message, said digital quantity to be cryptographically processed using an asymmetric cryptographic protocol involving a private key including a modulus and a secret exponent;
• (b) instructions for transforming said exponent to an expanded representation thereof, said expanded representation including a sequence of symbols, each said symbol representing a modular multiplication;
• (c) instructions for loading an accumulator with a positive integer power of said digital quantity;
• (d) instructions for operating on each said symbol in at least a portion of said expanded representation as follows:
• (i) multiplying said value in said accumulator by a positive integer power of said digital quantity, said integer power being indicated by said symbol, and
• (ii) updating said accumulator with the result of said step (i),
• (iii) said instructions having a form independent of the value of said symbol;
• for cryptographically processing said digital quantity in a manner resistant to external detection of said secret exponent.

A computer apparatus containing logic instructions that, when performed, cryptographically process a message using an asymmetric cryptographic protocol involving a private key including a secret exponent, in a manner resistant to external detection of the secret exponent, comprising:

• (a) instructions for obtaining a base representative of at least a portion of said message, said base to be cryptographically processed using an asymmetric cryptographic protocol involving a private key including a secret exponent and an associated modulus;
• (b) instructions for storing in a memory one or more values representing predefined positive integer powers of said base;
• (c) instructions for storing in an accumulator a representation of said base raised to an integer power;
• (d) instructions for using a portion of said secret exponent to derive an index referencing one of said previously stored values of said base raised to an integer power, by executing a sequence of processor instructions having a form independent of said exponent;
• (e) instructions for multiplying modulo said modulus (i) a value in said accumulator and (ii) said referenced value, by executing a sequence of processor instructions having a form independent of a value of said index;
• (f) instructions for storing the result of said step (e) in said accumulator;
• (g) instructions for repeating said steps (d) through (g) until said accumulator contains a representation of said base raised to said exponent;
• for cryptographically processing said base in a manner resistant to detection of said exponent by monitoring of said processor instructions.

A method of securing a computer processor against external monitoring of cryptographic operations performed thereby, comprising:

• (a) receiving logic instructions for execution on said processor to implement a cryptographic operation involving a cryptographic secret;
• (b) identifying an execution path-dependent portion of said logic instructions configured to produce a first computational result, and which would, if executed, reveal useful information about said cryptographic secret upon external monitoring;
• and
• (c) securing said processor against external monitoring, by replacing said path-dependent logic instructions with execution path-independent logic code that, when executed, reproduces said first computational result, and when monitored, reveals no useful information about said cryptographic secret.