Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-16
2003-12-23
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06668267
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a device and method for the implementation of an elementary modular operation according to the Montgomery method. This method can be used to perform modular computations in a finite field (or Galois field) without performing divisions.
BACKGROUND OF THE INVENTION
Modular operations in finite fields are used in cryptography for applications such as the authentication of messages, the identification of a user and the exchange of keys. Exemplary applications of this kind are described, for example, in the European patent application FR-A-2,679,054.
There are commercially available integrated circuits dedicated to such applications, such as the product referenced ST16CF54, which is manufactured by STMicroelectronics S.A., the current assignee of the present invention. This product is built around a central processing unit and an arithmetic coprocessor for implementing modular computations. The coprocessor enables the processing of the modular multiplications by using the Montgomery method, which is the object of the European patent application EP-A-601,907.
The basic operation, called a P
field
operation, includes the use of three binary data elements A (multiplicand), B (multiplier lower than N) and N (modulo) encoded on an integer number of n bits to produce a binary data element referenced P(A, B)
N
encoded on n bits such that P(A, B)
N
=A*B*I mod N, with I=2
−n
mod N. For this purpose, it is assumed that the data elements are encoded on m words of k bits with m*k=n, and the words A and B are given to a multiplication circuit having a serial input, a parallel input and a series output.
For the coprocessor described in the above referenced European patent application EP-A-601,907, we have k=32 and m=8 or 16.
FIG. 1
shows the modular arithmetic coprocessor disclosed by the referenced patent application. This coprocessor includes the following elements:
three shift registers
10
,
11
and
12
, with m*k bits, designed to receive respectively the multiplier B, the result S and the modulo N;
multiplexers
13
to
15
that are respectively connected to the inputs of the registers
10
to
12
;
three k-bit shift registers
16
,
17
and
18
having one series input and one parallel output, designed to receive respectively k bits of the multiplicand A, a computation parameter referenced J
0
, an intermediate result referenced Y
0
;
two multiplication circuits
19
and
20
each having one series input, one parallel k-bit input and one series output;
two k-bit parallel latches
21
and
22
used as a buffer for the multiplication circuits
19
and
20
;
a multiplexer
23
used to connect the latch
22
either to the register
17
or to the register
18
;
three multiplexers
24
,
25
and
26
used to route the data elements to the inputs of the multiplication circuits
19
and
20
;
three subtraction circuits
27
,
28
and
29
each comprising two series inputs and one series output;
two addition circuits
30
and
31
, each having two series inputs and one series output;
three delay cells
32
,
33
and
34
that are actually k-bit shift registers and are used to delay the data elements by k clock cycles to mask the computation time of the multiplication circuits
19
and
20
;
a comparison circuit
35
;
two multiplexers
36
and
37
used to control the subtraction circuits
27
and
28
;
a multiplexer
38
; and
a demultiplexer
39
.
For further details on the making of these elements, reference may be made to the above referenced European patent application EP-A-601,907.
To perform an elementary operation called a P
field
operation of the P
field
(A, B)
N
=A*B*I mod N type, A and B are encoded on a number of m k-bit words and I is an error equal to 2
−m*k
, and the iteration of the next loop is performed m times with i being an index varying from 0 to m−1:
X=S(i−1)+Ai*B;
Y
0
=(X*J
0
) mod
2
k
;
Z=X+(N*Y
0
);
S(i)=Z/2
k
(an integer division);
if S(i) is greater than N, then N is subtracted from S(i) before the next iteration;
with S(−1)−0, Ai is the k-bit word with a place value i, and J
0
is a k-bit word defined by the equation ((J*Y
0
)+1) mod
2
k
=0.
The coprocessor of
FIG. 1
enables the performance of a full iteration by a simultaneous shift, by m*k bits, of the registers
10
to
12
respectively containing B, S(i−1) and N followed by a shift, by
2
*k bits, of the register
12
to store S(i). The word Ai is loaded into the register
21
and the word J
0
is loaded into the register
17
. To perform the full computation of P
field
(A, B)
N
, it is enough to repeat each iteration m times by changing the word Ai contained in the register
21
during each iteration.
The operation X=S(i−1)+Ai*B is done by the multiplication circuit
19
and the addition circuit
30
. The operation Y
0
=(X*J
0
) mod
2
k
is done, during the k first shifts, in the multiplication circuit
20
while storing J
0
in the register
22
and storing the result Y
0
in the register
18
. The operation Z=X+(N+Y
0
), with N and X having been delayed by k bits in the delay cells
32
and
34
and with Y
0
having been put into the latch
22
, is performed by the multiplication circuit
20
and the addition circuit
31
. The operation S(i)=Z/2
k
is done by a k-bit shift. The comparison of S(i) with N is done by the subtraction of N from S(i) in the subtraction circuit
29
. N is delayed by k bits in the delay cell
33
, and a possible overflow is detected and stored in the comparison circuit
35
to find out the result of the comparison. The subtraction of N from S(i) is done during the next iteration in the subtraction circuit
28
.
Many improvements have been made in this circuit. The improvements are aimed at obtaining higher speeds, reducing the size of the circuit, reducing the consumption of the circuit, and/or providing additional functions without considerably increasing the size of the circuit. Those skilled in the art may refer to the publications of the European patent applications EP-712,070, EP-712,071, EP-712,072, EP-778,518, EP-784,262, EP-785,502, EP-785,503, EP-793,165, EP-853,275, and also to the publication of the international patent application WO/97-25,668.
There is also another circuit known from the publication of the European patent application EP-566, 498 enabling the computation of the elementary operation P(A, B)
N
=A*B*I mod N, with I=2
−n
and n is the size of A, B or N. This circuit uses a single parallel/series multiplication circuit, in the form of a parallel adder coupled with a shift register.
The circuit does not produce exactly the Montgomery algorithm and uses an intermediate data element equal to N−1)/2+1. The circuit uses a multiplication circuit having a parallel input with n bits and is limited to computation operands with a permanently fixed size. Furthermore, the size of the circuit disclosed in the European patent application EP-566,498 is proportional to the size of the operands used. Consequently, the surface area thus occupied by the circuit is considerable.
SUMMARY OF THE INVENTION
The present invention is aimed at improving the prior art by providing a coprocessor that uses a single multiplication circuit coupled to a computation circuit dedicated to the computation of Y
0
, with Y
0
=(X*J
0
) mod
2
k
and J
0
being defined by the equation ((N*J
0
)+1) mod
2
k
=0. The invention also provides a method for the computation of a modular operation using the circuit for the computation of Y
0
.
An object of the invention is to provide an integrated circuit comprising a modular arithmetic coprocessor comprising:
storage means to store and provide, in series, first and second operands A and B, a modulo N and a result S with A as an integer encoded on a*k bits, a is a non-zero integer at most equal to m, and B, N and S are integers encoded on at most m*k bits, m and k are inte
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Do Chat C.
Jorgenson Lisa K.
Ngo Chuong Dinh
STMicroeletronics S.A.
LandOfFree
Device and method for the implementation of an elementary... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for the implementation of an elementary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for the implementation of an elementary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3095322