Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1999-03-05
2003-04-08
Smithers, Matthew (Department: 2134)
Cryptography
Particular algorithmic function encoding
C708S491000
Reexamination Certificate
active
06546104
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a Montgomery reduction apparatus and a storage medium which are suitable for repetition of arithmetic processing including multiple-length multiplication using an odd integer as a modulus, e.g., public key encryption used for encryption of data in data communication over a computer network and authentication of a communication partner.
In an information communication network or computer system, electronic data are exchanged and accumulated. When such a system increases in size and an unspecified large number of users use the system, tapping and tampering by malevolent users become problems. To solve these problems, the public key encryption technique is often used.
In many cases, public key encryption is implemented by arithmetic operation (remainder computation system) using a multiple-length odd integer as a modulus. The speed of this arithmetic operation influences the performance of this scheme. In the remainder computation system, multiplication and division, in particular, exert great influences on the processing time. For example, in RSA encryption, encryption and decryption are executed by power calculations in a remainder computation system using an odd composite number as a modulus. In elliptic curve encryption on a prime field F
p
, addition of points on an elliptic curve is implemented by an appropriate combination of addition, subtraction, multiplication, and division using an odd prime number as a modulus, and encryption and decryption are executed by repetition of the point addition operation.
When a multiplication (calculation of A*B mod p) in a remainder computation system is to be implemented, a multiple-length multiplication (calculation of C=A*B) and a multiple-length remainder calculation (calculation of C mod p) with respect to the multiplication result are often configured. In this case, the performance of a multiple-length remainder calculation tends to be inferior to that of a multiple-length multiplication, and hence several studies have been made on the efficiency of remainder calculations.
As a calculation algorithm suitable for repetitive execution of multiplication in a remainder computation system, the Montgomery calculation is known.
According to a Montgomery calculation method, multiplication in a remainder computation system using an odd integer as a modulus is executed as follows. First of all, a multiple-length multiplication of a multiplier A and a multiplicand B is executed to obtain C. Assume that A and B are equal to or smaller in size than an integer p as a modulus. A computation called Montgomery reduction is then performed for C to reduce its size to that of the modulus or less. That is, C having a size about twice that of the modulus p is reduced to that of the modulus p. The Montgomery reduction corresponds to a general remainder calculation. The processing amount for this operation is almost equal to that for one multiplication of multiple-length values. That is, the remainder calculation processing is made efficient. This is because, of arithmetic operations on a computer, division is time-consuming operation as compared with addition, subtraction, and multiplication.
The Montgomery calculation method is an algorithm suitable for repetitive execution of multiplication in a remainder computation system for the reason given below. The Montgomery calculation method is a multiplication algorithm using an element in a Montgomery operation domain (this is also a remainder system with the same modulus), and the following processing is required to implement a multiplication in a general remainder system. First of all, a multiplier and a multiplicand are converted into values in the Montgomery operation domain. A Montgomery multiplication (multiplication and Montgomery reduction) is then performed. Lastly, the result must be inversely converted from the Montgomery operation domain to the original remainder system. The correspondence between the elements in the Montgomery operation domain and the original remainder system is stored before and after the Montgomery multiplication. Assume that multiplication is to be repeated in the remainder computation system as in power calculation. In this case, if the base of a power is converted into a value in the Montgomery operation domain at first, the Montgomery multiplication result need not be inversely converted into a value in the original remainder system every time the result is obtained. The result can be repeatedly used as an input for Montgomery multiplication. It therefore suffices if the value in the Montgomery operation domain is converted into a value in the original remainder system as the end of power calculation. The computation sizes for conversion and inverse conversion to and from the Montgomery computation respectively correspond to one remainder calculation and one multiplication. When such operation is performed only once at the beginning and start of the overall processing, no overhead occurs.
Elements in the Montgomery operation domain and the general remainder system have the following relationship. First of all, a power of 2 which is prime relative to the modulus p and larger than the modulus p is defined as R. In general, R is often set as a value that is a multiple of the word size of a computer and the minimum value exceeding the size of the modulus p. Consider, for example, software for a 32-bit CPU, and 1,024bits the modulus p. In this case, if R=2
1024
(=(2
32
)
32
), and the modulus p is 160 bits, R=2
160
(=(2
32
)
5
).
If elements in the general remainder system are represented by a and b with R described above, elements in the Montgomery operation domain which correspond to the elements a and b are represented by A=aR(mod p) and B=bR(mod p). In Montgomery reduction, D=CR
−1
(mod p)=(ab)R(mod p) is calculated with respect to C=AB. The element D in the Montgomery operation domain corresponds to the values a and b in the general remainder system. Montgomery reduction is arithmetic operation equivalent to D=CR
−1
(mod p), and hence can also be used for inverse conversion of the element D in the Montgomery operation domain to an element d in the general remainder system. That is, d=DR
−1
(mod p)=ab(mod p).
This Montgomery reduction is main arithmetic processing in Montgomery operation, and the processing speed of this arithmetic operation greatly influences the speed of encryption and the like. This arithmetic operation corresponds to about one multiple-length multiplication and hence is efficient as compared with computation methods other than the Montgomery computation method. Demands, however, have arisen for an increase in processing speed in consideration of the recent spread of encryption techniques and the like.
At present, there is no technique implemented, which can greatly reduce the processing amount of Montgomery reduction beyond one multiple-length multiplication. In practice, therefore, even the use of a Montgomery computation system cannot sufficiently improve the computation efficiency.
BRIEF SUMMARY OF THE INVENTION
The present invention has been made in consideration of the above situation, and has as its object to provide a Montgomery reduction apparatus which can implement Montgomery reduction with a small calculation amount and greatly improve the efficiency of Montgomery reduction.
It is another object of the present invention to provide an elliptic curve encryption apparatus using the Montgomery reduction apparatus.
In order to achieve the above objects, according to the first aspect of the present invention, there is provided a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R
−1
mod p by using R defined as R=2
n
using an integer a falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising:
an (&agr;, &bgr;) extraction section for calculating an integ
Kawamura Shin'ichi
Shimbo Atsushi
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Kabushiki Kaisha Toshiba
Smithers Matthew
LandOfFree
Montgomery reduction apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Montgomery reduction apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Montgomery reduction apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3099823