Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-07-20
2003-08-19
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S523000
Reexamination Certificate
active
06609142
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to electronic circuits, and more specifically to a circuit and method for performing multiplication with accumulation in a Galois Field.
2. Description of Related Art
GF(2
k
) is the field of polynomials of degree k−1 at the most with coefficients over {0,1}. Galois Fields are examples of finite element sets on which mathematical operations are defined differently. The Galois Field GF(2
k
) is a field which comprises k elements, with k=2
k
. A representation of this field is the polynomial representation. All the elements can be expressed in the form of a polynomial of degree k−1: P(x)=a
k−1
x
k−1
+a
k−2
x
k−2
+ . . . a
2
x
2
+a
1
x+a
0
, with a
i
being a coefficient belonging to GF(2), and thus equal to either “0” or “1”. Consequently, each element can be assimilated to a number coded on k bits. This causes the calculations performed on the different elements to correspond to calculations performed on polynomials reduced using an irreducible polynomial of degree k.
Galois Fields can be used in digital transmissions to produce error correction codes or as mathematical structures serving as a support for implementing cryptographic systems. An example of encryption codes is the elliptic curve encryption. This type of encryption uses binary numbers coded on a large number of bits (typically 150 to 200 bits). The calculation devices used at present are classical processors, and in some cases are coupled to dedicated circuits. If a conventional processor is used, the calculation time is difficult to optimize. On the other hand, the use of dedicated circuits is more cumbersome and consumes more energy.
With Galois Fields, the calculations performed on numbers coded on k bits representing the elements of the field are carried out differently from usual addition and multiplication operations. Thus, the addition of two elements is carried out bit by bit using an exclusive OR logic circuit. A subtraction is carried in an identical manner as for an addition. A multiplication is performed in two stages: in a first stage a multiplication similar to the multiplication of two polynomials is performed, then in a second stage a reduction using an irreducible polynomial of degree k is performed.
Another operation frequently used in a Galois Field is a “multiplication with accumulation”, which is denoted as Xmac. This operation, which calls for three items of data A, B and C, is defined as follows: Xmac(A,B,C)=A×B+C, where the symbol “x” denotes multiplication in the sense of the arithmetic of polynomials with coefficients on GF(2), and where the symbol “+” denotes addition in the sense of the arithmetic of a Galois Field.
Conventionally, the data A, B and C are coded on a same number of bits. Thus, if A and B are coded on n bits, an electronic circuit for carrying out the multiplication in the sense of the arithmetic of a Galois Field would comprise n accumulation latches, n adders, and so on. Accordingly, the size of circuits suitable for carrying out operations in a Galois Field depends directly on the size (i.e., the number of bits) of the numbers that involved in the different operations.
FIG. 1
is a block diagram showing a conventional circuit for performing multiplication operation with accumulation in a Galois Field. As mentioned above, three items of data A, B and C are used in a multiplication operation with accumulation. The first data A is stored in a first input register Areg, the second data B is stored in a second input register Breg, and the third data C is stored in a third input register Creg. The data A, B, and C have a size of 2 n bits. The first, second, and third input registers Areg, Breg, and Creg are preferably registers capable of containing 2 n bits. They can, however, have a different size, provided their size is sufficient to contain the data A, B, and C. The different registers can belong to a common memory unit or to separate memory units.
A circuit
10
for multiplication in a Galois Field receives the data A and B, which are respectively conveyed by a first data bus
12
and by a second data bus
14
from the input registers Areg and Breg. The circuit
10
for multiplication in a Galois Field performs a multiplication, in accordance with the arithmetic of a Galois Field, of the first data A and the second data B. The result of this multiplication, which is output by the multiplication circuit
10
, is a number coded on
4
n bits. This result is sent to a logic circuit
18
by a third data bus
16
. The logic circuit
18
carries out the addition, in accordance with the arithmetic of a Galois Field, of the result of the multiplication in the Galois Field and the third data C stored in third register Creg. In particular, the third data bus
20
sends the 2 n bits coding the number C to the logic circuit
18
. Generally, the logic circuit
18
is a two input exclusive OR (ex-OR) gate.
The result of the addition, in the sense of the arithmetic of a Galois Field, performed by the logic circuit
18
is a number coded on 4 n bits. The 2 n lowest weight bits (i.e., least significant bits) of the result of the addition operation are stored in a first output register LSW (less significant word) and the 2 n highest weight bits (i.e., most significant bits) of the result of the operation are stored in a second output register MSW (most significant word).
As mentioned above, the size of the circuit
10
for multiplication in a Galois Field depends directly on the size of the numbers which must be multiplied. It is common, for example in encryption operations of the elliptical curve type, to have to perform multiplications of numbers coded on 32 bits. The size of the multiplication circuit
10
is then quite considerable and it becomes too costly to implement because of the size of the required multiplication circuit.
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 provide a method for performing multiplication with accumulation in a Galois Field using a multiplication circuit that is not extremely large, and therefore not overly costly. A specific chain of successive operations is performed which makes it possible to replace multiplication between two numbers of 2 n bits by two multiplications between one number of 2 n bits and one number of n bits. Thus, The multiplication circuit required to implement the operation (i.e., which must perform multiplications between a number of 2 n bits and a number of n bits) is reduced in size by approximately two. More specifically, in the circuit for performing such a multiplication, the 2 n accumulation latches, 2 n adders, and so on are replaced by n accumulation latches and n adders.
One embodiment of the present invention provides a method is provided for performing multiplication with accumulation in a Galois Field on a first data, a second data, and a third data, with each of the data being coded on 2 n bits. According to the method, a first multiplication, in the sense of the arithmetic of a Galois Field, is performed on the first data and the n lowest weight bits of the second data to produce a first intermediate result coded on 3 n bits, and a first addition, in the sense of the arithmetic of a Galois Field, is performed on the third data and the first intermediate result to produce a second intermediate result on 3 n bits. A second multiplication, in the sense of the arithmetic of a Galois Field, is performed on the first data and the n highest weight bits of the second data to produce a third intermediate result on 3 n bits, and a second addition, in the sense of the arithmetic of Galois Field, is performed on the 2 n highest weight bits of the second intermediate result and the third intermediate result to produce a fourth intermediate result coded on 3 n bits. In a preferred embodiment, the 2 n highest weight bits of the second intermediate resu
Bongini Stephen
Fleit Kain Gibbons Gutman & Bongini P.L.
Jorgenson Lisa K.
Malzahn David H.
Stmicroelectronics S.A.
LandOfFree
Method of performing multiplication with accumulation in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of performing multiplication with accumulation in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of performing multiplication with accumulation in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3109250