Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-03-02
2002-04-02
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06366940
ABSTRACT:
BACKGROUND OF THE INVENTION
(1) Field of the Invention
This invention relates to a modular multiplication apparatus which performs modular multiplications.
(2) Description of the Prior Art
Recently, as the encryption has been sophisticated in the field of communications, the encryption requires various calculation apparatuses.
For example, modular multiplication apparatuses for performing modular multiplications are used in the elliptic curve cryptosystem. It should be noted here that the “modular multiplication” indicates an operation denotes as “(a*b) mod p,” where a, b, and p are integers respectively representing a multiplicand, a multiplier, and a modulus. This operation is also referred to as a modulo p multiplication of (a*b), and (a*b) mod p is also referred to as residue, or modular multiplication value.
FIG. 1
shows the construction of a conventional modular multiplication apparatus.
It is assumed that values a, b, and p used in the operations performed by the conventional modular multiplication apparatus are each as small as 4 bits, for the sake of conveniences.
The modular multiplication apparatus
1
includes a product calculating unit
2
, a residue calculating unit
3
, and a control unit
4
.
The product calculating unit
2
, including a multiplicand register
5
(4-bit), an adder
6
(4-bit), and a product register
7
(9-bit), calculates a*b (a multiplication of multiplicand a and multiplier b) under control of the control unit
4
.
The following is a description of the procedures by which the control unit
4
controls the product calculating unit
2
.
Step 1: The control unit
4
allows the multiplicand register
5
to store the multiplicand a, allows the lower four bits of the product register
7
to store the multiplier b, and allows the higher five bits of the product register
7
to store 0s.
Step 2: The control unit
4
judges whether the least significant bit (LSB) of the product register
7
is 0 or 1. When having judged that the LSB is 1, the control unit
4
allows the adder
6
to add four bits out of the higher five bits excluding the most significant bit (MSB) stored in the product register
7
to the multiplicand a stored in the multiplicand register
5
, and allows the higher five bits of the product register
7
to store the addition result.
Step 3: The control unit
4
performs a right shift of one bit on the value stored in the product register
7
.
Step 4: The control unit
4
repeats Steps 2 and 3 four times.
When the loop including Steps 2 and 3 has been executed four times, the product register
7
stores the product a*b.
The residue calculating unit
3
includes a modulus register
8
(4-bit), an adder
9
(5-bit), and a residue register
10
(13-bit). The residue calculating unit
3
calculates, under control of the control unit
4
, (a*b) mod p in the same manner as a calculation by manual writing. Note that the residue output from the residue calculating unit
3
is a 5-bit value with a sign bit.
The following is a description of the procedures by which the control unit
4
controls the residue calculating unit
3
.
Step 5: The control unit
4
allows the modulus register
8
to store the modulus p, allows the lower eight bits of the residue register
10
to store the product (a*b) read from the product register
7
, and allows the higher five bits of the residue register
10
to store 0s.
Step 6: The control unit
4
performs a left shift of one bit on the value stored in the residue register
10
.
Step 7: The control unit
4
allows the adder
9
to subtract the modulus p read from the modulus register
8
from the value read from the higher five bits of the residue register
10
and to store the subtraction result value in the higher five bits of the residue register
10
.
Step 8: The control unit
4
judges whether the value stored in the higher five bits of the residue register
10
is positive or negative based on the MSB. When having judged that the value is negative (the MSB is 1), the control unit
4
allows the adder
9
to add up the value stored in the higher five bits of the residue register
10
and the modulus p stored in the modulus register
8
to restore the previous value (the value before the subtractions performed in Step 7) to the register
10
.
Step 9: The control unit
4
repeats Steps 6 to 8 eight times.
When the loop including Steps 6 to 8 has been executed eight times, the higher five bits of the residue register
10
stores the residue (a*b) mod p.
In the conventional modular multiplication apparatus
1
, 4-bit addition operations are enough for the adder
6
and adder
9
since the values a, b, and p are each as small as 4-bit, and the number of executions of a loop is as small as four times in the product calculating unit
2
and as eight times in the residue calculating unit
3
. However, in practice, the values a, b, and p used in the elliptic curve cryptosystem are each as great as 160-bit, for example. Accordingly, the adder
6
and adder
9
will be required to perform 160-bit addition operations if the apparatus
1
is adjusted to deal with values 160-bit values a, b, and p, for example. This results in an increase in the circuit size which is one of the problems of the conventional modular multiplication apparatus
1
. Also, in this case, the number of executions of a loop is as great as 160 in the product calculating unit
2
and as 320 in the residue calculating unit
3
. This results in an increase in the time taken for performing operations, which is another problem of the conventional apparatus
1
.
The U.S. Pat. No. 5,144,574, Modular Multiplication Method and the System for Processing Data discloses a modular multiplication method which relates to the above operation-time problem.
According to this method, the residue (a*b) mod p is obtained by the following procedure: a partial product is calculated by multiplying the multiplicand a by each two bits of the multiplier b in order from the MSB; each time the partial product is obtained, a partial residue is calculated by subtracting an integral multiple of the modulus p from the calculated partial product; and the residue (a*b) mod p is obtained by accumulating the calculated partial products.
Compared with the first conventional method, this method reduces the number of executions of the loop and the operation time since the partial product is calculated for each two bits of the multiplier b while in the first method, the product is calculated for each bit.
However, the time reduced by the second conventional method is not so much when the values a, b, and p to be dealt with are large.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a modular multiplication apparatus which is achieved in a small circuit and performs calculations at high speed.
The above object is fulfilled by a modular multiplication apparatus for calculating a congruent value of a modulo P multiplication of a product of a multiplicand a and a k
b
-bit multiplier b, where P is k-bit, the congruent value being obtained from a following formula:
accumulated
value
=
∑
i
=
0
[
[
kb
/
s
]
]
C
(
i
)
*
b
[
s
*
i
+
s
-
1
:
s
*
i
]
,
where [[kb/s]] represents integers included in quotient k
b
/s, i represents integers in a range of 0 to [[kb/s]],
C(i) is represented by a recurrence formula, and
C
(
i
)=
a
(
i=
0)
C
(
i
)=(
C
(
i−
1)*2
s
) mod
P
(
i≧
1),
C(i) (intermediate value) is a congruent value of a modulo P multiplication of a product (a preceding intermediate value*2
S
), where the congruent value is calculated recurrently, an initial intermediate value is the multiplicand a, and the product being equal to the preceding intermediate value shifted s bits, b[s*i+s−1:s*i] represents s-bit, partial multipliers included in the multiplier b at places from 2
s*i+s−1
to 2
s*i
, the modular multiplication apparatus comprising: a table unit which prestores residues of modulo p multiplications o
Kashiwa Hiroshi
Matsuzaki Natsume
Ono Takatoshi
Mai Tan V.
Price and Gess
LandOfFree
High-speed modular multiplication apparatus achieved in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-speed modular multiplication apparatus achieved in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed modular multiplication apparatus achieved in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2910500