Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-11-12
2001-05-08
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06230178
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to modular computations and, more particularly, to a method for the production of an error correction parameter associated with the implementation of a modular operation according to the Montgomery method.
BACKGROUND OF THE INVENTION
Modular computations in a finite field, or Galois field, are denoted as GF(2
n
). Modular operations on GF(2
n
) are used in cryptography for various applications, such as authentication of messages, identification of a user, and exchange of keys. Exemplary applications are described in the French Patent Application No. 2 679 054.
Integrated circuits dedicated to such applications are commercially available. For example, one such integrated circuit is manufactured by SGS-THOMSON MICROELECTRONICS S.A. and is built around a central processing unit and an arithmetic coprocessor. This product has a reference designation of ST16CF54 and is dedicated to the performance of modular computations. The coprocessor enables the processing of modular operations using the Montgomery method. Further information on this coprocessor can be found in European Patent Application No. 0 601 907 A2.
FIG. 1
shows a modular arithmetic coprocessor according to the prior art. This figure corresponds to
FIG. 2
of the European application.
The basic operation of modular computations according to the Montgomery method is known as the P
field
method. In this method, three binary data elements A (multiplicand),
13
(multiplier) and N (modulo) are encoded on an integer number of n bits which is used to produce a binary data element referenced as P(A, B)
N
. This binary data element is encoded on n bits such that P(A, B)
N
=A*B*I mod N, where I is an error due to the Montgomery method. The Montgomery method uses a k-bit computation base and analyzes the n-bit words into m words of k bits, such that m*k>n>(m−1)* k. The Montgomery method operates as follows, with i being an index varying from 0 to m−1:
X=S
i
+A
i
*B;
Y
0
=(X*J
0
) mod 2
k
;
Z=X+(N*Y
0
);
S
i+1
=Z\2
k
, \ being an integer division;
if S
i+1
is greater than N, then N is subtracted from S
i+1
at the next iteration;
A
i
corresponds to a k-bit word of the binary date element A;
S
i
corresponds to an updated result of the P
field
operation; and
S
m
=P(A, B)
N
=A*B*I mod N.
To obtain a modular multiplication A*B mod N, it is necessary to eliminate the error I. Error I is known and equals 2
−m*k
. To eliminate the error I, a second P
field
operation is performed: P(S
m
, H)
N
, where H is a binary data element encoded on m words of k bits and equals 2
2m*k
mod N. The generation of a parameter H can be done by successive subtractions by a computation coprocessor such as the one described in the European application. It is also possible to combine successive subtractions and P
field
operations to compute H as disclosed in the European Patent Application EP-A-0 712 070.
When modular multiplications are performed with data elements of variable size, the value of H may assume different values as a function of the sizes of A, B and N. In general, H has the value
2
x
mod N, with x and N being non-zero integers. This is explained in the European Patent Application EP-A-712 071.
Furthermore, the coprocessor is also used to perform computations on operands with sizes greater than the maximum size of the registers of the coprocessors. The European Patent Document EP-A-0 785 502 discloses a successive subtraction circuit for processing values of N having a size twice that of the registers of the coprocessor.
SUMMARY OF THE INVENTION
A computation circuit performs successive subtractions while operating twice as fast as prior art circuits performing the same computation. A corresponding method enables the performance of modular computations in a finite field (or Galois field), denoted as GF(2
n
), without having to perform divisions.
An objective of the invention is to provide a modular arithmetic coprocessor comprising a circuit for the computation of an error correction parameter H=2
x
mod N associated with the Montgomery method, with x and N being non-zero integers. The computation circuit comprises a first shift register to hold intermediate values of H and a second register to hold N. The computation circuit further comprises first means for the series subtraction of either zero, N, twice N, or three times N from the contents of the first register. A multiplication circuit multiples by four the result provided by the first means. Second means are used to ascertain whether the result provided by the multiplication circuit is greater or smaller than N, twice N, or three times N. A third means produces twice N and three times N. The computation circuit further comprises third and fourth k-bit registers to process data elements of a size twice that of the registers.
Another objective of the invention is to provide a method for producing an error correction parameter H=2
x
mod N in a modular arithmetic coprocessor. This error correction parameter is associated with the Montgomery method, with x and N being non-zero integers. An intermediate value of H is stored in a first: register and N is stored in a second register. Either zero, N, twice N or three times N is subtracted in series from the contents of the first register. The result of this subtraction is multiplied by four to obtain a new intermediate value of H. The new intermediate value of H is compared with N, twice N, and three times N. Twice N and three times N are produced permanently from N.
It is possible to have alternative embodiments of the invention corresponding to the different cases that arise. These alternative embodiments can be combined with the teachings of the referenced European patent applications.
REFERENCES:
patent: 3684879 (1972-08-01), Koehler
patent: 4989173 (1991-01-01), Kaneda
patent: 5724279 (1998-03-01), Benoloh et al.
patent: 5751620 (1998-05-01), Monier
patent: 5764554 (1998-06-01), Monier
patent: 5777916 (1998-07-01), Monier
patent: 5793659 (1998-08-01), Chen et al.
patent: 5793660 (1998-08-01), Rentschler
patent: 5912904 (1999-06-01), Monier
patent: 5928315 (1999-07-01), Kobayashi et al.
patent: 0 785 502 A1 (1996-12-01), None
R.G. Saltman, “Reducing Computing Time for Synchronous Binary Division, ” IRE Transactions on Electronic Computers, vol. EC-10, No. 2, Jun. 1961, pp. 169-174.
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Galanthay Theodore E.
Malzahn David H.
STMicroelectronics S.A.
LandOfFree
Method for the production of an error correction parameter... 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 production of an error correction parameter..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the production of an error correction parameter... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2522661