Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-01-18
2001-03-13
Mai, Tan V. (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06202076
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a scheme for arithmetic operations in finite field and group operations over elliptic curves, and more particularly, to a computational scheme for arithmetic operations in finite fields such as GF(2
m
) which is to be utilized in realizing error correction coding (such as algebraic geometric coding) and information security technique (such as elliptic curve cryptosystem) including key distribution and authentication using group operations over elliptic curves.
2. Description of the Background Art
As a fast implementation of multiplicative inverse calculation in GF(2
m
), a scheme based on multiplication using a normal basis has been proposed by J. L. Massey and J. K. Omura (see U.S. Pat. No. 4,587,627). This scheme is based on the principle that, when the Fermat's little theorem over finite fields holds in a form of:
x
2m−1
=1 for an element
x
(≠0) of
GF
(2
m
)
it is possible to calculate multiplicative inverse in a form of:
x
1
=x
2n−2
Other schemes based on this same principle are also disclosed, for example, in Agnew et al.: “Arithmetic operations in GF(2
m
)”, Journal of Cryptology, Vol. 6, pp. 3-13, 1993, and P. C. van Oorschot, S. A. Vanstone: “A Geometric Approach to Root Finding in GF(q
m
), IEEE Transactions of Information Theory, Vol. 35, No. 2, pp. 444-453, March 1989.
Either scheme utilizes the fact that multiplication in GF(2
m
) can be efficiently realized by hardware by using a normal basis, and realizes multiplicative inverse calculation in GF(2
m
) as a combination of multiplication and shift (including rotate) operations in GF(2
m
). In the presently known algorithm, it is known that multiplications in GF(2
m
) are required for [log
2
m]+{the number of 1 in the binary representation of (m−1)}−1 times, bit shift operations are required for (m−1) times, and when GF(2
m
) is a quadratic extension of GF(2
m/2
), by the use of subfield in multiplicative inverse calculation in GF(2
m
), two multiplications in GF(2
m
) and one shift operation in GF(2
m/2
) constitute one multiplicative inverse calculation in GF(2
m/2
).
However, when this multiplication algorithm is straightforwardly implemented by software, there arises a problem of lowering of efficiency because of tedious bit unit handling.
For this reason, there is a known scheme for calculating multiplication in GF(2
m
) by using subfield (see A. Pincin: “A New Algorithm for Multiplication in Finite Fields”, IEEE Transactions on Computers, Vol. 38, No. 7, pp. 1045-1049, July 1989, for example).
In the case of realizing finite field arithmetic by software, because of the looser constraint on memory size compared with the case of hardware implementation, the fast implementation becomes possible by providing a table of calculation results obtained by preliminary calculations and reading out necessary information from the table subsequently. A very fast algorithm utilizing this fact is disclosed in E. De Win et al.: “A Fast Software Implementation for Arithmetic Operations in GF(2
n
)”, Advances in Cryptology—ASIACRYPT'96, Lecture Notes in Computer Science 1163, pp. 65-76, Springer-Verlag, 1996, for example.
Now, many secret key cryptosystems improve their security by iterating F functions several times. It is known that the security can be guaranteed by utilizing exponential calculations in F function (see K. Nyberg: “Differentially Uniform Mappings for Cryptography”, Advances in Cryptology—EUROCRYPT'93, Lecture Notes in Computer Science 765, pp. 55-64, Springer-Verlag, 1994, and K. Nyberg, L. R. Knudsen: “Provable Security Against a Differential Attack”, Journal of Cryptology, Vol. 8, pp. 27-37, 1995). In these references, it is recommended to construct F function by using cube calculations or multiplicative inverse calculations.
However, when conventionally used input data are represented by using a normal basis on prime field GF(2) and multiplicative inverse calculation in GF(2
2n
) is straightforwardly implemented by software using the algorithm of van Oorschot et al., there arises a problem of lowering of efficiency because of tedious bit unit handling.
Now, elements of a group E(K) of elliptic curves over a field K can be expressed in terms of either homogeneous coordinates formed by a set of three elements of K or affine coordinates formed by a set of two elements of K. Addition of E(K) can be calculated by arithmetic operations over field K in ether expression using homogeneous coordinates or affine coordinates.
In constructing a device for realizing group operations over elliptic curves, a field K can be chosen to be a finite field GF(q), and in particular, a finite field GF(2
n
) with characteristic
2
is often employed because it is possible to realize a fast implementation.
Among arithmetic operations over finite field, the very fast implementation is possible for addition and additive inverse by the conventional implementation scheme, but considerable time is required for calculating multiplication and multiplicative inverse (hereafter inverse refers to multiplicative inverse unless otherwise indicated). Consequently, a time required for addition of groups over elliptic curves can be evaluated by the required number of multiplication and inverse calculations over field K.
On the other hand, conventionally, inverse calculation over finite field with characteristic
2
requires an enormous amount of calculations compared with multiplication. For this reason, the conventional schemes for implementing group operations over elliptic curves are mainly the implementation using homogeneous coordinates which does not require inverse calculations, even though the required number of multiplication calculations becomes rather large (see A. J. Menczes, S. A. Vanstone: “Elliptic Curve Cryptosystems and Their Implementation”, Journal of Cryptology, Vol. 6, pp. 209-289, 1993, for example).
However, in recent years, a scheme for implementing inverse calculation in finite field with characteristic
2
has been developed, and schemes using affine coordinates for expressing elements of group over elliptic curves have been proposed, for example, in E. De Win et al.: “A Fast Software Implementation for Arithmetic Operations in GF(2
n
)”, Advances in Cryptology—ASIACRYPT'96, Lecture Notes in Computer Science 1163, pp. 65-76, Springer-Verlag, 1996. In the following, this scheme will be referred to as De Win's scheme.
Outline of the implementation of finite field according to the De Win's scheme is as follows. When a number of bits for basic operations of a processor is w (8 or 16, for example), all the operations over ground field are calculated in advance by using GF(2
w
) as ground field. Also, using an odd degree three term irreducible polynomial over GF(2) in a form of:
x
d
+x
t
+1(
d>t
),
operations in GF(2
wd
) are represented as:
GF
(2
wd
)≅
GF
(2
w
)[
x
]/(
x
d
+x
t
+1)
where a symbol ≅ denotes isomorphism of fields (see S. MacLane, G. Birkhoff: “Algebra”, Chelsea Publishing, 1967, for detail), and then using this representation, E(GF(2
wd
) is implemented. In the De Win's scheme, inverse calculation in finite field utilizes the extended Euclidean algorithm over GF(2
w
) which is the general inverse calculation method, and many multiplications and divisions are required in executing the extended Euclidean algorithm.
Note that finite fields with characteristic
2
are important because they have data structures suitable for computers, and they can be utilized in error correction coding and cryptography. Individual element of a finite field GF(2
n
) can be represented by using n-th degree irreducible polynomial f(X) over GF(2) as:
GF
(2
n
)≅
GF
(2)[
x
]/(
f
(
x
))
so that it can be represented by polynomial of (n−1)-th degree or less. In other words, by regarding coefficients GF(2) of polynomial as bits, GF(2
n
) can be represented In terms of n bits.
When suc
Aoki Kazmaro
Ohta Kazuo
Kilpatrick & Stockton
Mai Tan V.
Nippon Telegraph and Telephone Corporation
LandOfFree
Scheme for arithmetic operations in finite field and group... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheme for arithmetic operations in finite field and group..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheme for arithmetic operations in finite field and group... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452739