Modular multiplication using look-up tables
AssigneeNXP B.V.
InventorsJoppe Bos, Michaël Peeters
Life of this patent
Estimating the term…
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, bd 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.
Claims20
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, bd 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.
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.
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 Li,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 L0,k is 0, setting the values of a first lookup table, L0,k, of the plurality of lookup tables as
- L0,mi(ai)=(δo*aie0)mod mi
- where ai is a potential RNS integer for modulus mi of the RNS moduli, δo is a first predetermined constant, and e0 is a first predetermined exponent;
- and
- instructions for, when the value of the secret exponent, d, at the bit position corresponding to a first lookup table L0,k is 1, setting the values of a first lookup table, L0,mi, of the plurality of lookup tables as
- L0,mi(ai)=(δo*aie0*ai)mod mi.
Dependencies are inferred from the claim text.