Efficient finite field multiplication in normal basis

A method for use in a processor for multiplying signals represented in a normal basis for a finite field, the method comprising:

• receiving a first input signal representative of a first normal basis field element;
• receiving at least one additional input signal representative of a corresponding additional normal basis field element;
• generating rotated digital representations of the first and additional elements;
• and
• processing the rotated representations w bits at a time to generate an output signal representative of a product of the first and additional elements, where w is a word length which is associated with the processor and which is selected independently of the degree of the finite field.

An article of manufacture comprising a machine-readable medium containing one or more programs for multiplying signals represented in a normal basis for a finite field, which when executed on a processor, implement the steps of:

• receiving a first input signal representative of a first normal basis field element;
• receiving at least one additional input signal representative of a corresponding additional normal basis field element;
• generating rotated digital representations of the first and additional elements;
• and
• processing the rotated representations w bits at a time to generate an output signal representative of a product of the first an additional elements, where w is a word length which is associated with the processor and which is selected independently of the degree of the finite field.

An apparatus for multiplying signals represented in a normal basis for a finite field, the apparatus comprising:

• a normal basis multiplication unit comprising a first rotator receiving a first input signal representative of a first normal basis field element;
• at least one additional rotator, each receiving an input signal representative of a corresponding additional normal basis field element;
• and a word multiplier operative to receive output signals from the first and additional rotators, corresponding to rotated digital representations of the first and additional elements, respectively, and to process the rotated representations w bits at a time to generate an output signal representative of a product of the first and additional elements, where w is a word length which is associated with the word multiplier and which is selected independently of the degree of the finite field;
• at least one of a normal basis inversion unit and a normal basis squaring unit;
• and a memory associated with at least the multiplication unit.

An apparatus for multiplying signals represented in a normal basis for a finite field, the apparatus comprising:

• a normal basis multiplication unit comprising a first rotator receiving a first input signal representative of a first normal basis field element;
• at least one additional rotator, each receiving an input signal representative of a corresponding additional normal basis field element;
• and a word multiplier operative to receive output signals from the first and additional rotators, corresponding to rotated digital representations of the first and additional elements, respectively, and to process the rotated representations w bits at a time to generate an output signal representative of a product of the first and additional elements, where w is a word length which is associated with the word multiplier and which is selected independently of the degree of the finite field;
• and
• a cryptographic processor for implementing one or more cryptographic operations utilizing the normal basis multiplication unit.