Efficient finite field multiplication in normal basis
First Claim
1. An apparatus for multiplying signals represented in a normal basis for a finite field, the apparatus comprising:
- a first rotator receiving a first input signal representative of a first normal basis 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.
13 Assignments
0 Petitions
Accused Products
Abstract
The invention provides improved techniques for multiplication of signals represented in a normal basis of a finite field. An illustrative embodiment includes a first rotator which receives a first input signal representative of a first normal basis field element (a0 a1 . . . am−1), and a second rotator which receives a second input signal representative of a second normal basis field element (b0 b1 . . . bm−1). A word multiplier receives output signals from the first and second rotators, corresponding to rotated representations of the first and second elements, respectively, and processes the rotated representations w bits at a time to generate an output signal representative of a product of the first and second elements, where w is a word length associated with the word multiplier. The rotated representation of the first element may be given by A[i]=(ai ai+1 . . . ai+w−1), the rotated representation of the second element may be given by B[i]=(bi bi+1 . . . bi+w−1), and the product may be given by c=(C[0], C[w], C[2w], . . . , C[m−w]), where C[i]=(ci Ci+1 . . . ci +w−1), m is the degree of the finite field, w is the word length, and i=0, 1, . . . m−1. The invention is particularly well suited for implementation in software, and can provide performance advantages for both general normal basis and optimal normal basis.
280 Citations
16 Claims
-
1. An apparatus for multiplying signals represented in a normal basis for a finite field, the apparatus comprising:
-
a first rotator receiving a first input signal representative of a first normal basis 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
5. The apparatus of claim 4 wherein A[i] and B[i] are precomputed and stored for i=0, 1, . . . m−
- 1.
-
6. The apparatus of claim 3 wherein the product c=(C[0], C[w], C[2w], . . . , C[m−
- w]) is computed as follows;
for t from 0 to (m/w−
1)
- w]) is computed as follows;
-
7. The apparatus of claim 6 wherein A[i] and B[i] are precomputed and stored for i=0, 1, . . . m−
- 1.
-
8. The apparatus of claim 3 wherein A[i+m]=A[i]=(ai ai+1 . . . ai+w−
- 1), B[i+m]=B[i]=(bi bi+1 . . . bi+w−
1), array A is precomputed as A[0], A[1], . . . , A[m−
1], A[m], A[m+1], . . . , A[2m−
1], and array B is precomputed as B[0], B[1], . . . , B[m−
1], B[m], B[m+1], . . . , B[2m−
1], such that each of array A and B include 2m elements of length w.
- 1), B[i+m]=B[i]=(bi bi+1 . . . bi+w−
-
9. The apparatus of claim 8 wherein words 0 through m−
- 1 in A and B are used in computing C[0], words w through w+m−
1 in A and B are used in computing C[w], and the remaining elements C[2w], . . . , C[m−
w] of the product c are computed in the same manner.
- 1 in A and B are used in computing C[0], words w through w+m−
-
10. The apparatus of claim 1 wherein the word multiplier further comprises a multiplication index input and wherein the apparatus further comprises a multiplication index generator having an output coupled to the multiplication index input of the word multiplier.
-
11. The apparatus of claim 10 wherein the multiplication index generator generates a multiplication index which is an m-by-m multiplication matrix M, wherein m is the degree of the finite field.
-
12. The apparatus of claim 10 wherein the normal basis is an optimal normal basis, and wherein the multiplication index generator generates a multiplication index which is an array with 2m−
- 1 entries, corresponding to a compact representation of a multiplication matrix M, where m is the degree of the finite field.
-
13. 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.
-
-
14. 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.
-
-
15. 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.
-
-
16. 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.
-
Specification