Patent ID: 7536429

Claim:
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 x n each having a first predetermined number of bits, k; (b) fragmenting Y into a second plurality of words y n each having a second predetermined number of bits, m; (c) pre-calculating multiples of a word x n of X in a pre-calculation circuit and using said pre-calculated multiples to derive products of the word x n of X with each of the plurality of words y n of Y; (d) computing an intermediate result R j 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, R j , for each of the first plurality of words x n ; (f) providing as output each of the intermediate results R j to form a final result; and (g) using the final result to complete an encryption or decryption operation within the electronic device.