Efficient finite field multiplication in normal basis

Details Efficient finite field multiplication in normal basis Efficient finite field multiplication in normal basis

1998-12-28

2002-05-14

Ngo, Ohuong Dinh (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C380S028000

Reexamination Certificate

active

06389442

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to information processing systems and devices, such as cryptographic systems and devices, which include a capability for multiplying signals of a finite field having a normal basis.
BACKGROUND OF THE INVENTION
Finite field arithmetic operations are becoming increasingly important in today's computer systems, particularly for cryptographic processing applications. Among the more common finite fields used in cryptography are odd-characteristic finite fields of degree 1, conventionally known as GF(p) arithmetic or arithmetic modulo a prime, and even-characteristic finite fields of degree greater than 1, conventionally known as GF(2
m
) arithmetic (where m is the degree). GF(2
m
) arithmetic is further classified according to the choice of basis for representing elements of the finite field; two common choices are polynomial basis and normal basis.
It is known that multiplication in normal basis, particularly in optimal normal basis (ONB), can be implemented efficiently in hardware. However, little attention has been devoted to implementing normal basis multiplication efficiently in software. A number of difficulties have prevented the development of fast software implementation of normal basis multiplication. First, when multiplying two elements represented in normal basis according to the standard formula, the coefficients of their product need to be computed one bit at a time. Second, the computation of a given coefficient involves a series of arithmetic operations which need to be performed sequentially in software, while in hardware, they can be easily parallelized.
We will first define some basic notation for a finite field GF(2
m
) and its representation in normal basis. Then, we will describe conventional multiplication formulas for both general normal basis and ONB. Let w denote the word size in bits. For a typical software implementation, we have w=32. Let m be a positive integer. For simplicity, we assume that w|m. The finite field GF(2
m
) consists of 2
m
elements, with certain rules for field addition and multiplication. The finite field GF(2
m
) has various basis representations including normal basis representation. A binary polynomial is a polynomial with coefficients in GF(2). A binary polynomial is irreducible if it is not the product of two binary polynomials of smaller degree. For simplicity, we will refer to such a polynomial an irreducible polynomial. Irreducible polynomials exist for every degree m and can be found efficiently. Let g(x) be an irreducible polynomial of degree m. If &bgr; is a root of g(x), then the m distinct roots of g(x) in GF(2
m
) are given by
B={&bgr;, &bgr;
2
, &bgr;
2
2
, . . . , &bgr;
2
m−1
}.
If the elements of B are linearly independent, then g(x) is called a normal polynomial and B is called a normal basis for GF(2
m
) over GF(2). Normal polynomials exist for every degree m. Given any element a &egr;GF(2
m
), one can write
a
=
∑
i
=
0
m
-
1
⁢
a
i
⁢
β
2
i
,
 
⁢
where
⁢
 
⁢
a
i
∈
{
0
,
1
}
.
In normal basis, field multiplication is generally carried out using a multiplication matrix, which is an m-by-m matrix M with entries in GF(2). Details on how to compute matrix M from g(x) are known in the prior art, e.g., A. Menezes et al., “Applications of Finite Fields,” Kluwer Academic Publishers, 1993, and IEEE Standard for Public-Key Cryptography, http://stdsbbs.ieee.org/groups/1363/index.html. Other details regarding conventional finite field arithmetic techniques can be found in, e.g., U.S. Pat. No. 4,587,627 issued May 6, 1986 to J. L. Massey and J. K. Omura, entitled “Computational method and apparatus for finite field arithmetic,” and G.B. Patent No. 2,176,325 issued Dec. 17, 1986 to R. C. Mullin, I. M. Onyszchuk, and S. A. Vanstone, entitled “Finite field multiplication in a cryptographic system—offsetting suffixes and rotating binary digits in respective shift registers so as to produce all product vector terms simultaneously” (related U.S. Pat. No. 4,745,568 was issued May 17, 1988).
Below, we describe a conventional normal basis multiplication formula in two slightly different formats. Let a=(a
0
a
1
. . . a
m−1
) and b=(b
0
b
1
. . . b
m−1
) be two elements. Then their product c=(c
0
c
1
. . . c
m−1
) can be computed one bit at a time as follows:
c
0
=(
a
0
a
1
. . . a
m−1
)
M
(
b
0
b
1
. . . b
m−1
)
T
c
1
=(
a
1
a
2
. . . a
0
)
M
(
b
1
b
2
. . . b
0
)
T
c
m−1
=(
a
m−1
a
0
. . . a
m−2
)
M
(
b
m−1
b
0
. . . b
m−2
)
T
  (1)
In formula (1), when a new coefficient c
k
needs to be computed, the coefficients of both a and b are rotated to the left by one bit. This allows efficient hardware implementations of normal basis multiplication.
In a typical “C” programming language implementation of formula (1), a, b, and columns of M are all stored in words. Each matrix-vector multiplication M(b
0
b
1
. . . b
m−1
)
T
can be carried out with (m/2)(m/w) exclusive-or operations on average, and hence the total number of word operations for computing c is about m(m/2) (m/w)=m
3
/2w. Note that the computation time is independent of the number of non-zero entries in M.
Let M
ij
denote the entries of matrix M. The following is another way of writing formula (1):
for k from 0 to m−1
c
k
=&Sgr;
i=0, . . . m−1
a
i+k
•(&Sgr;
j=0, . . . m−1
M
ij
•b
j+k
).  (2)
Throughout the description, the addition operation “+” in a subscript is to be understood as addition modulo the degree m, unless otherwise specified; the symbol “•” denotes AND; and the symbols “&Sgr;” and “⊕” denote exclusive-or. In formula (2), essentially the same expression is used for each coefficient c
k
. More specifically, given the expression for c
k
, we simply increase the subscripts of a and b by one (modulo m) and the result is the expression for c
k+1
.
Using formula (2), the fewer 1's in the multiplication matrix M, the faster a field multiplication can be done. An ONB is a normal basis which has the smallest number of 1's in the multiplication matrix M. There are two kinds of ONB, called type I ONB and type II ONB, that differ in the mathematical formulae which define them. For both types of ONB, the multiplication matrix has exactly 2m−1 non-zero entries. In particular, the first row has a single non-zero entry, and the rest of the rows have exactly two non-zero entries. In terms of formula (2), the total number of terms (of the form a
i
M
ij
b
j
) for each c
k
is 2m−1. ONBs only exist for certain values of degree m. For example, in the range [150, 200], there are only 15 values of m for which an ONB exists.
It is an object of the present invention to provide improved techniques for multiplication in a normal basis, which are particularly well suited for implementation in software, and can be applied to both general normal basis and ONB.
SUMMARY OF THE INVENTION
The invention provides improved techniques for implementing normal basis multiplication in processing systems and devices. The techniques are particularly well suited for implementation in software. Using the invention, the coefficients of a product of field elements can be computed one processor word at a time, e.g., 32 bits in a 32-bit processor, as opposed to one bit at a time as required by certain conventional approaches, thereby fully taking advantage of the fast word-based operations currently available in modern processors and software.
An illustrative embodiment of the invention includes a first rotator which receives a first input signal representative of a first normal basis field element (a
0
a
1
. . . a
m−1
), and a second rotator which receives a second input signal representative of a second normal basis field element (b
0
b
1
. . . b
m−1
). A word multiplier receives output sign

Affiliated with

Also associated with

Rating

Efficient finite field multiplication in normal basis does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient finite field multiplication in normal basis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient finite field multiplication in normal basis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2871529