Method and apparatus for calculating a polynomial multiplication, in particular for elliptic curve cryptography

A polynomial multiplier comprising

• at least one partial multiplier
• a selection unit which is adapted
• to receive coefficients ai, bi of two polynomials
• A
• ⁡
• (
• x
• )
• =
• ⊕
• i
• =
• 0
• n
• -
• 1
• ⁢
• a
• i
• ⁢
• x
• i
• and
• B
• ⁡
• (
• x
• )
• =
• ⊕
• i
• =
• 0
• n
• -
• 1
• ⁢
• b
• i
• ⁢
• x
• i
• ,
• wherein “⊕” identifies an addition or an XOR operation, ai and bi are one-bit binary values, that is to say 0 or 1, and xi=1, and
• in a working step to select either two or more than two fragments, one from each polynomial, of such a length as operands for a partial multiplication and to provide same at its output, that the partial multiplication to be made by the partial multiplier requires only one calculation step,
• wherein the selection unit is additionally adapted to select the fragments iteratively in accordance with a predefined selection plan in successive working steps,
• wherein the at least one partial multiplier is connected to the selection unit and is adapted in an iteration step to carry out partial multiplication of the either two or the more than two operands and to provide the obtained partial product at its output,
• an accumulation unit which is connected to the partial multiplier and which is adapted to calculate the complete polynomial product by an accumulation which is completed iteration step by iteration step of the partial products which it has received from the partial multiplier, and characterized in that, the polynomial multiplier is in the form of an integrated circuit, which further comprises
• an accumulation control unit which is connected to the partial multiplier and the accumulation unit and which is adapted to output after a respective current iteration step a control signal which instructs the accumulation unit in accordance with a predetermined accumulation plan to accumulate a partial product currently occurring at the output of the partial multiplier with one or more terms of a result polynomial which is further developed iteration step by iteration step,
• wherein the accumulation unit includes a number of XOR gates, each XOR gate is connected at an input to one or more terms of the arising result polynomial and at another input to the partial multiplier and the accumulation control unit has a number of control logic gates which corresponds to the number of XOR gates of the accumulation unit, wherein each control logic gate is associated with a respective XOR gate and in which the accumulation control unit is adapted to produce a predetermined set of control signals in a respective iteration step and to apply the control signals to the control logic gates, wherein a respective control signal establishes whether a respective XOR gate is or is not activated in a current iteration step for accumulation, wherein the control logic gates are AND gates having two inputs of which a first input receives a logic one and a second input receives a control signal and wherein the polynomial multiplier comprises a selection control unit which is connected to the selection unit and which is adapted in accordance with the respective current iteration step to output a control signal which instructs the selection unit in accordance with the predetermined selection plan to select a respective fragment of predetermined size from each polynomial.