Efficient finite field basis conversion involving a dual basis

Abstract

The invention provides apparatus and methods for use in basis conversion involving a dual basis, such as a dual of a polynomial basis or dual of a normal basis. The invention in an illustrative embodiment includes basis generators for generating elements of a dual of a polynomial or a normal basis of a finite field GF(q m ), where q is a prime number or power of a prime number and m is an integer greater than or equal to 2. The basis generators can be used in “import” basis conversion, such as converting a representation in an external basis to a representation in an internal dual of a polynomial basis or dual of a normal basis, as part of a generate-accumulate algorithm, or in “export” basis conversion, such as converting a representation in an internal dual of a polynomial basis or dual of a normal basis to a representation in an external basis, as part of a generate-evaluate algorithm. The invention also includes basis shifters which generate a shifted version of a representation in an internal polynomial or normal basis. The basis shifters may be used in import basis conversion as part of a shift-insert algorithm, or in export basis conversion as part of a shift-extract algorithm. The basis shifters may also be used to provide alternative shift-based basis generators. The basis conversion techniques of the invention significantly increase the storage and computational efficiency of dual basis operations in cryptographic systems and other applications.

What is claimed is:  
     
         1 . An apparatus for determining elements in a dual of a polynomial basis for a finite field, the apparatus comprising: 
 a coefficient generator which generates a coefficient in the polynomial basis;    a multiplier for multiplying a first value by a function of a generator of the polynomial basis; and    a subtractor for subtracting a function of the coefficient from one of an output of the multiplier and an input value, such that an output of one of the subtractor and the multiplier corresponds to a second value which is used to provide a shifted version of the input value in the dual of the polynomial basis.    
     
     
         2 . The apparatus of    claim 1    wherein the first value corresponds to the input value, the output of the multiplier is applied to an input of the subtractor and to an input of the coefficient generator, such that the subtractor subtracts the function of the coefficient from the output of the multiplier, the output of the subtractor corresponds to the second value, and the coefficient generator utilizes the output of the multiplier to generate the coefficient.  
     
     
         3 . The apparatus of    claim 1    wherein the first value corresponds to the input value, the output of the multiplier is applied to an input of the subtractor, such that the subtractor subtracts the function of the coefficient from the output of the multiplier, the output of the subtractor corresponds to the second value, and the coefficient generator utilizes the input value to generate the coefficient.  
     
     
         4 . The apparatus of    claim 1    wherein the first value corresponds to an output of the subtractor, the coefficient generator utilizes the input value to generate the coefficient, the subtractor subtracts the function of the coefficient from the input value, the output of the subtractor is applied to an input of the multiplier, and the output of the multiplier corresponds to the second value.  
     
     
         5 . The apparatus of    claim 1    wherein the operations of the coefficient generator, multiplier and subtractor are repeated to provide additional shifted versions of the input value in the dual of the polynomial basis, and wherein the shifted versions of the input value are used to generate elements of the dual of the polynomial basis.  
     
     
         6 . The apparatus of    claim 1    further including a looping mechanism operative to repeat the operations of the coefficient generator, multiplier and subtractor so as to generate a plurality of shifted versions of elements in the dual of the polynomial basis, wherein each non-initial iteration of the loop starts with the input value set to the second value generated in the previous iteration of the loop.  
     
     
         7 . The apparatus of    claim 1    wherein the input value initially corresponds to an identity element and the dual of the polynomial basis is a canonical polynomial basis.  
     
     
         8 . The apparatus of    claim 1    further including an additional multiplier for multiplying the second value by a scaling factor to generate a shifted version of an element in the dual of the polynomial basis.  
     
     
         9 . The apparatus of    claim 8    wherein the scaling factor corresponds to a linear function.  
     
     
         10 . The apparatus of    claim 1    wherein the coefficient generator generates the coefficient using a coefficient extractor which determines a coefficient of a representation of an element in the polynomial basis.  
     
     
         11 . The apparatus of    claim 1    wherein the coefficient generator generates the coefficient using an additional multiplier in conjunction with a coefficient selector.  
     
     
         12 . The apparatus of    claim 1    wherein the coefficient generated by the coefficient generator is computed as a function of V 0 , where V 0  is an element such that (A×V 0 ) [0]=h 0 (A) in the polynomial basis, and where h 0 (A) is a function whose output is a coefficient of A when A is represented in the polynomial basis.  
     
     
         13 . The apparatus of    claim 12    wherein the coefficient generated by the coefficient generator is of the form (W×V 0 )[0].  
     
     
         14 . The apparatus of    claim 1    wherein the multiplier multiplies the first value by a function YH, where Y is the inverse of a scaling factor and H is the inverse of the polynomial basis generator.  
     
     
         15 . The apparatus of    claim 1    wherein the multiplier multiplies the first value by a function H, where H is the inverse of the polynomial basis generator.  
     
     
         16 . The apparatus of    claim 12    wherein the coefficient generated by the coefficient generator is computed as a function of V 0 YH, where Y is the inverse of a scaling factor and H is the inverse of the polynomial basis generator.  
     
     
         17 . The apparatus of    claim 1    wherein at least a subset of the coefficient generator, multiplier and subtractor are implemented in a processor which is operative to convert a representation in an external dual of a polynomial basis to a representation in an internal basis using a generate-accumulate algorithm.  
     
     
         18 . The apparatus of    claim 1    wherein at least a subset of the coefficient generator, multiplier and subtractor are implemented in a processor which is operative to convert a representation in an internal basis to a representation in an external polynomial basis using a generate-evaluate algorithm which generates a dual of the polynomial basis.  
     
     
         19 . The apparatus of    claim 1    wherein at least a subset of the coefficient generator, multiplier and subtractor are implemented in a processor which is operative to convert a representation in an external dual of a polynomial basis to a representation in an internal basis using a shift-insert algorithm.  
     
     
         20 . The apparatus of    claim 1    wherein at least a subset of the coefficient generator, multiplier and subtractor are implemented in a processor which is operative to convert a representation in an internal basis to a representation in an external dual of a polynomial basis using a shift-extract algorithm.  
     
     
         21 . An apparatus for determining elements in a dual of a normal basis for a finite field, the apparatus comprising: 
 an exponentiator; and    a multiplier which is operative to multiply one of an input value and an output of the exponentiator by a function of a generator of the dual basis, wherein the multiplier and exponentiator are configured to operate such that one of the multiplier and exponentiator generates an output value corresponding to a shifted version of the input value in the dual of the normal basis.    
     
     
         22 . The apparatus of    claim 21    wherein the function of a generator of the dual basis is also a function of a scaling value.  
     
     
         23 . The apparatus of    claim 21    wherein the multiplier multiplies the input value by a function of the generator of the dual basis, and the exponentiator raises an output of the multiplier to a power to generate the output value.  
     
     
         24 . The apparatus of    claim 21    wherein the exponentiator computes a value representing the input value raised to a power, and the multiplier generates the output value as a product of the value computed by the exponentiator multiplied by a function of the generator.  
     
     
         25 . The apparatus of    claim 21    wherein the operations of the exponentiator and multiplier are repeated to provide additional output values corresponding to shifted versions of the input value in the dual of the normal basis, and wherein the output values are used to generate elements of the dual of the normal basis.  
     
     
         26 . The apparatus of    claim 21    further including a looping mechanism operative to repeat the operations of the exponentiator and multiplier so as to generate a plurality of shifted versions of elements in the dual of the normal basis, wherein each non-initial iteration of the loop starts with the input value set to the output value generated in the previous iteration of the loop.  
     
     
         27 . The apparatus of    claim 21    wherein the input value initially corresponds to an identity element and the dual of the normal basis is a canonical normal basis.  
     
     
         28 . The apparatus of    claim 21    an initial value of the input value corresponds to a scaling factor.  
     
     
         29 . The apparatus of    claim 28    wherein the scaling factor corresponds to a linear function.  
     
     
         30 . The apparatus of    claim 21    wherein the multiplier multiplies one of the input value and the output value by a function SZ 1−q  where S is a generator of the dual of the normal basis, Z is a scaling factor and q is a prime or a power of a prime.  
     
     
         31 . The apparatus of    claim 21    wherein the multiplier multiplies one of the input value and the output value by a function SZ, where S is a generator of the dual of the normal basis, and Z is a scaling factor.  
     
     
         32 . The apparatus of    claim 21    wherein the multiplier multiplies one of the input value and the output value by a qth root of SZ 1−q  where S is a generator of the dual of the normal basis, Z is a scaling factor and q is a prime or a power of a prime.  
     
     
         33 . The apparatus of    claim 21    further including an additional multiplier for multiplying one of the input value and the output value by a function of a scaling factor.  
     
     
         34 . The apparatus of    claim 21    wherein at least one of the exponentiator and multiplier are implemented in a processor which is operative to convert a representation in an external dual of a normal basis to a representation in an internal basis using a generate-accumulate algorithm.  
     
     
         35 . The apparatus of    claim 21    wherein at least one of the exponentiator and multiplier are implemented in a processor which is operative to convert a representation in an internal basis to a representation in an external normal basis using a generate-evaluate algorithm which generates a dual of the normal basis.  
     
     
         36 . The apparatus of    claim 21    wherein at least one of the exponentiator and multiplier are implemented in a processor which is operative to convert a representation in an external dual of a normal basis to a representation in an internal basis using a shift-insert algorithm.  
     
     
         37 . The apparatus of    claim 21    wherein at least one of the exponentiator and multiplier are implemented in a processor which is operative to convert a representation in an internal basis to a representation in an external dual of a normal basis using a shift-extract algorithm.  
     
     
         38 . An apparatus for determining elements of a dual of a normal basis for a finite field, the apparatus comprising: 
 an exponentiator which raises an input value to a power, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and    a multiplier which is operative to multiply an output of the exponentiator, generated after the designated number of repetitions, by a scaling factor which is a function of a (q−1) st  root of S, where S is a generator of the normal basis and q is a prime or a power of a prime, such that an output of the multiplier corresponds to an element of the dual of the normal basis.    
     
     
         39 . The apparatus of    claim 38    wherein an initial value of the input value corresponds to a (q−1) st  root of S.  
     
     
         40 . The apparatus of    claim 38    wherein the operations of the exponentiator and multiplier are repeated to generate additional elements of the dual of the normal basis.  
     
     
         41 . An apparatus for determining elements of a dual of a normal basis for a finite field, the apparatus comprising: 
 an exponentiator which raises an input value to a power, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and    a multiplier which is operative to multiply an output of the exponentiator, generated after the designated number of repetitions, by one of an initial value and a previously-generated output of the multiplier, such that a current output of the multiplier corresponds to an element of the dual of the normal basis.    
     
     
         42 . The apparatus of    claim 41    wherein the operations of the exponentiator and multiplier are repeated to generate additional elements of the dual of the normal basis.  
     
     
         43 . The apparatus of    claim 41    wherein the input value is initially set to a function of a generator of the dual basis.  
     
     
         44 . The apparatus of    claim 41    wherein the input value initially corresponds to an identity element.  
     
     
         45 . The apparatus of    claim 41    wherein the initial value corresponds to a scaling factor.  
     
     
         46 . The apparatus of    claim 41    wherein the initial value corresponds to an identity element.  
     
     
         47 . A method of determining elements in a dual of a polynomial basis for a finite field, the method comprising the steps of: 
 generating a signal corresponding to a coefficient in the polynomial basis in a coefficient generator;    multiplying a signal corresponding to a first value by a function of a generator of the polynomial basis in a multiplier; and    subtracting a function of the signal corresponding to the coefficient from one of an output of the multiplier and an input value in a subtractor, such that an output of one of the subtractor and the multiplier is used to provide a shifted version of the input value in the dual of the polynomial basis.    
     
     
         48 . A method for determining elements in a dual of a normal basis for a finite field, the method comprising: 
 multiplying one of a signal corresponding to an input value and an output of an exponentiator by a function of a generator of the dual basis in a multiplier, wherein the multiplier and exponentiator are configured to operate such that one of the multiplier and exponentiator generates an output value corresponding to a shifted version of the input value in the dual of the normal basis.    
     
     
         49 . A method for determining elements of a dual of a normal basis for a finite field, the method comprising: 
 raising a signal corresponding to an input value to a power in an exponentiator, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and    multiplying an output of the exponentiator, generated after the designated number of repetitions, in a multiplier by a scaling factor which is a function of a (q−1) st  root of S, where S is a generator of the normal basis and q is a prime or a power of a prime, such that an output of the multiplier corresponds to an element of the dual of the normal basis.    
     
     
         50 . A method for determining elements of a dual of a normal basis for a finite field, the method comprising: 
 raising a signal corresponding to an input value to a power in an exponentiator, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and    multiplying an output of the exponentiator, generated after the designated number of repetitions, in a multiplier by one of an initial value and a previously-generated output of the multiplier, such that a current output of the multiplier corresponds to an element of the dual of the normal basis.