Circuit for multiplication in a Galois field

Details Circuit for multiplication in a Galois field Circuit for multiplication in a Galois field

2000-01-14

2003-06-17

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06581084

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
This application is based upon and claims priority from prior French Patent Application No. 99-00472, filed Jan. 15, 1999, the entire disclosure of which is herein incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to circuits for multiplication in a Galois field, and more specifically to a multiplication circuit for performing multiplication operations in the GF(2
n
) Galois field generated by a generator polynomial.
2. Description of Related Art
Galois fields are finite sets of elements on which the mathematical operations are defined differently. The Galois field GF(2
n
) is a field having N elements, with N=2
n
. One representation of this field is the polynomial representation. All of the elements are written in the form of an n−1 degree polynomial:
a
n−1
X
n−1
+a
n−2
X
n−2
+ . . . +a
2
X
2
+a
1
X+a
0
with a
1
being a coefficient belonging to GF(2) and therefore being equal to either “0” or “1”. Consequently, each element can be likened to a number encoded on n bits.
The computations performed on the different elements correspond to computations made on polynomials reduced by an irreducible n
th
degree polynomial. The computations done on the numbers encoded on eight bits representing the elements of the field operate differently than the conventional operations. In particular, the addition of two elements is done bit-by-bit using an XOR circuit. The subtraction is done identically to the addition. The multiplication is done in two steps. In a first step, a multiplication similar to a normal multiplication is done, and then in a second step, a reduction is done using a generator polynomial.
Galois fields are used in digital transmission to generate either error correction codes or encryption codes. Among the encryption codes, there is the encryption known as elliptic curve encryption. This type of encryption uses binary numbers encoded on a large number of bits (typically, 100 to 200 bits). The computation circuits that are currently used for performing operations in Galois fields are conventional processors, possibly coupled with dedicated circuits. When a conventional processor is used, it is hard to optimize the computation time. On the other hand, dedicated circuits takes up more space and consumes more energy.
SUMMARY OF THE INVENTION
In view of these drawbacks, it is an object of the present invention to overcome the above-mentioned drawbacks and to integrate a specific multiplication circuit in a standard processor without substantially increasing the size of the processor.
Another object of the present invention is to provide an accumulation multiplication circuit that enables multiplication operations to be performed both conventionally and in Galois fields.
One embodiment of the present invention provides a multiplication circuit with an accumulator. The multiplication circuit includes first latch circuits, second latch circuits, and elementary adders that are cascade-coupled to one another in series through the first latch circuits. Each of the adders has its carry output coupled to one of its inputs through one of the second latch circuits. Additionally, the multiplication circuit includes cancellation circuitry for canceling the contents of each of the second latch circuits at least during selected multiplication operations so as to carry out multiplication operations in a Galois field. In some preferred embodiments, the cancellation circuitry includes a logic gate that receives a selection signal indicating the mode of operation, and the logic gate sets and holds the second latch circuits at zero when the selection signal indicates that the multiplication operation is to be done in a Galois field. In other preferred embodiments, the cancellation circuitry includes logic gates that are each associated with a pair formed by one of the adders and the associated second latch circuit.
Another embodiment of the present invention provides a method for performing a multiplication operation in a Galois field using a multiplication circuit with an accumulator. The multiplication circuit includes elementary adders that are cascade-coupled to one another in series through first latch circuits. According to the method, for each adder, a carry output of the adder is coupled to one of the inputs of the adder through a second latch circuit. The carry value stored in each of the second latch circuits is canceled when carrying out a multiplication operation in a Galois field.
Other objects, features, and advantages of the present invention will become apparent from the following detailed description. It should be understood, however, that the detailed description and specific examples, while indicating preferred embodiments of the present invention, are given by way of illustration only and various modifications may naturally be performed without deviating from the present invention.


REFERENCES:
patent: 4797848 (1989-01-01), Walby
patent: 6138134 (2000-10-01), Matsuo
patent: 6151939 (2000-11-01), Jeong
patent: 6230179 (2001-05-01), Dworkin et al.
patent: 6349318 (2002-02-01), Vanstone et al.
patent: 19644688 (1998-04-01), None
patent: WO 98 48345 (1998-10-01), None

Affiliated with

Also associated with

Rating

Circuit for multiplication in a Galois field does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3152591