Method for the implementation of a specific modular...

Details Method for the implementation of a specific modular... Method for the implementation of a specific modular...

1999-02-19

2002-07-23

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06424987

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to the field of microprocessors, and, more particularly, to a modular arithmetic coprocessor.
BACKGROUND OF THE INVENTION
The Montgomery method makes it possible to carry out modular calculations 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 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 by using the Montgomery method. Further information on this coprocessor can be found in 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 of n 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 with m*k=n.
In the referenced U.S. Pat. No. 5,313,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 Pfield operations. 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.
The use of the coprocessor disclosed in the referenced U.S. patent enables optimizing in terms of computing duration, memory size, etc., of the processing of modular operations using a fixed data size, e.g., 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 form larger-sized 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 ever 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.
1
. 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
, a coprocessor
4
and a communications bus
5
used to connect the different elements
2
,
3
and
4
together and/or external to the circuit
1
. In circuit
1
of
FIG. 1
, 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 the 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 binary 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 element referenced as P(A, B)
N
, which is 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 m times:
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, and 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 for 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 large number of data exchanges between the coprocessor
4
and the memory
3
, and requires the memory
3
to be sized as a function of the data elements to be stored during intermediate computations. The European Patent 793,165, which corresponds to U.S. patent application having Ser. No. 08/806,456, explains how to perform non-modular multiplication operations and operations of the type S=A*B+C or S=A*B+C+D. A, B, C and D are encoded on Bt bits with Bt equal at most to m*k. S is encoded on 2*Bt bits.
If the Montgomery algorithm set up by means of elementary operations of the S=A*B+C+D type is developed, then the following loop repetition is obtained.
A) Computation of X=S
i
+A
i
*B for providing X
p
. . . X
0
=S
i,p−1
. . . S
i,0
+A
i
*B
p−1
. . . B
0
, with X
j
, S
i,j
and B
j
being the Bt bit words of X, S
i
and B. This is a result of the succession of the p computations made in the coprocessor
4
.
A
1
) X′
1
X
0
=S
i,0
+A
i
*B
0
+0
A
2
) X′
2
X
1
=S
i,1
+A
i
*B
1
+X′
1
. . .
Ap−1) X′
p−1
X
p−2
=Si,
p
−2+A
i
*B
p−2
+X′
p−2
Ap) X
p
X
p−1
=S
i,p−1
+A
i
*B
p−1
+X′
p−1
, with X′
1
to X′
p−1
being Bt bit words of intermediate computation that remain permanently in the coprocessor
4
.
B) Y
0
=(X*J
0
) mod 2
Bt
, for providing Y
0
=(X
p
. . . X
0
*J
0
) mod 2
Bt
by the following computation made in the coprocessor
4
: Y′
1
Y
0
=0+X
0
*J
0
+0. The least significant word Y
0
is the only one of interest.
C) Z=X+N*Y
0
, for providing Z
p
. . . Z
0
=X
p
. . . X
0
+Y
0
*N
p−1
. . . N
0
. Z
j
, X
j
and N
j
are the Bt bit words of Z, X and N using the following succession of p+1 computations made in the coprocessor
4
.
C
1
) Z′
1
Z
0
=X
0
+Y
0
*N
0
+0
C
2
) Z′
2
Z
1
=X
1
+Y
0
*N
1
+Z′
1
. . .
Cp−1) Z′
p−1
Z
p−2
=X
p−2
+Y
0
*N
p−2
+Z′
p−2
Cp) Z′
p
Z
p

Affiliated with

Also associated with

Rating

Method for the implementation of a specific 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 a specific modular..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the implementation of a specific modular... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2903256