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

Abstract

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(2 m ) whose elements are of a maximum length m corresponds to a polynomial C″0(x) equivalent to C(x), wherein m is smaller than or equal to n, includes partitioning of the first data word into a binary first sub-data word C0 and a binary second sub-data word C1, repeated right-shift of C1 to form summand terms until a respective summand term is associated with each non-disappearing term of a reduction trinomial or pentanomial which is not the term x m , adding the summand terms formed to the first sub-data word to form a sum data word and applying the partitioning step to the summand data word formed until the ascertained sum data word is of a length of a maximum m and forms the desired second data word.

1 . 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(2 m ) 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)*x m +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 x m  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 to the first sub-data word to form a sum 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 thus forms the second data word.   
   
   
       2 . 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(2 m ) 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)*x m +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 x m  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.   
   
   
       3 . A method as set forth in  claim 1  wherein the first data word is of a length of less than 2n−1, comprising an additional first adjustment step which is performed prior to the right-shift operation and which includes a left-shift of the first data word by a filling step width and attachment at both sides of a number of zeros corresponding to the filling step width to the first data word in such a way that the length of the first data word modified in that way is 2n−1 and that in the modified first data word those terms of the polynomial C(x) corresponding to the first data word, that are of an order of greater than m, are arranged at the same bit positions as if the first data word were already initially of the length 2n−1. 
   
   
       4 . A method as set forth in  claim 3  comprising a second adjustment step which includes removal of the initially attached zeros from the ascertained sum data word and a right-shift of the sum data word by the filling step width. 
   
   
       5 . A method as set forth in  claim 1  wherein the irreducible polynomial is represented solely by the powers of the non-vanishing terms of the reduction polynomial, which are not the term x m . 
   
   
       6 . A method as set forth in  claim 5  wherein the irreducible polynomial is additionally represented by the known maximum length m of data words of the binary finite field. 
   
   
       7 . An asymmetric cryptography method for use in an electronic cryptography apparatus comprising
 reducing 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(2 m ) 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, in accordance with a method as set forth in  claim 1 .   
   
   
       8 . An asymmetric cryptography method as set forth in  claim 7  which forms a method of elliptic curve cryptography, including prior to the reduction operation:
 multiplying two factor data words corresponding to factor polynomials A(x) and B(x) to give the first data word corresponding to a polynomial C(x) of a length of a maximum of 2n−1.   
   
   
       9 . A method of calculating a digital signature including an asymmetric cryptography method as set forth in  claim 8 . 
   
   
       10 . 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(2 m ) 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)*x m +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 x m , 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. 
   
   
   
       11 . Apparatus as set forth in  claim 10  wherein the control unit is adapted to instruct the adding unit in the case of a repetition of the method steps from the step of ascertaining a binary sub-data word to add the respectively formed summand terms with the exception of the first summand term to the respective first data word, 
     and after establishing that an ascertained sum data word is of a length which is no greater than m, for forming the second data word, to add each first summand term ascertained in the meantime to the ascertained sum data word. 
   
   
       12 . Apparatus as set forth in  claim 10  comprising a first and a second adjustment unit, 
     wherein the first adjustment unit is adapted to shift an incoming first data word of a length of less than 2n−1, prior to the right-shift operation, by a filling step width towards the left and on both sides of the first data word to attach a number of zeros corresponding to the filling step width to the first data word in such a way that the length of the first data word modified in that way is 2n−1 and that in the modified first data word those terms of the polynomial C(x) corresponding to the first data word, that are of an order of greater than m, are arranged at the same bit positions as if the first data word were already initially of the length 2n−1, and 
     wherein the second adjustment unit is adapted to shift the ascertained sum data word of the length of a maximum m by the filling step width towards the right and to remove the initially added zeros. 
   
   
       13 . Apparatus as set forth in  claim 10  wherein the shift unit includes a number of parallel-connected right-shifters, to which the sub-data word is fed. 
   
   
       14 . Apparatus as set forth in  claim 10  wherein the shift unit includes precisely one right-shifter and wherein the control unit is adapted to effect the repetition of the right-shift step for forming further summand terms by additional right-shifting of the summand term last outputted by the right-shifter by a respective difference step width, wherein the respective difference step width is the difference between the right-shifts of successive summand terms in each case in relation to the first summand term. 
   
   
       15 . An electronic cryptography apparatus including a reduction apparatus as set forth in  claim 10 . 
   
   
       16 . An electronic cryptography apparatus as set forth in  claim 15  adapted for encryption or decryption of data in accordance with a method of elliptic curve cryptography. 
   
   
       17 . An electronic cryptography apparatus as set forth in  claim 16  comprising a multiplier apparatus adapted to multiply two factor data words corresponding to factor polynomials A(x) and B(x) to give a first data word corresponding to the polynomial C(x) of a length of a maximum of 2n−1. 
   
   
       18 . A method as set forth in  claim 2  wherein the first data word is of a length of less than 2n−1, comprising an additional first adjustment step which is performed prior to the right-shift operation and which includes a left-shift of the first data word by a filling step width and attachment at both sides of a number of zeros corresponding to the filling step width to the first data word in such a way that the length of the first data word modified in that way is 2n−1 and that in the modified first data word those terms of the polynomial C(x) corresponding to the first data word, that are of an order of greater than m, are arranged at the same bit positions as if the first data word were already initially of the length 2n−1. 
   
   
       19 . A method as set forth in  claim 2  wherein the irreducible polynomial is represented solely by the powers of the non-vanishing terms of the reduction polynomial, which are not the term x m . 
   
   
       20 . A method as set forth in  claim 3  wherein the irreducible polynomial is represented solely by the powers of the non-vanishing terms of the reduction polynomial, which are not the term x m . 
   
   
       21 . A method as set forth in  claim 4  wherein the irreducible polynomial is represented solely by the powers of the non-vanishing terms of the reduction polynomial, which are not the term x m . 
   
   
       22 . An asymmetric cryptography method for use in an electronic cryptography apparatus comprising
 reducing 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(2 m ) 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, in accordance with a method as set forth in  claim 2 .   
   
   
       23 . An asymmetric cryptography method for use in an electronic cryptography apparatus comprising
 reducing 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(2 m ) 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, in accordance with a method as set forth in  claim 3 .   
   
   
       24 . An asymmetric cryptography method for use in an electronic cryptography apparatus comprising
 reducing 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(2 m ) 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, in accordance with a method as set forth in  claim 4 .   
   
   
       25 . An asymmetric cryptography method for use in an electronic cryptography apparatus comprising
 reducing 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(2 m ) 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, in accordance with a method as set forth in  claim 5 .   
   
   
       26 . An asymmetric cryptography method for use in an electronic cryptography apparatus comprising
 reducing 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(2 m ) 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, in accordance with a method as set forth in  claim 6 .   
   
   
       27 . Apparatus as set forth in  claim 11  comprising a first and a second adjustment unit, 
     wherein the first adjustment unit is adapted to shift an incoming first data word of a length of less than 2n−1, prior to the right-shift operation, by a filling step width towards the left and on both sides of the first data word to attach a number of zeros corresponding to the filling step width to the first data word in such a way that the length of the first data word modified in that way is 2n−1 and that in the modified first data word those terms of the polynomial C(x) corresponding to the first data word, that are of an order of greater than m, are arranged at the same bit positions as if the first data word were already initially of the length 2n−1, and 
     wherein the second adjustment unit is adapted to shift the ascertained sum data word of the length of a maximum m by the filling step width towards the right and to remove the initially added zeros. 
   
   
       28 . Apparatus as set forth in  claim 11  wherein the shift unit includes a number of parallel-connected right-shifters, to which the sub-data word is fed. 
   
   
       29 . Apparatus as set forth in  claim 12  wherein the shift unit includes a number of parallel-connected right-shifters, to which the sub-data word is fed. 
   
   
       30 . Apparatus as set forth in  claim 11  wherein the shift unit includes precisely one right-shifter and wherein the control unit is adapted to effect the repetition of the right-shift step for forming further summand terms by additional right-shifting of the summand term last outputted by the right-shifter by a respective difference step width, wherein the respective difference step width is the difference between the right-shifts of successive summand terms in each case in relation to the first summand term. 
   
   
       31 . Apparatus as set forth in  claim 12  wherein the shift unit includes precisely one right-shifter and wherein the control unit is adapted to effect the repetition of the right-shift step for forming further summand terms by additional right-shifting of the summand term last outputted by the right-shifter by a respective difference step width, wherein the respective difference step width is the difference between the right-shifts of successive summand terms in each case in relation to the first summand term. 
   
   
       32 . An electronic cryptography apparatus including a reduction apparatus as set forth in  claim 11 . 
   
   
       33 . An electronic cryptography apparatus including a reduction apparatus as set forth in  claim 12 . 
   
   
       34 . An electronic cryptography apparatus including a reduction apparatus as set forth in  claim 13 . 
   
   
       35 . An electronic cryptography apparatus including a reduction apparatus as set forth in  claim 14 .