Modular multiplication using look-up tables

Patent metadata

Field	Value
Publication number	US-2016239267-A1
Application number	US-201514624874-A
Country	US
Kind code	A1
Filing date	Feb 18, 2015
Priority date	Feb 18, 2015
Publication date	Aug 18, 2016
Grant date	—

Abstract

Various embodiments relate to a method, system, and non-transitory machine-readable medium encoded with instructions for execution by a processor for performing modular exponentiation, the non-transitory machine-readable medium including: instructions for iteratively calculating a modular exponentiation, b d mod n, including: instructions for squaring a working value, c; and instructions for conditionally multiplying the working value, c, by a base value, b, dependent on a bit of an exponent, d, including: instructions for unconditionally multiplying the working value, c, by a lookup table entry associated with the base value.

First claim

What is claimed is:

1 . A non-transitory machine-readable medium encoded with instructions for execution by a processor for performing modular exponentiation, the non-transitory machine-readable medium comprising:
instructions for iteratively calculating a modular exponentiation, b d mod n, comprising:
instructions for squaring a working value, c; and
instructions for conditionally multiplying the working value, c, by a base value, b, dependent on a bit of an exponent, d, comprising:
instructions for unconditionally multiplying the working value, c, by a lookup table entry associated with the base value.

2 . The non-transitory machine-readable medium of claim 1 , wherein:
the working value c, and base value, b, are represented in a residue number system (RNS), and the instructions for unconditionally multiplying the working value, c, by a lookup table entry associated with the base value comprises multiplying a plurality of working RNS integers representative of the working value, c, by a plurality of lookup table entries associated with a plurality of base RNS integers representative of the base value, b.

3 . The non-transitory machine-readable medium of claim 2 , wherein the instructions for multiplying a plurality of working RNS integers representative of the working value, c, by a plurality of lookup table entries associated with a plurality of base RNS integers representative of the base value, b, comprises:
instructions for multiplying a working RNS integer of the plurality of working RNS integers representative of the working value, c, by a lookup table entry associated with a base RNS integer of the plurality of base RNS integers representative of the base value, b, from a lookup table associated with an RNS modulus corresponding to the base RNS integer.

4 . The non-transitory machine-readable medium of claim 1 , wherein:
the instructions for iteratively calculating the modular exponentiation comprise instructions for iterating through a plurality of bit positions of the exponent, d, and the instructions for unconditionally multiplying the working value, c, by a lookup table entry associated with the base value, b, comprise instructions for utilizing a lookup table associated with a current bit position from a plurality of lookup tables.

5 . The non-transitory machine-readable medium of claim 1 , wherein the instructions for conditionally multiplying the working value, c, by a base value, b, dependent on a bit of an exponent, d, comprise instructions for performing a Montgomery multiplication, and
the instructions for performing a Montgomery multiplication invoke the instructions for unconditionally multiplying the working value, c, by a lookup table entry associated with the base value.

6 . The non-transitory machine-readable medium of claim 1 , further comprising:
instructions for receiving, from another device, a set of lookup tables for use by the instructions for unconditionally multiplying the working value, c, by a lookup table entry associated with the base value.

7 . A non-transitory machine-readable medium encoded with instructions for execution by a processor for generating lookup tables for performing modular exponentiation, the non-transitory machine-readable medium comprising:
instructions for initializing a plurality of lookup tables respectively corresponding to different bit positions within a secret exponent, d; and instructions for generating values for inclusion in the plurality of lookup tables, comprising
instructions for generating a value for a lookup table according to a first method when the secret exponent, d, carries a first bit value at a bit position associated with the lookup table, and
instructions for generating a value for a lookup table according to a second method different from the first method when the secret exponent, d, carries a second bit value different from the first bit value at a bit position associated with the lookup table.

8 . The non-transitory machine-readable medium of claim 7 , wherein the instructions for generating values for inclusion in the plurality of lookup tables comprise instructions for obfuscating the generated values.

9 . The non-transitory machine-readable medium of claim 8 , wherein the instructions for obfuscating the generated values comprise:
instructions for performing a first mathematical function on a first value for inclusion in a first lookup table; and instructions for performing a second mathematical function on a second value for inclusion in a second lookup table, wherein the second mathematical function is an effective inverse of the first mathematical function.

10 . The non-transitory machine-readable medium of claim 9 , wherein:
the first mathematical function incorporates an obfuscating value into the first value, and the second mathematical function incorporates the square of a modular inverse of the obfuscating value into the second value.

11 . The non-transitory machine-readable medium of claim 10 , wherein the obfuscating value comprises a constant value that is invariant based on an index where the first value will be stored within the first lookup table.

12 . The non-transitory machine-readable medium of claim 10 , wherein the obfuscating value comprises an index where the first value will be stored within the lookup table raised to the power of a constant exponent value.

13 . The non-transitory machine-readable medium of claim 7 , wherein the first method and the second method share at least one instruction in common.

14 . The non-transitory machine-readable medium of claim 7 , wherein:
the first method comprises a differentiating instruction for incorporating into the value an index where the value will be stored within the lookup; and the second method omits the differentiating instruction.

15 . The non-transitory machine-readable medium of claim 7 , wherein the instructions for initializing a plurality of lookup tables respectively corresponding to different bit positions within a secret exponent, d, comprise:
instructions for determining a set of moduli M to be used in a residue numerical system (RNS); and instructions for initializing, for each modulus m i in the set of moduli M, a plurality of lookup tables respectively corresponding to different bit positions within a secret exponent, d.

16 . A system for providing white box modular exponentiation comprising:
a first device comprising a first processor and the non-transitory machine-readable medium of claim 1 ; and a second device comprising a second processor and the non-transitory machine-readable medium of claim 7 , wherein the second device generates a plurality of lookup tables for use by the first device for performing modular exponentiation without access to the secret exponent, d.

17 . A non-transitory machine-readable medium encoded with instructions for execution by a processor for generating lookup tables for performing modular exponentiation, the non-transitory machine-readable medium comprising:
instructions for initializing a plurality of lookup tables L i,j respectively corresponding to a plurality of pairings of bit positions of a secret exponent, d, and residue number system (RNS) moduli; instructions for, when the value of the secret exponent, d, at the bit position corresponding to a first lookup table L 0,k is 0, setting the values of a first lookup table, L 0,k , of the plurality of lookup tables as
L 0,m i ( a i )=(δ o *a i e 0 )mod m i

where a i is a potential RNS integer for modulus m i

Assignees

• Nxp Bv

Inventors

• Bos Joppe
• Peeters Michaël

Classifications

• G06F2207/7261

  Uniform execution, e.g. avoiding jumps, or using formulae with the same power profile · CPC title

• G06F7/4812 Primary

  Complex multiplication · CPC title

• H04L2209/16

  Obfuscation or hiding, e.g. involving white box · CPC title

• G06F7/729

  using representation by a residue number system · CPC title

• H04L9/002

  Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441) · CPC title