Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-02-02
2001-01-16
Ngo, Ohuong Dinh (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S650000
Reexamination Certificate
active
06175850
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a scheme for carrying out modular calculations, especially modular exponentiation calculations, which are necessary for basic operations and key generation in public key cryptosystems such as RSA cryptosystem.
2. Description of the Background Art
Basic operations and key generation in public key cryptosystems such as RSA cryptosystem require modular calculations such as modular exponentiation a
b
mod c, modular multiplication a×b mod c, and modular reduction a mod c. In addition, application protocols utilizing public key cryptosystems often utilize these modular calculations in combination. Consequently one frequently encounters cases where some modular calculation result is to be used in next calculation. In view of this fact, there has been a proposition of a calculation scheme using redundant binary calculation, as disclosed in A. Vandemeulebroecke, et al.: “A New Carry-Free Division Algorithm and its Application to a Single-Chip 1024-b RSA Processor”, IEEE Journal of Solid-State Circuits, Vol. 25, No. 3, pp. 748-756, June 1990.
However, this conventional scheme has been associated with the problem that modular exponentiation a
b
mod c and modular reduction a mod c cannot be calculated when |a|>|c|. In the following description, |k| will be referred to as a number of bits of k, and a, b and c appearing in modular exponentiation a
b
mod c will be referred to as mantissa (dividend), exponent, and modulus (divisor), respectively.
In principle, the redundant binary calculation requires the most significant bit of a divisor in binary expression to be “1” in a case of division, so that there has been a limitation that a number of bits of a divisor of a designed division circuit must coincide with a number of bits of a divisor to be used in calculation.
In this regard, there has been a proposition disclosed in Japanese Patent Application Laid Open No. 8-147266 (1996) for removing this limitation on a number of bits of a modulus by the following provisions.
(1) An entire divisor (modulus) is left shifted until the most significant bit of a divisor (modulus) becomes “1”.
(2) An entire dividend (mantissa) is also left shifted as much as a shifting made in (1).
(3) A calculation is carried out by the conventional redundant binary calculation.
(4) A calculation result is right shifted as much as a shifting made in (1) in order to correct the calculation result.
However, since the mantissa is to be right shifted for the same number of bits as the modulus in (2), there has been a problem that an accurate calculation becomes impossible when a number of bits of the mantissa is larger than a number of bits of the modulus because of the overflow.
Under such condition, when an application of this proposition to LSI is considered, there is no problem when the mantissa is set to be smaller than the modulus in advance, but it is rather inconvenient for applications to various application programs. For example, in a case of modular multiplication a×b mod c, one usually has a<c and b<c but a product a×b becomes larger than c in general so that this calculation cannot be carried out by this proposition.
Now, the modular exponentiation is frequently utilized as basic operations in public key cryptosystems. For example, in RSA cryptosystem, modular exponentiation using a secret exponent is to be carried out in the decryption operation and the signing operation.
Conventionally, almost all public key cryptosystems utilize modular exponentiation, which can be expressed as a
b
mod c. In the signing operation or the decryption operation, at least one of the three parameters involved in modular exponentiation is to be kept secret.
However, when three parameters are exactly the same, an identical result will be obtained obviously. On the other hand, in a case of carrying out modular exponentiation using a dedicated processor, an identical calculation result is always obtained when an environment such as operation frequency is constant. Then, there is a report which points out that a secret key can be obtained by utilizing these features, as disclosed in P. C. Kocher: “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems”, Advances in Cryptology—CRYPTO'96, Lecture Notes in Computer Science 1109, pp. 104-113, Springer-Verlag.
This method (called timing attack) is somewhat time consuming and not very easy, but still far easier than a method for deriving a secret key by utilizing mathematical features or a method for carrying out the extensive search of a secret key. This method becomes more dangerous in an environment in which the time can be measured more accurately. Moreover, this method becomes more dangerous when a number of parallel jobs is fewer.
Thus, the secret key calculation utilizing modular exponentiation and the like has the same amount of calculations for exactly the same parameters, and there are cases where this feature can be maliciously utilized to obtain a secret key.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a scheme for carrying out modular calculations which is capable of carrying out modular calculations using redundant binary calculation even when a number of bits of the mantissa is larger than a number of bits of the modulus.
It is another object of the present invention to provide a scheme for calculating modular exponentiation capable of preventing the timing attack for obtaining a secret key by utilizing the same parameters, which is a known attacking method for the public key cryptosystem using modular exponentiation by a dedicated processor.
According to one aspect of the present invention there is provided a method for carrying out modular calculations based on a redundant binary calculation scheme, including a modular reduction a mod c where a is a dividend and c is a divisor, comprising the steps of: (a) registering the dividend a and the divisor c in a dividend register and a divisor register, respectively; (b) left shifting the divisor c in the divisor register by (i−j) digits when a number of digits j of the divisor c is less than a number of digits i that can be stored in the divisor register; and (c) calculating the modular reduction a mod c up to (i−j)-th decimal place using the dividend a in the dividend register and the divisor c in the divisor register as left shifted by the step (b), to obtain a remainder as a modular reduction result.
According to another aspect of the present invention there is provided a method for carrying out modular calculations based on a redundant binary calculation scheme, including a modular reduction a mod c where a is a dividend given in h-ary notation and c is a divisor given in h-ary notation, comprising the steps of: (a) registering the dividend a and the divisor c in a dividend register and a divisor register, respectively; (b) left shifting the divisor c in the divisor register by (i−j) digits when a number of digits j of the divisor c is less than a number of digits i that can be stored in the divisor register; (c) left shifting the dividend a in the dividend register by (k−l) digits when a number of digits l of the dividend a is less than a number of digits k that can be stored in the dividend register, where k≧i; (d) calculating the modular reduction a mod c up to a digit of [(k−l)−(i−j)]-th power of h using the dividend a in the dividend register as left shifted by the step (c) and the divisor c in the divisor register as left shifted by the step (b), to obtain a remainder; and (e) right shifting the remainder obtained by the step (d) by (k−l) digits, to obtain a modular reduction result.
According to another aspect of the present invention there is provided a method for carrying out modular calculations based on a redundant binary calculation scheme, including a modular multiplication a×b mod c where a and b are dividends and c
Ishii Shinji
Oyama Katsuichi
Tanaka Kiyoto
Kilpatrick & Stockton LLP
Ngo Ohuong Dinh
Nippon Telegraph and Telephone Corporation
LandOfFree
Scheme for carrying out modular calculations based on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheme for carrying out modular calculations based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheme for carrying out modular calculations based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2489816