Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-31
2001-05-22
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06237015
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of modular operations, and, more particularly, to the generation of a computation parameter used in the implementation of modular operations according to the Montgomery method.
BACKGROUND OF THE INVENTION
Modular operations according to the Montgomery method enable the performance of modular computations in a finite Galois field without carrying out any division. The finite Galois field is denoted as GF(2
n
), with 2
n
elements. These operations are applicable to cryptography for the authentication of messages, the identification of a user, and the 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, e.g., the product ST16CF54 made by SGS-THOMSON Microelectronics. To carry out modular computations, a dedicated arithmetic coprocessor is used as described in the European patent application No. 601,907. In the implementation of modular operations by the dedicated coprocessor, it is necessary to produce a binary parameter J0 encoded on an integer number Bt of bits, such that [(J0+N0)+1]mod 2
Bt
=0 with N0 as an odd integer number encoded on Bt bits and mod representing the modulo.
Methods have already been proposed by the assignee of the present invention to produce the parameter J0 using a dedicated circuit, thus enabling this parameter to be computed at a high speed in an integrated circuit. These methods are described in the European patent application 0 778 518 published on Jun. 11, 1996. This application corresponds to the patent application filed Dec. 3, 1996 in the United States under number Ser. No. 08/759,892. An important factor in the performance of modular operations is the computation time needed to produce the desired result.
SUMMARY OF THE INVENTION
The invention provides a higher speed method for generating in an integrated circuit a parameter J0 associated with implementation of modular operations according to the Montgomery method. J0 is encoded on Q*L bits such that J0=J0
L−1
. . . J0
0
, with Q and L being integers. The method comprises the following steps:
Step 1: The loading of a binary data element N0 encoded on Q*L bits is performed. The least significant bit of N0 is equal to 1 in a first register. The loading of Q*L zeros in the second and third register, and the loading of L zeros in a fourth register are performed.
Step 2: A loop of Q iterations is formed, which comprises the following steps, indexed by j, with j varying from 0 to Q−1:
Step 2.1: Forming a loop of L iterations, indexed by i with i varying from 0 to L−1, and comprising the steps of shifting the contents of the fourth register by one unit towards the right. This operation corresponds to a division by two of the contents of this register while overlooking the remainder. The bit derived from this shift is tested in a test circuit. If the bit checked is a 1, the following steps are performed. A rightward shifting is performed for the contents of the third register by one unit towards the right and a zero is loaded. This is done on the most significant bit of the third register and in a fifth register. The bit-by-bit addition of the contents of the fourth register with a zero in a first adder is performed. An output of this first adder is connected to the input of the fourth register. The testing of a second least significant bit at an output of the first adder is performed.
If the bit checked is not a 1, the following steps are performed. A rightward shifting of the contents of the third register by one unit towards the right is performed. The loading of a 1 on the most significant bit of the third register and in the fifth register is performed. The bit-by-bit addition of the contents of the fourth register and the L last bits of the first register in the first adder is performed. The output of this first adder is provided to the input of the fourth register. The first register forms an L bit register whose input and output are provided, and the second least significant bit at an output of the first adder is tested.
Step 2.2: The contents of the entire first register are shifted and the multiplication, in a multiplication circuit, of the contents of the first register by the contents of the fifth register is performed. The fifth register is replenished with logic zeros if its size is greater than L. The shifting of the contents of the second register and the addition of these contents with the result of the multiplication, encoded on Q*L+L bits, is performed in a second adder. The Q*L most significant bits of the binary data element produced by the second adder are stored in the second register. The L least significant bits of these Q*L bits are stored in the fourth register.
According to one mode of operation, the step 2.2 is performed as follows. During the Q−1 first iterations, the shifting of the contents of the entire first register and the multiplication in a multiplication circuit of the contents of the first register by the contents of the fifth register is performed. This fifth register has been replenished with logic zeros if its size is greater than L. The shifting of the contents of the second register and the addition of these contents with the result of the multiplication, encoded on Q*L+L bits, is performed in a second adder. The Q*L most significant bits of the binary data element produced by the second adder are stored in the second register. The L least significant bits of these Q*L bits in the fourth register are stored.
According to another mode of operation, the step 2.2 is performed as follows. The shifting of the contents of the entire first register and the multiplication, in a multiplication circuit, of the contents of the first register by the contents of the fifth register is performed. This fifth register has been replenished with logic zeros if its size is greater than L. The shifting of the contents of the second register and the addition of these contents with the result of the multiplication, encoded on Q*L+L bits, is performed in a second adder. The [Q−j]*L most significant bits of the binary data element produced by the second adder are stored in a second register. The L least significant bits of these [Q−j]*L bits are stored in the fourth register.
According to yet another mode of operation, the step 2.2 is performed as follows. During the Q−1 first iterations, the shifting of the contents of the entire first register and the multiplication, in a multiplication circuit, of the contents of the first register by the contents of the fifth register is performed. This fifth register has been replenished with logic zeros if its size is greater than L. The shifting of the contents of the second register and the addition of these contents with the result of the multiplication, encoded on Q*L+L bits, is performed in a second adder. The [Q−j]*L most significant bits of the binary data element produced by the second adder are stored in the second register. The L least significant bits of these [Q−j]*L bits are stored in the fourth register.
According to one embodiment, with the variables i=j=0, the step 2.1 is performed as follows. The shifting of the contents of the third register by one unit towards the right and the loading of a 1 on the most significant bit of this third register and in a fifth register is performed. The bit-by-bit addition of the contents of the fourth register with a zero is performed in a first adder. The output of this first adder is provided to the input of the fourth register. The testing of the second least significant bit at the output of the first adder is performed by a test circuit. A loop is formed of L iterations indexed by i with i varying from 0 to L−1 if j is different from 0 and, if not, from 1 to L−1. The loop comprises the steps of shifting the content
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Galanthay Theodore E.
Mai Tan V.
STMicroelectronics S.A.
LandOfFree
Method for the production of a parameter J0 associated with... 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 a parameter J0 associated with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the production of a parameter J0 associated with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2555893