Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-02-04
2001-08-14
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06275837
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of computations, and, more particularly, to a modular computation according to the Montgomery method.
BACKGROUND OF THE INVENTION
Modular computations according to the Montgomery method are performed in a finite field, or Galois field, denoted as GF(2
n
). Conventionally, modular operations on GF(2
n
) are used in cryptography for applications, such as the authentication of messages, the identification of a user, and the exchange of cryptographic keys. Exemplary applications are described, for example, in the French Patent Application FR-A 2,679,054.
There are commercially available integrated circuits dedicated to such applications. These include, for example, the product referenced as ST16CF54, which is manufactured by SGS-THOMSON MICROELECTRONICS S.A. This product is built around a central processing unit and an arithmetic coprocessor, and is dedicated for performing modular computations. The coprocessor enables processing of modular multiplication operations using the Montgomery method, which is disclosed in U.S. Pat. No. 5,513,133.
The basic operation, called a P
field
operation, includes generation of a binary data element denoted as P(A, B)
N
and encoded on n bits, such that P(A, B)
N
=A*B*I mod N, with I=2
−n
mod N. The generation of the binary data element is based on three binary data elements A (multiplicand), B (multiplier) and N (modulus) encoded on a whole number of n bits. 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 of A and B are provided to a multiplication circuit having a series input, a parallel input, and a series output.
For the coprocessor described in the referenced U.S. patent application, k=32 and m=8 or 16.
FIG. 1
shows the modular arithmetic coprocessor disclosed in the referenced U.S. patent application. This coprocessor has the following elements. Three m*k bit shift registers
10
,
11
and
12
, including one series input and one series output. These shift registers
10
-
12
receive respectively the multiplier B, the result S and the modulus N. A multiplexer
13
with three series inputs includes one series output connected to the input of the register
10
. A first input is connected to a first input terminal, and a second input is connected to the output of the register
10
. A multiplexer
14
with two series inputs has one series output connected to the input of the register
11
. A first input is connected to a logic 0.
The coprocessor further includes a multiplexer
15
having three series inputs and one series output connected to the input of the register
12
. A first input is connected to a second input terminal, and a second input is connected to the output of the register
12
. Three k-bit shift registers
16
,
17
and
18
have one series input and one parallel output. These registers
16
-
18
receive respectively k bits of the multiplicand A, a computation parameter referenced J
0
, and an intermediate result referenced Y
0
. The input of the register
17
is connected to a third input terminal. Two multiplication circuits
19
and
20
each have a series input, a k-bit parallel input and a series output. Two k-bit registers
21
and
22
have a parallel input and a parallel output. The input of the register
21
is connected to the output of the register
16
. The output of the register
21
is connected to the input of the multiplication circuit
19
. The output of the register
22
is connected to the input of the multiplication circuit
20
.
Furthermore, the coprocessor includes a multiplexer
23
with two parallel inputs and one parallel output. A first input of the multiplexer
23
is connected to the output of the register
17
. A second input of the multiplexer
23
is connected to the output of the register
18
. The output of the multiplexer
23
is connected to the input of the register
22
. Two multiplexers
24
,
25
each have two series inputs and one series output. The output of the multiplexer
24
is connected to the input of the register
16
. A first input of the multiplexer
24
is connected to a fourth input terminal. The output of the multiplexer
25
is connected to the series input of the multiplication circuit
19
. A first input of the multiplexer
25
is connected to a logic 0.
A multiplexer
26
has three series inputs and one output. The output is connected to the series input of the multiplication circuit
20
, and a first input is connected to a logic 0. Three subtraction circuits
27
,
28
and
29
each include two series inputs and one series output. The first input of the circuit
27
is connected to the output of the register
10
. The output of the circuit
27
is connected to each of the second inputs of the multiplexers
24
and
25
and also to an output terminal. The first input of the circuit
28
is connected to the output of the register
11
. Two addition circuits
30
and
31
each have two series inputs and one series output. The first input of the circuit
30
is connected to the output of the circuit
28
. The second input of the circuit
30
is connected to the output of the circuit
19
. The output of the circuit
30
is connected to a second input of the multiplexer
26
. The output of the circuit is connected to a first input of the circuit
29
, and to a second input of the multiplexer
14
, and to each of the third inputs of the multiplexers
13
and
15
.
Three delay cells
32
,
33
and
34
, which are actually k-bit shift registers, have a series input and a series output. The output of the cell
32
is connected firstly to a third input of the multiplexer
26
and secondly to the input of the cell
33
. The output of the cell
33
is connected to a second input of the circuit
29
. The input of the cell
34
is connected to the output of the circuit
30
. The output of the cell
34
is connected to a first input of the circuit
31
. A comparison circuit
35
has two series inputs and two outputs. A first input is connected to the output of the circuit
31
. A second input is connected to the output of the circuit
29
.
Two multiplexers
36
and
37
each have two series inputs, one selection input, and one output. Each of the first series inputs is connected to a logic 0. Each of the selection inputs is connected to one of the outputs of the circuit
35
. The output of the multiplexer
36
is connected to a second input of the circuit
27
. The output of the multiplexer
37
is connected to a second input of the circuit
28
. A multiplexer
38
has two inputs and one output. A first input is connected to a logic 1. A second input is connected to the output of the register
12
. The output is connected firstly to the input of the cell
32
, and secondly to the second inputs of the multiplexers
36
and
37
. A demultiplexer
39
has one input and two outputs. The input is connected to the output of the circuit
20
. A first output is connected to the input of the register
18
. A second output is connected to a second input of the circuit
31
.
For further details on forming certain elements, reference may be made to the previously referenced U.S. patent. To carry out an elementary operation known as a P
Field
operation of the type P
Field
(A, B)
N
=A*B*I mod N, with A and B encoded on m words of k bits, and I is an error equal to 2
−m*k
, iteration of the following loop is performed m times with i as an index varying from 1 to m:
X=S(i)+A
i−1
*B,
Y
0
=(X*J
0
)mod2
k,
Z=X+(N*Y
0
),
S(i)=Z\2
k
\ is an integer division, if S(i) is greater than N, then N is subtracted from S at the next iteration, with S(0)=0, A
i
is the k bit word with the significance i, J
0
is 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 of m*k bits of the registers
10
-
12
respectively containing B, S(i−1) and N. This is foll
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Galanthay Theodore E.
Mai Tan V.
STMicroelectronics S.A.
LandOfFree
Method for the implementation of an elementary modular... 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 for the implementation of an elementary modular..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the implementation of an elementary modular... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444571