US 2004/0019622 A1Published application

Method and apparatus for modular multiplying and calculating unit for modular multiplying

AssigneeInfineon Technologies AG

InventorsAstrid Elbe, Norbert Janssen, Holger Sedlak, Jean-Pierre Seifert

Life of this patent

Estimating the term…

Loading patent…

Abstract

In a method for modular multiplying a multiplicand by a multiplier using a modulus, the multiplicand, the multiplier and the modulus being polynomials of variable, a multiplication look-ahead method to obtain a multiplication shift value is carried out. An intermediate result polynomial is shifted to the left by the number of digits of the multiplication shift value to obtain a shifted intermediate result polynomial. Furthermore, a reduction look-ahead method to obtain a reduction shift value is carried out, the reduction shift value equalling the difference of the degree of the shifted intermediate result polynomial and the degree of the modulus polynomial. The modulus polynomial is then shifted by a number of digits equalling the reduction shift value to obtain a shifted modulus polynomial. In a three-operands addition, the shifted intermediate result polynomial and the multiplicand are summed and the shifted modulus polynomial is subtracted to obtain an updated intermediate result polynomial. By iteratively executing the preceding steps the modular multiplication is processed progressively until all the powers of the multiplier polynomial have been processed. By means of a carry disabling function it is possible to carry out both a Z/NZ arithmetic as well as a GFarithmetic on a single long number calculating unit.

Claims13

Dependent claims

Method for modular multiplying a multiplicand by a multiplier using a modulus, said multiplicand, said multiplier and said modulus being polynomials of a variable, with 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.

6 more elements

Apparatus for modular multiplying a multiplicand by a multiplier using a modulus, said multiplicand, said multiplier and said modulus being polynomials of a variable, within a cryptographic calculation, said multiplicand, said multiplier and said modulus being parameters in said cryptographic calculation, said apparatus comprising:

(a) means for 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) means for multiplying said variable which is raised to the power of said multiplication shift value by an intermediate result polynomial to obtain a shifted intermediate result polynomial;
(c) means for 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) means for multiplying said variable which is raised to the power of said reduction shift value by said modulus polynomial to obtain a shifted modulus polynomial;
(e) means for summing said shifted intermediate result polynomial and said multiplicand and subtracting said shifted modulus polynomial to obtain an updated intermediate result polynomial;
and
(f) means for repeatedly controlling said means (a) to (e) until all the powers of said multiplier have been processed, wherein in a repeated control of said means (a) to (e)
said means for multiplying to obtain a shifted intermediate result polynomial is arranged to use said updated intermediate result polynomial of the previous control of said means for summing as an intermediate result polynomial, and
said means for performing a reduction look-ahead method is arranged to use, in a repeated control, as the modulus polynomial, said shifted modulus polynomial of the previous control of said means for multiplying to obtain a shifted modulus polynomial.

6 more elements

Dependencies are inferred from the claim text.