The present invention relates to security technologies, and more particularly to a data processing method using the modular exponentiation operation.
The RSA cryptosystem is the public-key cryptosystem proposed by Rivest, Shamir, and Adleman. The public-key cryptosystem includes information called “public key” which may be open to the general public, and secret information called “private key” which must be kept confidential. The public key is used for encryption of given data and verification of the signature. Meanwhile, the private key is used for decryption of the encrypted given data and generation of the signature.
In the RSA cryptosystem, the private key is defined as large prime numbers p and q and an integer d, while the public key is defined as integers n and e. Among these numerical values, relations:n=pq  (expression 1)ed=1 mod Phi(n)  (expression 2)hold. Here, Phi(n) denotes the Euler function for indicating the number of positive integers which are relatively prime to the integer n. In the case of n=pq, the Euler function is given byPhi(n)=(p−1)(q−1).  (expression 3)From the expression 1 and the expression 2, a relation satisfyingzed=z mod n  (expression 4)holds for an arbitrary integer z. Taking advantage of this property allows accomplishment of the encryption, the decryption, and the like. Namely, in the encryption and verification of the signature,xe mod n  (expression 5)is computed. Meanwhile, in the decryption and generation of the signature,yd mod n  (expression 6)is computed. Here, x and y are integers for indicating input data. This type of computation is referred to as “modular exponentiation operation”.
In general, for enhancement of the processing speed, the value of e is set as being small compared with the integer n. The value normally used ise=65537(=216+1).  (expression 7)
Also, as a high-speed implementation technique for speeding up the RSA cryptosystem, the Chinese Remainder Theorem (hereinafter, referred to as “CRT”) has been known. Meanwhile, proposals have been made concerning various types of public-key cryptosystems which are created by enhancing performance of the RSA cryptosystem. Their examples are multi-prime RSA, multi-exponent RSA, Rabin cryptosystem, HIME(R), and the like, which have been described in after-mentioned documents 4 to 7. The CRT is applicable to these public-key cryptosystems as well.
When the RSA cryptosystem or the like has been implemented as a cryptographic device, it is possible to observe such information as the computation time and power-consumption amount needed for the cryptographic processing, and accompanying electromagnetic waves. As a result, a proposal has been made regarding a method which, based on these pieces of information, allows revelation of the secret information such as the private key stored inside the cryptographic device. This method is referred to as “side-channel attack”. The side-channel attack has been described in P. C. Kocher, J. Jaffe, and B. Jun, “Differential Power Analysis” in the proceedings of CRYPTO 1999, Lecture Notes in Computer Science 1666, Springer-Verlag, pp. 388-397, 1999 (hereinafter document 1).
The side-channel attack on the RSA cryptosystem using the CRT has been described in R. Novak, “SPA-Based Adaptive Chosen-Ciphertext Attack on RSA Implementation” in the proceedings of 2002 International Workshop on Practice and Theory in Public Key Cryptography (PKC2002), Lecture Notes in Computer Science 2274, Springer-Verlag, pp. 252-262, 2002 (hereinafter document 2). This attack, which is referred to as “Novak's attack”, is expandable to the above-described public-key cryptosystems as well, i.e., the multi-prime RSA, the multi-exponent RSA, the Rabin cryptosystem, the HIME(R), and the like.
On the other hand, a technique for preventing the side-channel attack has been described in P. C. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems” in the proceedings of CRYPTO 1996, Lecture Notes in Computer Science 1109, Springer-Verlag, pp. 104-113, 1996 (hereinafter document 3). The method in the document 3, however, uses the inverse operation that necessitates a tremendous computation amount. Because of this, this method necessitates a tremendous computation time, although it is capable of preventing the side-channel attack. Also, it is possible to compute the inverse operation and store the computed value into a memory in advance. In this case, however, a large amount of memory is used.