Patent ID: 6920473

Claim:
Method for modular multiplying a multiplicand by a multiplier using a modulus, said multiplicand, said multiplier and said modulus being polynomials of a variable in a polynomial modulo arithmetic, within a cryptographic calculation, said multiplicand, said multiplier and said modulus being parameters in said cryptographic calculation, said method comprising the following steps: (a) performing a multiplication look-ahead method to obtain a multiplication shift value, said multiplication shift value being incremented at a power of said multiplier, which is not present in the multiplier polynomial; (b) multiplying said variable raised to the power of said multiplication shift value by an intermediate result polynomial to obtain a shifted intermediate result polynomial; (c) performing a reduction look-ahead method to obtain a reduction shift value, said reduction shift value being equal to the difference of the degree of said shifted intermediate result polynomial and the degree of said modulus polynomial; (d) multiplying said variable raised to the power of said reduction shift value by said modulus polynomial to obtain a shifted modulus polynomial; (e) summing said shifted intermediate result polynomial and said multiplicand and subtracting said shifted modulus polynomial to obtain an updated intermediate result polynomial; and (f) repeating steps (a) to (e) until all the powers of said multiplier have been processed, wherein in the repetition of steps (a) to (e) in step (d) said updated intermediate result polynomial of the previous step (e) is used as said intermediate result polynomial, and in step (c) said shifted polynomial of the previous step (d) is used as a modulus polynomial.