Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-15
2003-12-02
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06658442
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is based upon and claims priority from prior French Patent Application No. 99-03409, filed Mar. 17, 1999, the entire disclosure of which is herein incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally 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.
Conventionally, modular operations in finite fields are used in cryptography for applications such as the authentication of messages, and the identification of a user or the exchange of keys. Exemplary applications of this kind are described for example in patent application FR-A-2 679 054 (hereinafter D1).
2. Description of Related Art
There are commercially available integrated circuits that are generally dedicated to such applications, for example the product manufactured by STMicroelectronics S.A. referenced ST16CF54 built around an association of the type comprising a central processing unit and an arithmetic coprocessor and generally dedicated to the implementation of modular computations. The coprocessor used enables the processing of the operations of modular multiplication by using the Montgomery method. It is the object of the patent application EP-A-0 601 907 (hereinafter D2).
The basic operation, called a Pfield operation, consists of the use of three binary data elements, A (multiplicand), B (multiplier lower than N) and N (modulo), encoded on an integer number n of 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 and k as integers such that 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 D2, we have k=32 and m=8 or 16.
FIG. 1
shows the modular arithmetic coprocessor disclosed by D2. This coprocessor comprises 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 D2.
To perform an elementary operation called a Pfield operation of the P
Field
(A, B)
N
=A*B*I mod N type, A and B being encoded on a number m of k-bit words and I being an error equal to 2
−m*k
, 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)+A
i
*B,
Y
0
=(X*J
0
)mod 2
k
,
Z=X+(N*Y
0
)
S(i)=Z2
k
, being 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, A
i
being the ith k-bit word of A, J
0
being a k-bit word defined by the equation ((N*J
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 A
i
being loaded into the register
21
and the word J
0
being 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 A
i
contained in the register
21
during each iteration.
The operation “X=S(i−1)+A*B” is done by means of 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
, in taking care to store J
0
in the register
22
, the result Y
0
being stored in the register
18
. The operation “Z=X+(N+Y
0
)”, N and X having been delayed by k bits in the delay cells
32
and
34
and Y
0
having been put into the register
22
, is performed by means of the multiplication circuit
20
and the addition circuit
31
. The operation “S(i)=Z2
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 being delayed by k bits in the cell
33
, a possible overflow being 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 and/or reducing the size of the circuit and/or 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, inter alia, to the publications of the European patent applications EP-0 712 070, EP-0 712 071, EP-0 712 072, EP-0 778 518, EP-0 784 262, EP-0 785 502, EP-0 785 503, EP-0 793 165, EP-0 853 275, and also to the publication of the international patent application WO/97 25668.
There is also another circuit known from the publication of the European patent application EP-0 566 498 (hereinafter D3) enabling the computation of the elementary operation P(A, B)
N
=A*B*I mod N, with I=2
−n
and n being the size of A, B or N. The circuit of D3 uses a single parallel/series multiplication circuit, represented in D3 in the form of a parallel adder coupled with a shift register. The circuit of D3 does not reproduce exactly the Montgomery algorithm and uses an intermediate data element equal to (N−1)/2+1. The circuit of D3 uses a multiplication circuit having an n-bit parallel input and is limited to computation operands with a permanently fixed size. Furthermore, the size of the circuit of D3 is proportional to the size of the operands used, the surface area thus occupied being considerable.
The present invention is aimed at improving the prior art by proposing 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
, J
0
being defined by the equation ((N*J
0
)+1)mod 2
k
=0. The computation of Y
0
is done according to the invention bit by bit, one clock half-cycle before the use of each bit. The invention also proposes a method for the computation of a modular operation using the circuit for the computation of Y
0
.
Thus, there is a need
Do Chat
Fleit Kain Gibbons Gutman Bongini & Bianco P.L.
Gutman Jose
Jorgenson Lisa K.
Ngo Chuong Dinh
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-3149409