Method of and apparatus for the reduction of a polynomial in a binary finite field, in particular in the context of a cryptographic application

A method of reducing a first data word corresponding to a polynomial C(x) and having a length of a maximum of 2n−1 to a second data word of a length of a maximum m which in a binary finite field GF(2m) whose elements are of a maximum length m corresponds to a polynomial C″0(x) equivalent to C(x), wherein m is either smaller than or equal to n, comprising the steps:

• providing a reduction polynomial R(x) which forms a trinomial or a pentanomial;
• partitioning the first data word into a binary first sub-data word C0 and a binary second sub-data word C1 whose corresponding polynomials C0(x) and C1(x) satisfy the equation C(x)=C1(x)*xm+C0(x), and picking off the second sub-data word to form a first summand term;
• right-shifting the second sub-data word to form a second summand term and repeating the right-shifting step to form further summand terms until a respective summand term is associated with each non-vanishing term of the reduction polynomial which is not the term xm by the step width of a respective right-shift being equal to the difference of m and the order of a respective non-vanishing term of the reduction polynomial;
• adding the formed summand terms with the exception of the first summand term, to the first data word;
• if the sum data word ascertained in that way is of a length greater than m, application of the method steps from the partitioning step to the summand data word formed until the sum data word ascertained in that way is of a length of a maximum m;
• and
• adding the first summand term and in the stated case of an application of the method steps from the partitioning step to the formed summand data word each further second sub-data word which has been ascertained in the meantime to the last-ascertained sum data word to form the second data word.

Apparatus for the reduction of a first data word corresponding to a polynomial C(x) and of a length of a maximum of 2n−1 to a second data word of a length of a maximum m which in a binary finite field GF(2m) whose elements are of a maximum length m corresponds to a polynomial C″0(x) equivalent to C(x), wherein m is either less than or equal to n, comprising:

• a memory which contains a representation of at least one reduction polynomial R(x) which forms a trinomial or pentanomial;
• a selection unit which is adapted to pick off a binary sub-data word from the first data word, whose corresponding polynomial C1(x) complies with the equation C(x)=C1(x)*xm+C0(x) and which forms a first summand term;
• a shift unit connected to the selection unit and adapted to shift the sub-data word towards the right by a respectively predetermined step width for forming a second or further summand terms and to output the formed summand terms;
• an adding unit connected to the shift unit and adapted to add a respective summand term and the summands outputted by the shift unit to the first data word;
• and
• a control unit which is adapted
• to determine the step width of a respective right-shift to be performed by the shift unit for forming a summand term as a difference of m and the order of a respective non-vanishing term of the reduction polynomial,
• to instruct the shift unit for repeated execution of the right-shift step for a formation of further summand terms with respective freshly determined step width until a respective summand term is associated with each non-vanishing term of a respectively predetermined reduction polynomial which is not the term xm, and
• to again activate if necessary the calculation unit, the shift unit and the adding unit until an ascertained sum data word is of a length of a maximum m and thus forms the second data word.