Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-02-19
2002-01-22
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S491000
Reexamination Certificate
active
06341299
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of microprocessors, and, more particularly, to a modular arithmetic coprocessor that performs non-modular operations.
BACKGROUND OF THE INVENTION
The Montgomery method makes it possible to carry out modular computations in a finite field (or Galois field) denoted as GF(2
n
), without the performance of divisions. Conventionally, modular operations on GF(2
n
) are used in cryptography for applications such as authentication of messages, identification of a user, and exchange of cryptographic keys. Exemplary applications are described in the French Patent Application No. 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. This product is built around a central processing unit and an arithmetic coprocessor, and is dedicated to the performance of modular computations. The coprocessor enables the processing of modular multiplication operations using the Montgomery method. Further information on this coprocessor can be found in the U.S. Pat. No. 5,513,133.
The basic operation, called a P
field
operation, is implemented by this coprocessor. Three binary data elements A (multiplicand), B (multiplier), and N (modulo) are encoded on a whole number n of bits. This is done for a binary data element denoted as P
field
(A, B)
N
which is encoded on n bits such that P
field
(A, B)
N
=A*B*I mod N. I is a binary data element, called an error, which is encoded on n bits such that I=2
−n
mod N. More specifically, the value of I depends on the number of k bit blocks considered for the encoding of A, with k being an integer. To perform the operation A*B*I mod N, the data elements are assumed to have been encoded on m words of k bits, with m and k being integers and m*k=n. The words of the data elements A and B are provided to a multiplication circuit having a series input to receive B, a parallel input to receive the k bit blocks of A, and a series output.
In the referenced U.S. Pat. No. 5,513,133, the coprocessor operates with k=32 and m=8 or 16. The coprocessor may be used to produce the result of the modular multiplication A*B mod N. The modular multiplication can be subdivided into two successive elementary P
field
operations. P
field
(P
field
(A, B)
N
, H)
N
is computed with H being a data element encoded on n bits, called an error correction parameter, which is equal to 2
2n
mod N. For further details on the implementation of modular multiplication, reference may be made to the above referenced U.S. patent. Several possibilities of computation are already known. They include the use either a software method or a specialized circuit, such as the one illustrated in the referenced U.S. patent.
The circuit illustrated in
FIG. 1
includes three shift registers
10
,
11
and
12
with a series input and output. These registers include n number of cells, with n=m*k. Multiplexers
13
,
14
and
15
are placed respectively before the inputs of the registers
10
,
11
and
12
. The circuit also includes three registers
16
,
17
and
18
with a series input and a parallel output, with each register having k cells. Two multiplication circuits
19
and
20
include a series input, a parallel input, and a series output. The circuit further includes two k-cell registers
21
and
22
, multiplexers
24
,
25
,
26
,
36
,
37
and
38
, a demultiplexer
39
, series subtraction circuits
27
,
28
and
29
, series addition circuits
30
and
31
, delay cells
32
,
33
and
34
to delay the propagation of binary data elements by k cycle periods, and a comparison circuit
35
. For further details on the arrangements of the different elements with respect to each other, reference may be made to the referenced U.S. patent.
The use of the circuit shown in
FIG. 1
enables optimizing in terms of computing duration, memory size, etc. of the processing of modular operations using a fixed data size, e.g., in this case 256 or 512 bits. Cryptography requires machines with increasingly high performance levels, operating at increasingly high speeds, and using increasingly complex cryptographic keys. The trend is towards the manipulation of data elements encoded on 768, 1024, 1536 and even 2048 bits. To process data elements of this size, it may be necessary to construct larger-size circuits by adapting the elements of the circuit to the sizes of the data.
This approach may raise problems in applications such as chip cards, wherein the size of the circuit is physically limited because of differences in mechanical bending stresses between the cards and the silicon substrates. Furthermore, it is becoming increasingly necessary to integrate larger numbers of different functional elements in a card of this kind. The space available for an encryption circuit is thereby correspondingly reduced. Approaches therefore need to be found to limit the increase in the size of this circuit while, at the same time, enabling optimum operation for data elements with a size greater than the size of the initially planned registers.
To carry out modular operations using operands with a size greater than that managed by the coprocessor, it is possible to use the circuit
1
shown in FIG.
2
. In practice, the maximum size is equal to the size of the registers. Circuit
1
includes a standard processor
2
(8, 16 or 32 bits), a memory
3
, the coprocessor
4
of
FIG. 1
, and a communications bus
5
used to connect the different elements
2
,
3
and
4
together and/or external to the circuit
1
. In the circuit of
FIG. 2
, the coprocessor
4
is used as a multiplier operating on m*k bits, which is conventionally 256 or 512 bits. The processor
2
is used, in particular, to supervise operations to be performed according to a particular encryption algorithm, and the data exchanges between the memory
3
and the coprocessor
4
.
Performance of the basic operation of modular computations according to the Montgomery method, known as the P
field
operation, is based upon three binary data elements. These data elements are A (multiplicand), B (multiplier) and N (modulo), which are encoded on a whole number of n bits. They are used for the production of a binary data referenced as P(A, B)
N
encoded on n bits such that P(A, B)N=A*B*I mod N. I is an error due to the Montgomery method. Should n have a size greater than the size of the registers, namely m*k, it is appropriate to subdivide n into p words of Bt bits. Bt is a working base with a size smaller than or equal to m*k, e.g., m*k. The Montgomery method operates as follows. The variable i is an index varying from 0 to m−1, and the following computation loop is repeated:
X=S
i
+A
i
*B,
Y
0
=(X*J
0
) mod 2
Bt
,
Z=X+(N*Y
0
),
S
i+1
=Z\2
Bt
, \ is a whole number division,
if S
i+1
is greater than N, then N is subtracted from S
i+1
,
A
i
corresponds to a word of Bt bits of the breakdown of A, and
S
i
corresponds to an updated result of the P
field
operation, and S
m
=P(A, B)
N
=A*B*I mod N.
A computation method of this kind requires a larger number of data exchanges between the coprocessors
4
and the memory
3
. The coprocessor
4
of
FIG. 1
can carry out only simple operations of multiplication such as A*B=S. A and B are encoded on Bt bits and S is encoded on 2*Bt bits. One approach proposed in U.S. Pat. No. 5,987,489 includes the coprocessor
4
performing an operation of the type S=A*B+C, in which A, B and C are encoded on Bt bits, and S is encoded on 2*Bt bits.
FIG. 3
shows a coprocessor
4
according to the referenced U.S. Pat. No. 5,987,489. The coprocessor
4
illustrated in
FIG. 3
includes three shift register
110
,
111
and
112
with serial a input and a serial output. These registers include a number of n cells, and n=m*k, where n, m and k are integers. A multiplexer
113
includes thr
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Jorgenson Lisa K.
Malzahn David H.
STMicroelectronics S.A.
LandOfFree
Modular arithmetic coprocessor enabling the performance of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modular arithmetic coprocessor enabling the performance of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular arithmetic coprocessor enabling the performance of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2852858