US 7,069,287 B2Granted

Method for efficient computation of odd characteristic extension fields

AssigneeWorcester Polytechnic Institute

InventorsChristof Paar, Adam D Woodbury, Daniel V Bailey

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for implementing an elliptic curve or discrete logarithm cryptosystem on inexpensive microprocessors is disclosed which provides for advantageous finite field computational performance on microprocessors having limited computational capabilities. The method can be employed with a variety of commercial and industrial imbedded microprocessor applications such as consumer smart cards, smart cards, wireless devices, personal digital assistants, and microprocessor controlled equipment. In one embodiment, a Galois Field (GF) implementation based on the finite field GF((28−17)17) is disclosed for an Intel 8051 microcontroller, a popular commercial smart card microprocessor. The method is particularly suited for low end 8-bit and 16-bit processors either with or without a coprocessor. The method provides for fast and efficient finite field multiplication on any microprocessor or coprocessor device having intrinsic computational characteristics such that a modular reduction has a greater computational cost than double precision, long number additions or accumulations. The disclosed method offers unique computational efficiencies in requiring only infrequent subfield modular reduction and in employing an adaptation of Itoh and Tsujii's inversion algorithm for the group operation. In one embodiment, a core operation for a signature generation, an elliptic curve scalar multiplication with a fixed point, is performed in a group of order approximately 2134 in less than 2 seconds. In contrast to conventional methods, the method does not utilize or require curves defined over a subfield such as Koblitz curves.

Claims20

Dependent claims

A method for finite field multiplication of odd characteristic extension fields with a microcontroller comprising the steps of:

providing a microcontroller comprised of
a central processing unit (CPU) having an arithmetic and logical unit (ALU);
a multiplier module;
an addition module;
a division module;
and
memory locations comprising internal random access memory (RAM) and external random access memory (XRAM);
selecting a basis representation of field elements;
providing at least two field elements A and B in a field GF (pm) represented as m-tuples where p>2, m>1, A is represented as an first array of integer coefficients (a0, a1, . . . ai, . . . a(m−1)), B is represented as second array of integer coefficients (b0, b1, . . . bj, . . . b(m−1)) and the tuple coefficients ai and bj are elements of the field GF(p) where 0≦i, j≦(m−1);
storing said first array in a first memory location;
storing said second array in a second memory location;
multiplying the two field elements A and B with said multiplier module to produce a product C in a field GF (pm) where C is represented as a third array of integer coefficients (c0, c1, . . . ck, . . . c(m−1). and tuple coefficents ck are elements of the field GF(p) where 0≦k≦(m−1);
storing said third array in a third memory location;
computing m temporary coefficients ck′ as a sum of m intermediate products without an immediate modular reduction where
∑
0
m
-
1
⁢
c
k
′
=
∑
i
+
j
=
k
⁢
a
i
·
b
j
;
and said intermediate products ai·bj are computed with said multiplier module;
adding said intermediate products for each of temporary coefficient ck′ with said addition module;
storing said temporary coefficients ck′ in either a fourth memory location or said first, said second or said third memory locations;
computing m coefficients ck with said multiplier, addition and division modules by performing a single modular reduction on each of said temporary coefficients ck′;
and
storing the coefficients ck in either said first, said second, said third or said fourth memory location.

40 more elements

A system for finite field multiplication of odd characteristic extension comprising:

a microcontroller having memory locations comprising internal random access memory (RAM) and external random access memory (XRAM);
a basis representation of field elements;
at least two field elements A and B in a field GF (pm) represented as m-tuples where p>2, >m>1, A is represented as an first array of integer coefficients (a0, a1, . . . ai, . . . a(m−1)), B is represented as second array of integer coefficients (b0, b1, . . . bj, . . . b(m−1)) and the tuple coefficients ai and bj are elements of the field GF(p) where 0≦i, j≦(m−1);
a first memory location for storing said first array;
a second memory location for storing said second array;
a multiplier module for multiplying the two field elements A and B to produce a product C in a field GF (pm) where C is represented as a third array of integer coefficients (c0, c1, . . . ck, . . . c(m−1). and tuple coefficents ck are elements of the field GF(p) where 0≦k≦(m−1);
a third memory location for storing said third array;
a multiplier module for computing intermediate products ai·bj;
an addition model for computing m temporary coefficients ck′ as a sum of m intermediate products without an immediate modular reduction where
∑
0
m
-
1
⁢
c
k
′
=
∑
i
+
j
=
k
⁢
a
i
·
b
j
;
a fourth memory location for storing said temporary coefficients ck′;
an arithmetic module for computing m coefficients ck with said multiplier, addition and division modules by performing a single modular reduction on each of said temporary coefficients ck′;
and
a fifth memory location for storing the coefficients ck.

33 more elements

Dependencies are inferred from the claim text.