US 7,536,429 B2 · Multiplier with look up tables

Abstract

A method of performing modular multiplication of integers X and Y to produce a result R, where R=X.Y mod N, in a multiplication engine. X is fragmented into a first plurality of words xn each having a first predetermined number of bits, k and Y is fragmented into a second plurality of words yn each having a second predetermined number of bits, m. Multiples of a word xn of X are derived in a pre calculation circuit and subsequently used to derive products of the word xn of X with each of the plurality of words yn of Y. An intermediate result Rjis calculated as a cumulating sum derived from said pre-calculated multiples and the steps repeated for each successive word of X so as to generate successive intermediate results, Rj, for each of the first plurality of words xn. The final result, R is obtained from the last of the intermediate results Rn−1.

Claims20

Dependent claims

A method for implementing a cryptographic algorithm in an electronic device that includes performing modular multiplication of integers X and Y to produce a result R, where R=X.Y mod N, in a multiplication engine, the method comprising the steps of:

(a) fragmenting X into a first plurality of words xn each having a first predetermined number of bits, k;
(b) fragmenting Y into a second plurality of words yn each having a second predetermined number of bits, m;
(c) pre-calculating multiples of a word xn of X in a pre-calculation circuit and using said pre-calculated multiples to derive products of the word xn of X with each of the plurality of words yn of Y;
(d) computing an intermediate result Rj as a cumulating sum derived from said products;
(e) for each successive word of X, repeating the steps of pre-calculating and computing to generate successive intermediate results, Rj, for each of the first plurality of words xn;
(f) providing as output each of the intermediate results Rj to form a final result;
and
(g) using the final result to complete an encryption or decryption operation within the electronic device.

5 more elements

Apparatus for performing modular multiplication of integers X and Y to produce a result R, where R=X.Y mod N, comprising:

means for fragmenting X into a first plurality of words xn each having a first predetermined number of bits, k;
means for fragmenting Y into a second plurality of words Yn each having a second predetermined number of bits, m;
a pre-calculation circuit for pre-calculating multiples of a word xn of X and using said pre-calculated multiples to derive products of the word xn of X with each of the plurality of words yn of Y;
means for computing an intermediate result Rj as a cumulating sum derived from said products;
and
control means for controlling repetition of the pre-calculations and computing of an intermediate result for each successive word of X to generate successive intermediate results, Rj, for each of the first plurality of words xn.

3 more elements

Dependencies are inferred from the claim text.

Multiplier with look up tables

Life of this patent

Multiplier with look up tables

Life of this patent

Abstract

Claims20