Abstract:
A randomly selected point on an elliptic curve is set as the initial value of a variable and calculation including a random point value is performed in an algorithm for calculating arbitrary scalar multiple operation on an elliptic curve when scalar multiplication and addition on an elliptic curve are defined, then a calculation value obtained as a result of including a random point is subtracted from the calculation result, whereby an intended scalar multiple operation value on an elliptic curve is determined.

Description:
CROSS REFERENCE TO RELATED APPLICATION  
       [0001]     This application is a continuation of PCTapplication of PCT/JP2005/000878, which was filed on Jan. 24, 2005. 
     
    
     BACKGROUND OF THE INVENTION  
       [0002]     1. Field of the Invention  
         [0003]     The present invention relates to a cryptographic device, and particularly to a cryptographic device having tamper resistance for preventing power analysis attacks on processors executing the RSA cryptosystem and the elliptic-curve cryptosystem.  
         [0004]     2. Description of the Related Arts  
         [0005]     Services using networks, such as electronic money, electronic tickets, services provided by e-government, have been widely employed. In these services, smart cards (IC cards) each including an IC chip storing secret information on a user are sometimes used in order to certify that the user is a legitimate user. Smart cards have functions that perform encryption, digital signatures, verification, and the like, and use users&#39; secret information as keys. Smart cards present much better protection and tamper resistance against unauthorized accesses by third parties than magnetic cards because, in smart cards, the secret information is stored in the IC chips or memory units.  
         [0006]     Examples of the cryptosystem employed in cryptographic devices such as smart cards include public key cryptosystem and common key cryptosystem. In public key cryptosystem, different keys are used for encryption and decryption. Typically, the key used for encryption (public key) is in a public state, and a person who wants to transmit his or her information encrypts the plaintext by using this public key before the transmission. The key used for decrypting the encrypted text (secret key) is held as secret information that is known only to the receiving person, and the receiving person can obtain the plaintext by decrypting the encrypted text with the secret key. Examples of public key cryptosystem include RSA cryptosystem and elliptic-curve cryptosystem.  
         [0007]     One of the functions for performing the main operations that are required for executing the RSA cryptosystem is the modular exponentiation operation function. The exponentiation operation is an operation in the form of 
 
 aˆd (mod  n )= a×a× . . . ×a ( d  times)(mod  n ) 
 
 where “ˆ” represents the exponentiation, and a, d, and n represent integers. Also, “mod n” represents the remainder left after division by n. The functions of the RSA cryptosystem include encryption, decryption, signature generation, and signature verification. In decryption and signature generation, values related to the secret information of users are used for “d”. 
 
         [0008]     Examples of functions for performing the main operations required for executing the processes of elliptic-curve cryptosystem include scalar multiplication. The scalar multiplication used herein is an operation in the form of 
 
 d×P=P+P+ . . . +P ( d  times) 
 
 where d represents an integer and P represents a point on an elliptic curve. The functions based on elliptic-curve cryptosystem include encryption, decryption, signature generation, signature verification, and key sharing. In decryption, signature generation, and key sharing, values related to the secret information of users are used for “d”. The above modular exponentiation operation for the RSA cryptosystem and scalar multiplication for the elliptic-curve cryptosystem are examples for operations called the exponentiation operation. 
 
         [0009]     Examples of techniques employed in the field of handling secret information include a technique called cryptanalysis (tampering technique). Cryptanalysis is a technique used for detecting what is included in secret information (such as a secret key) on the basis of available information (such as an encrypted text), the various methods of which are known. Among these methods, there is a method called side channel attack that has recently gained interest.  
         [0010]     The side channel attack method is a cryptanalysis method that was introduced by P. Kocher in 1996 (see “Timing attacks on implementation of Diffie-Hellman, RSA, USA and other systems”, CRYPTO&#39;96, Lecture Notes in Computer Science Vol. 1109, pp. 104-113, Springer-Verlag, 1996 (document [Koc96]). In this method, side channel information (electrical power consumption data, time consumption data, electromagnetic wave data and the like) obtained when various data are input into the cryptographic processor mounted on a smart card or the like is collected and analyzed in order to detect the key information in the cryptographic processor. It has been pointed out that, by using the side channel attack, the secret keys in cryptographic processors can be detected both in public key cryptosystem and common key cryptosystem.  
         [0011]     An example of a method of side channel attack is a powerful method called power analysis attack, in which electric power consumption data is used. Examples of power analysis attacks include differential power analysis (DPA), reported by P. Kocher, J. Jaffe and B. Jun in Crypto&#39;99, Lecture Notes in Computer Science Vol. 1666, pp. 388-397, Springer-Verlag, 1999 (document [KJJ99]), and simple power analysis (SPA). SPA is a method in which secret keys are detected on the basis of characteristics in electric power consumption data in cryptographic processors, and DPA is a method in which secret keys are detected by analyzing the differences between a large number of pieces of electric power consumption data. Other examples of power analysis attacks include the refined power analysis (RPA) reported by L. Goubin in “Refined Power-analysis Attacks on Elliptic Curve Cryptosystems”, PKC 2003, Lecture Notes in Computer Science Vol. 2567, pp. 199-210, Springer-Verlag, 2003 (document [Gou03]), and zero-value power analysis (ZVA) reported by T. Akishita and T. Takagi in “Zero-value Point Attacks on Elliptic Curve Cryptosystems”, ISC 2003, Lecture Notes in Computer Science Vol. 2851, pp. 218-233, Springer-Verlag, 2003 (document [AT03]).  
         [0012]     The need for techniques that prevent such power analysis attacks as described above has been suggested in the field of international standardization. For example, in the protection profile (PP) for smart cards that is based on (ISO) (International Standards Organization) 15408 in the field of security, countermeasures against power analysis attacks are required. Also, in FIPS140-2, which is one of the standards for cryptographic modules employed in the USA, it is thought that countermeasures against power analysis attacks will be required in the future, although this need is only being discussed at present.  
         [0013]     In RSA cryptosystem and elliptic-curve cryptosystems, the main operation in the cryptographic process is the exponentiation operation. Also, this exponentiation operation is the target of power analysis attacks. Hereinafter, a method of realizing the scalar multiplication d×P in elliptic-curve cryptosystem is described.  
         [0014]     The binary method is an operation for computing the scalar multiplication. Some of the binary methods are a method in which computations are performed from the least significant bit (binary method (LSB)), a method in which computations are performed from the most significant bit (binary method (MSB), and a method that is a variation of the binary method (MSB) using the Montgomery chain (Montgomery method).  
         [0015]     An example of an algorithm for the binary method (LSB) is given as (1) Algorithm 1, an example of an algorithm for the binary method (MSB) is given as (2) Algorithm 2, and an example of an algorithm for the Montgomery method is given as (3) Algorithm 3. In these algorithms, unless otherwise noted, lowercase letters (such as “d”) represent scalar values and capital letters (such as “P”) represent points on elliptic curves. Also, “ˆ” represents exponentiation, and a series of numbers expressed between “(” and “) 2 ” represents a number expressed as a binary number. Also, numbers preceded by an “S” (e.g., “S 1 :”) are step numbers in an exemplary program. Hereinafter, the four arithmetical operations on an elliptic curve are respectively included between “┌” and “┘”.  
                                                                                   (1) Algorithm 1 [Binary method (LSB)]                                    S1: T[0]           0, T[1]           P           S2: for i = 0 upto n-1 {                S3:   if (d[i] == 1 ) {                S4:   T[0]           ┌T[0] + T[1]┘           *                S5:   }           S6:   T[1]           ┌2*T[1]┘           S7: }           S8: return T[0] ,                      
 
 where T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d. 
 
         [0016]     As an example, a case is described here in which the scalar multiplication ┌d×P┘ for d=21=2ˆ4+2ˆ2+2ˆ0=(10101) 2  (d is an integer in 5 bits) is performed. In step S 1 , the variable T[0] is set to the point 0, and the variable T[1] is set to the point P. In steps S 2  through S 7  that follow, respective processes corresponding to i=0, 1, 2, 3, 4 are executed.  
         [0017]     When i=0, d[i]=d[0]=1, and accordingly the variable T[0] is set to ┌T[0]+T[1]┘ and the value of the variable T[0]after processing is P. In step S 6 , the variable T[1] is set to ┌2*T[1]{cube root} and the variable T[1] after processing is ┌2×P┘.  
         [0018]     When i=1, d[i]=d[1]=0, and accordingly steps S 3  through S 5  are skipped. In step S 6 , the variable T[1] is set to ┌2*T[1]┘, and the value of the variable T[1] after processing is ┌4×P┘.  
         [0019]     When i=2, d[i]=d[2]=1, and accordingly in step S 4  the variable T[0] is set to ┌T[0]+T[1]┘, and the value of the variable T[0 after processing is ┌5×P┘. In step S 6 , the variable T1] is set to ┌2*T[1]┘, and the value of the variable T[1] after processing is ┌8×P┘.  
         [0020]     When i=3, d[i]=d[3]=0, and accordingly steps S 3  through S 5  are skipped. In step S 6 , the variable T[1] is set to ┌2*T[1]┘, and the value of the variable T[1] after processing is ┌16×P┘.  
         [0021]     When i=4, d[i]=d[0]=1, and accordingly in step S 4  the variable T[0] is set to ┌T[0]+t[1]┘ and the value of the variable T[0] after processing is ┌21×P┘. In step S 6 , the variable T[1] is set to ┌2*T[1]┘, and the value of the variable T[1] after processing is ┌32×P┘.  
         [0022]     After the above processes, the processes in steps S 2  through S 7  are terminated, and the value of the variable T[0] i.e., ┌21×P┘, is output in the last step S 8 .  
                                                                                   (2) Algorithm 2 [binary method (MSB)]                                    S1: T[0]           P           S2: for i = n-2 downto 0 {                S3:   T[0]           ┌2*T[0]┘           S4:   if ( d[i] == 1 ) {                S5:   T[0]           ┌T[0] + P┘           *                S6:   }           S7: }           S8: return T[0]                      
 
 where T[0] represents a temporary variable, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d. 
 
         [0023]     As an example, a case is described in which the scalar multiplication ┌d×P┘ for d=21=2ˆ4+2ˆ2+2ˆ0=(10101) 2  (d is an integer in 5 bits) is performed. In step S 1 , the variable T[0] is set to the point P. In steps S 2  through S 7  that follow, respective processes corresponding to i=3, 2, 1, 0 are executed.  
         [0024]     When i=3, in step S 3 , the variable T[0] is set to ┌2*T[0]┘, and the value of the variable T[0] after processing is ┌2×P┘. Also, when i=3, d [i]=d[3]=0, and accordingly steps S 4  through S 6  are skipped.  
         [0025]     When i=2, in step S 3 , the variable T[0] is set to ┌2*T[0]┘, and the value of the variable T[0] after processing is ┌4×P┘. Also, when i=2, d[i]=d[2]=1, and accordingly in step s 5  the variable T[0] is set to ┌T[0]+P┘, and the value of the variable T[0] after processing is ┌5×P┘.  
         [0026]     When i=1, in step S 3 , the variable T[0] is set to ┌2*T[0]┘, and the value of the variable T[0] after processing is ┌10×P┘. Also, when i=1, d [i]=d[1]=0, and accordingly steps S 4  through s 6  are skipped.  
         [0027]     When i=0, in step S 3 , the variable T[0] is set to ┌2*T[0]┘, and the value of the variable T[0] after processing is ┌20×P┘. Also, when i=0, d[i]=d[0]=1, and accordingly variable T[0] is set to ┌T[0]+P┘ in step s 5 , and the value of the variable T[0] after processing is ┌21×P┘.  
         [0028]     After the above processes, the processes in steps S 2  through S 7  are terminated, and the value of the variable T[0], i.e., ┌21×P┘ is output in the last step, S 8 .  
                                                                 (3) Algorithm 3 [Montgomery method]                                    S1: T[0]           P, T[1]           ┌2*P┘           S2: for i = n-2 downto 0 {                S3:   T[2]           ┌2*T[d[i]]┘           S4:   T[1]           ┌T[0] + T[1]┘           S5:   T[0]           T[2-d[i] ]           S6:   T[1]           T[1+d[i] ]                S7: }           S8: return T[0] ,                      
 
 where T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d. 
 
         [0029]     As an example, the case is described here in which the scalar multiplication ┌d×P┘ for d=21=2ˆ4+2ˆ2+2ˆ0=(10101) 2  (d is an integer in 5 bits) is performed. In step S 1 , the variable T[0] is set to the point P, and the variable T[1] is set to ┌2×P┘. In the following steps S 2  through S 7 , respective processes corresponding to i=3, 2, 1, 0 are executed.  
         [0030]     When i=3, d[i]=d[3]=0. In step S 3 , the variable T[2] is set to ┌2*T[0]┘, and the value of the variable T[2] after processing is ┌2×P┘. In step S 4 , the variable T[1] is set to ┌T[0]+T[1]┘, and the value of the variable T[1] after processing is ┌3×P┘. In step S 5 , the variable T[0] is set to T[2], and the value of the variable T[0] after processing is ┌2×P┘. In step S 6 , the variable T[1] is set to T[1], and the value of the variable T[1] is ┌3×P┘.  
         [0031]     When i=2, d[i]=d[2]=1. In step S 3 , the variable t[2] is set to ┌2*T[1]┘, and the value of the variable T[2] after processing is ┌4×P┘. In step S 4 , the variable T[1] is set to ┌T[0]+T[1]┘, and the value of the variable T[1] after processing is ┌6×P┘. In step S 5 , the variable T[0] is set to T[1], and the value of the variable T[0] after processing is ┌6×P┘. In step s 6 , the variable T[1] is set to T[2], and the value of the variable T[1] after processing is ┌6×P┘.  
         [0032]     When i=1, d[i]=d[1]=0. In step S 3 , the variable T[2] is set to ┌2*t[0]┘, and the value of the variable T[2] after processing is ┌10×P┘. In step S 4 , the variable T[1] is set to ┌T[0]+T[1]┘, and the value of the variable t[1] after processing is ┌11×P┘. In step S 5 , the variable T[0] is set to T[2], and the value of the variable T[0] after processing is ┌10×P┘. In step S 6 , the variable T[1] is set to T[1], and the value of the variable T[1] after processing is ┌11×P┘.  
         [0033]     When i=0, d[i]=d[0]=0. In step S 3 , the variable T[2] is set to ┌2*T[1]┘, and the value of the variable T[2] after processing is ┌22×P┘. In step S 4 , the variable T[1] is set to ┌T[0]+T[1]┘, and the value of the variable T[1] after processing is ┌21×P┘. In step s 5 , the variable T[0] is set to T[1], and the value of the variable T[0] after processing is ┌21×P┘. In step S 6 , the variable T[1] is set to T[2], and the value of the variable T[1] after processing is ┌22×P┘.  
         [0034]     After the above processes, the processes in steps S 2  through S 7  are terminated, and the value ┌21×P┘ of the variable T[0] is output in the last step, S 8 .  
         [0035]     Also, in addition to the above binary methods (Algorithms 1 and 2) and the Montgomery method (Algorithm 3), a method called the window method can be employed for realizing the scalar multiplication ┌d×P┘. In the window method, using a width of, for example, 4-bit, scalar multiplication by integers 0 through 15 are computed as an initial process, the results are held in a table, and in a scalar multiplication by d, the scalar d is divided for every 4 bits (windows); thereby, the scalar multiplication is computed. Hereinafter, an example of an algorithm for the window method (4-bit width) is described as Algorithm 4.  
                                                                                             (4) Algorithm 4 [Window method (4-bit width)]                                    S01: W[0]           O, W[1]           P           S02: for i = 2 upto 15 {                S03:   W[i] = ┌W[i-1] + P┘           S04: }                S05: T[0]           W[d[n-1,n-4] ]           S06: for i = n-5 downto 3 step -4 {                S07:   T[0]           ┌16*T[0]┘                S08:   T[0]           ┌T[0] + W[d[i,i-3]]┘           S09: }           S10: return T[0] ,                      
 
 where it is assumed that d is a scalar value in n bits, and n is a multiple of 4. Also, it is assumed that d[i, i−3] is a value in 4-bits starting from the lower i-th bit to the (i−3)th bit of d. W[i] is a table used in the window method. 
 
         [0036]     As an example, a case is described herein which the scalar multiplication for d=21=2ˆ4+2ˆ2+2ˆ0=(10101) 2 =(0001 0101) 2  (d is an integer in 5 bits) is computed. Because the bit length of d (i.e., 5) is not a multiple of 4, zeros are padded into the higher three bits and it is handled as 8 bits for convenience, which results in n=8. First, W[0]=0 and W[1]=P are set as the initial values in step S 01 . Next, steps S 02  through S 04  are executed for i=2, 3, . . . , 15. For each i, W[i]=┌W[i−1]+P┘ is set in step S 03 . Then, the value to which W[i] is set is ┌i×P┘. After the processes of steps S 02  through S 04 , the variable T[0] is set to W[d[n−1, n−4]]=W[d[7, 4]]=W[0001]=┌1×P┘ in step S 05 .  
         [0037]     Next, processes in steps S 06  through S 09  corresponding to i=3 are executed. In step S 07 , the process of T[0]←┌16*T[0]┘ is executed, and ┌16×P┘ is registered as the variable T[0]. In step S 08 , the process of T[0]←┌T[0]+W[d[i, i−3]]┘=┌T[0]+W[0101]┘=┌┌16×P┘+┌5×P┘┘=┌21×P┘, and ┌21×P┘ is registered as the variable T[0].  
         [0038]     After the above processes, the processes in steps S 06  through S 09  are terminated. The value of ┌21×P┘ is output in the last step S 10 . In the window method, as described above, the scalar multiplication ┌d×P┘ is computed by using a table that is prepared in advance.  
         [0039]     In a case in which the scalar multiplication is computed by using Algorithms 1 and 2 above, it depends on the bit value d[i] of d whether or not the processes in the steps with the marks of “*” are executed. In the simple power analysis (SPA), the secret key d is estimated by using this feature. From many experiments, it is detected that the waveform of power consumption that results from the addition of points on an elliptic curve (elliptic addition) and the waveform that results from doubling (elliptic doubling) can easily be distinguished from each other. Accordingly, it is possible to obtain the secret key d because the order and the number of elliptic additions and elliptic doublings can be obtained by measuring the waveforms formed in the computations in Algorithms 1 and 2 in processors. Additionally, Algorithms 3 and 4 do not include a branch condition that depends on the bit value d[i], and thus they have resistance to the SPA.  
         [0040]     As a countermeasure against the SPA targeting Algorithms 1 and 2, a method called add-and-double-always method has been reported. In this method, an addition and a doubling are always computed for each bit in the algorithms. This method is reported by J. Coron, in “Resistance against Differential Power Analysis”, Cryptographic Hardware and Embedded Systems 1999 (CHES 1999), Lecture Notes in Computer Science Vol. 1717, pp. 292-302, Springer-Verlag, 1999 (document [Coron99]). Because the elliptic addition and elliptic doubling are always performed alternately in this method, this method is thought to have resistance to the SPA. Algorithm examples in which add-and-double-always method is performed on the above Algorithms 1 and 2 are given below as (5) Algorithm 1′ and (6) Algorithm 2′.  
                                                                 (5) Algorithm 1′ [Binary method (LSB, add-and-double-always)]                                    S1: T[0]           0, T[2]           P           S2: for i = 0 upto n-1 {                S3:   T[1]           ┌T[0] + T[2]┘           S4:   T[2]           ┌2*T[2]┘           S5:   T[0]           T[d[i]]                S6: }           S7: return T[0] ,                      
 
         [0041]     where T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit.  
                                                                 (6) Algorithm 2′ [Binary method (MSB, add-and-double-always)]                                    S1: T[0]           0, T[2]           P           S2: for i = n-1 downto 0 {                S3:   T[0]           ┌2*T[0]┘           S4:   T[1]           ┌T[0] + T[2]┘           S5:   T[0]           T[d[i]]                S6: }           S7: return T[0] ,                      
 
 where T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit. 
 
         [0042]     By using Algorithms 1′, 2′, 3, and 4 above, it is possible to prevent the SPA. However, the document [Coron99] describes the DPA targeting these algorithms, and points out that a secret key is analyzed by the DPA even when these algorithms are used. Also, the analysis methods using the RPA and the ZVA are reported.  
         [0043]     Neither the binary methods nor the Montgomery method have resistance to SPA, DPA, RPA, or ZVA. The exponent splitting (ES) method, a countermeasure against these power analysis methods, is reported by C. Clavier, M. Joye, in “Universal Exponentiation Algorithm—A First Step towards Provable SPA-resistance—”, Cryptographic Hardware and Embedded Systems 2001 (CHES 2001), Lecture Notes in Computer Science Vol. 2162, pp. 300-308, Springer-Verlag, 2001 (document [Clavier-Joye01]). This ES method is a method in which scalar values are converted at random, the scalar d is divided into d=r+(d−r) by the random number r, and two scalar multiplications ┌r×P┘ and ┌(d−r)×P┘ are computed independently; thereafter, a scalar multiplication ┌d×P┘ is computed by adding the results of the two scalar multiplications to each other, which is based on a below equation. 
 
┌┌ r×P┘+┌ ( d−r )× P┘┘=┌d×P┘ 
 
         [0044]     In the ES countermeasure, an algorithm having resistance to other types of SPA/DPA is used for the above two scalar multiplications ┌r×P┘ and ┌(d−r)×P┘.  
                                         (7) Algorithm 5 [Exponent Splitting method]                                    S1: r           random( )           S2: T[1]           scalar(r, P)           S3: T[2]           scalar(d-r, P)           S4: T[0]           ┌T[1] + T[2]┘           S5: return T[0] ,                      
 
 where random( ) represents a function for generating random numbers. Also, scalar (d, P) represents a function for computing the scalar multiplication ┌d×P┘, and is computed by using the above Algorithms 1′, 2′, 3, 4, and the like. Also, the variables r, T[0], T[1], T[2] represent temporary variables. 
 
         [0045]     It is likely to say that the ES method has resistance to all of the types of SPA, DPA, RPA, and ZVA; however, a problem with this method in relation to the computational efficiency is the large amount of overhead that is required.  
         [0046]     Patent Document 1 discloses an operating method, in which the elliptic addition and elliptic doubling are defined as one operation, and operations having the same properties are performed in parallel; thereby, resistance to side channel attacks is attained and scalar multiplication can be performed at a high speed.  
         [0000]     Patent Document 1:  
         [0000]     Japanese Patent Application Publication No. 2004-53814  
       SUMMARY OF THE INVENTION  
       [0047]     It is an object of the present invention to provide a cryptographic device that can enhance the security against SPA, DPA, RPA, and ZVA by increasing the difficulty of guessing secret information.  
         [0048]     The first cryptographic device according to the present invention is a cryptographic device executing a cryptographic process by using a secret key, comprising:  
         [0049]     a random value generation unit for generating a random integer value that is based on random numbers;  
         [0050]     a cryptographic operation unit for performing a cryptographic operation while including the random integer value in values that have to be originally used in an operation when executing an algorithm; and  
         [0051]     a randomization nullification unit for nullifying from an obtained value the effect of including the random integer value in an operation after execution of the encryption operation.  
         [0052]     The second cryptographic device according to the present invention is a cryptographic device executing elliptic-curve cryptosystem by using a secret key, comprising:  
         [0053]     a randomization unit for setting as an initial point a point R on an elliptic curve generated on the basis of random numbers;  
         [0054]     a unit for performing scalar multiplication by using the initial point, a scalar value d for elliptic-curve cryptosystem, and a point P on an elliptic curve;  
         [0055]     a randomization nullification unit for executing Q-R′ by using a point R′ related to the point R and a point Q obtained by the multiplication; and  
         [0056]     a unit for outputting a result of the nullification.  
         [0057]     The third cryptographic device according to the present invention is a cryptographic device executing RSA cryptosystem by using a secret key, comprising:  
         [0058]     a randomization unit for setting as an initial value an integer r generated on the basis of random numbers;  
         [0059]     a unit for performing a modular exponentiation operation by using the initial value, an exponent d that is necessary for RSA cryptosystems, and an integer p;  
         [0060]     a randomization nullification unit for executing modular multiplication of q/r′ by using a value r′ related to r and an integer q obtained in the operation; and  
         [0061]     a unit for outputting a result of the nullification.  
         [0062]     According to the present invention, operations are performed with random integer values (coordinate values on an elliptic curve or integer values on a finite field) taken into consideration, each of the integer values being newly generated each time a calculation based on an executed algorithm is performed. Accordingly, the difficulty of guessing secret information increases, and thus it is possible to enhance the security against power analysis attacks because the information that the attacker obtains differs randomly each time the information is obtained. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0063]      FIG. 1  shows the elliptic addition;  
         [0064]      FIG. 2  shows the elliptic doubling;  
         [0065]      FIG. 3  shows a configuration of the main portion of an elliptic-curve cryptosystem device according to the present invention;  
         [0066]      FIG. 4  is a block diagram showing a function configuration of an elliptic-curve cryptosystem device according to an embodiment of the present invention; and  
         [0067]      FIG. 5  shows a hardware environment of a cryptographic device according to an embodiment of the present invention. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0068]     According to an embodiment of the present invention, a cryptographic device for performing elliptic-curve cryptosystem by using secret keys includes a randomization unit for setting as an initial point a point R on an elliptic curve generated on the basis of random numbers, an operation unit for computing scalar multiplication by using the initial point, a scalar value d for the elliptic-curve cryptosystem, a point P on the elliptic curve, and a randomization nullification unit for executing Q-R′ by using a point R′ related to the point R and the point Q obtained by the multiplication, and a unit for outputting the result.  
         [0069]     When an embodiment of the present invention is applied to the RSA cryptosystem, a cryptographic device for processing the RSA cryptosystem by using a secret key comprises a randomization unit for setting as an initial value an integer r generated on the basis of random numbers, a unit for performing the modular exponentiation operation by using the initial value; an exponent d that is necessary for the RSA cryptosystem; an integer p, a randomization nullification unit for executing q/r′ by using the value r′ related to r from an integer q obtained in the operation, and a unit for outputting the result.  
         [0070]     According to an embodiment of the present invention, a process method can be realized that requires a smaller amount of scalar multiplication processes in elliptic-curve cryptosystem and has resistance to SPA, DPA, RPA, and ZVA.  
         [0071]     Also, it is possible to provide a process method having resistance to SPA, DPA, RPA, and ZVA by applying an embodiment of the present invention to the RSA cryptosystem.  
         [0000]     (a) Descriptions of Fundamentals  
         [0072]     An elliptic-curve cryptosystem device that is one embodiment of the present invention may be realized as, for example, an information processing device dedicated to elliptic-curve cryptosystem, a personal computer, an IC chip included in an IC card (smart card) or the like, a mobile phone, a mobile information terminal device (PDA (Personal Digital Assistant) or the like), or a DVD player or the like, and comprises a processor for performing operations.  
         [0073]     In the description below, an explanation is given for the case in which an elliptic-curve cryptosystem operation method according to an embodiment of the present invention is applied to an elliptic curve on a finite field GF (pˆm) with pˆm elements where p is a prime number and m is an integer equal to or greater than one. Additionally, hereinafter, unless otherwise noted, lowercase letters (such as “d”) represent scalar values and capital letters (such as “P” and “T”) represent points on elliptic curves. Also, “ˆ” represents the exponentiation, and a series of numbers between “(” and “) 2 ” represents a number expressed as a binary number. Also, a number preceded by “S” (for example, “S 1 :”) represents a step number in an exemplary program. Further, the four arithmetical operations on elliptic curves are respectively included between “┌” and “┘”.  
         [0074]     An elliptic curve E on GF (pˆm) is a set obtained by adding the point ∞ that is called the infinite point (also referred to as zero point hereinafter) to the set of points (x, y) that satisfies the equation below: 
 
E:  yˆ 2 +a 1 ×x×y+a 3 ×y=xˆ 3 +a 2 ×xˆ 2 +a 4 ×x+a 6 
 
 where a1, a2, a3, a4, a6, x, and y are respectively the elements in GF (pˆm). The points on elliptic curves can be expressed in the form of coordinates such as (x, y), however the infinite point ∞ is the only point that cannot be expressed in the form of (x, y). 
 
         [0075]     The inverse element “−P” of P is defined as below, on the assumption that P is a point on the elliptic curve on GF (pˆm). 
 
if  P=∞,┌−   P ┘=∞  (1) 
 
if  P≠∞,┌−P┘= ( x,−y−a 1 ×x−a 3) when  P =( x, y )  (2) 
 
         [0076]     Also, the sum (P3) of P1 and P2, i.e., P3=┌P1+P2┘ is defined as below on the assumption that P1 and P2 are two points on the elliptic curve E on GF (pˆm). 
 
if P1=∞,P3=P2  (1) 
 
if P2=∞,P3=P1  (2) 
 
if  P 1= ┌−P 2 ┘,P 3=∞  (3) 
 
if  P 1≠ ┌−P 2 ┘,P 1=( x 1 ,y 1), P 2=( x 2 ,y 2), and  P 3=( x 3 ,y 3),  (4) 
 
 x 3=λˆ2 +a 1 ×λ−a 2 −x 1 −x 2 
 
 y 3=−(λ+ a 1)× x 3 −ν−a 3 
 
 where 
 
         [0077]     when P1≠P2, 
 
λ=( y 2 −y 1)/( x 2 −x 1) 
 
ν=( y 1 ×x 2 −y 2 ×x 1)/( x 2 −x 1) 
 
         [0078]     when P1=P2, 
 
λ=(3 ×x 1ˆ2+2 ×a 2 ×x+a 4 −a 1 ×y 1)/(2 ×y 1+ a 1 ×x 1+ a 3) 
 
ν=(− x 1ˆ3 +a 4 ×x 1+2 ×a 6 −a 3 ×y 1)/(2 ×y 1+ a 1 ×x 1+ a 3) 
 
         [0079]     A computation of ┌P1+P2┘ performed when P1≠P2 is called elliptic addition, and a computation of ┌P1+P2┘=┌2×P1┘ performed when P1=P2 is called elliptic doubling. Elliptic addition and elliptic doubling are computed on the basis of combinations among the addition, subtraction, multiplication, squaring, and inversion in the GF (pˆm).  
         [0080]     When p is a prime number, the finite field GF (p) is referred to as a prime field. In particular, when p is a prime number equal to or greater than 5, the elliptic curve E on the prime field GF(p) is a set obtained by adding the point ∞ referred to as the infinite point to the set of points (x, y) that satisfy the equation below. 
 
E:  yˆ 2 =xˆ 3 +a×x+b  
 
         [0081]     The infinite point ∞ is also referred to as zero. Also, a, b, x, and y are respectively the elements of GF (p). The points on elliptic curves can be expressed in the form of coordinates such as (x, y); however, the infinite point ∞ is the only point that cannot be expressed in the form of (x, y).  
         [0082]     The inverse element “−P” of P is defined as below, on the assumption that P is a point on the elliptic curve of GF (p). 
 
if  P=∞,┌−   P ┘=∞  (1) 
 
if  P≠∞,┌−P┘= ( x,−y ) when  P =( x,y )  (2) 
 
         [0083]     Also, the sum (P3) of P1 and P2, i.e., P3=┌P1+P2┘ is defined as below on the assumption that P1 and P2 are two points on the elliptic curve E of GF (p). 
 
if P1=∞,P3=P2  (1) 
 
if P2=∞,P3=P1  (2) 
 
if  P 1= ┌−P 2 ┘,P 3=∞  (3) 
 
if  P 1≠ −P 2 ,P 1=( x 1 ,y 1), P 2=( x 2 ,y 2), and  P 3=( x 3 ,y 3),  (4) 
 
 x 3=λˆ2 −x 1 −x 2 
 
 y 3 =−λ×x 3−ν
 
 where 
 
         [0084]     when P1≠P2, 
 
λ=( y 2 −y 1)/( x 2 −x 1) 
 
ν=( y 1 ×x 2 −y 2 ×x 1)/( x 2 −x 1) 
 
         [0085]     when P1=P2, 
 
λ=(3 ×x 1ˆ2 +a )/(2 ×y 1) 
 
ν=(− x 1ˆ3 +a×x 1+2 ×b )/(2 ×y 1) 
 
         [0086]     A computation of ┌P1+P2┘ performed when P1≠P2 is called elliptic addition, and a computation of ┌P1+P2┘=┌2×P1┘ performed when P1=P2 is called elliptic doubling. The elliptic addition and elliptic doubling are performed on the basis of combinations among the addition, subtraction, multiplication, squaring, and inversion in the finite field GF (p).  
         [0087]      FIG. 1  shows the elliptic addition.  FIG. 2  shows the elliptic doubling.  
         [0088]     The elliptic addition is, as shown in  FIG. 1 , defined as the point P3 (P3=┌P1+P2┘=(x3, y3)) that is the point that is symmetric, with respect to the X-axis, to the intersection between the elliptic curve and the straight line drawn through the points P1 and P2 (P1=(x1, y1) and P2=(x2, y2)). In  FIG. 1 , the curve expressed as the elliptic curve on the prime field by the equation yˆ2=xˆ3−x is shown, and the curve is defined as below. 
 
 x   3 =(( y   1   −y   2 )/( x   1   −x   2 )) 2   −x   1   −x   2 , 
 
 y   3 =(( y   1   −y   2 )/( x   1   −x   2 ))( x   1   −x   3 )− y   1  
 
         [0089]     The elliptic doubling is, as shown in  FIG. 2 , defined as the point P4 (P4=┌P1+P1┘=┌2×P1┘=(x4, y4)) that is the point that is symmetric, with respect to the X-axis, to the intersection between the elliptic curve and the tangent line to the point P1 (P1=(x1, y1)) on the elliptic curve. In  FIG. 2 , the curve expressed, as the elliptic curve on the prime field, by the equation yˆ2=xˆ3−x is shown, and the curve is defined as below. 
 
 x   4 =((3 x   1 ˆ2−1)/(2 y   1 ) 2 −2 x   1 , 
 
 y   4 =((3 x   1 ˆ2−1)/(2 y   1 ))( x   1   −x   4 )− y   1  
 
         [0090]     The computation of the point ┌d×P┘=┌P+P+ . . . +P┘ (sum of d number of P) with respect to the elliptic curve E on the finite field, the point on the curve called the base point, and the integer d called the scalar is referred to as the scalar multiplication. The scalar multiplication is realized by combining the elliptic addition and the elliptic doubling.  
         [0091]     In many cases, the computation time for the elliptic addition, elliptic doubling and the scalar multiplication are estimated on the basis of the sum of the computing times of the multiplication, squaring, and inversion. This is because the actual elliptic addition, elliptic doubling, and scalar multiplication are performed on the basis of combinations of addition, subtraction, multiplication, squaring, and inversion in the finite field, and in many cases the computation time for the addition and subtraction is negligibly shorter than the other computations.  
         [0092]     Generally, the computation time for inversion in a finite field GF (pˆm) is often much longer than that for multiplication or squaring. Therefore, the projective coordinates system is sometimes used to express points on an elliptic curve.  
         [0093]     By employing the projective coordinates system, points on an elliptic curve on GF (pˆm) are expressed in the form of (X:Y:Z). However, it is assumed that the point (X:Y:Z) and the (r×X:r×Y:r×Z) with respect to the element r on GF (pˆm) (where r≠0) are identified to the same point to each other.  
         [0094]     The equation of an elliptic curve in the projective coordinates system is expressed as below by substituting X/Z for x and Y/Z for y in the original equation. 
 
E:  Yˆ 2 ×Z=Xˆ 3 +a×X×Zˆ 2 +b×Zˆ 3 
 
         [0095]     When the projective coordinates system is used, all the points on an elliptic curve can be expressed in the form of (X:Y:Z). The infinite point ∞=(0:1:0).  
         [0096]     In “Efficient Elliptic Curve Exponentiation Using Mixed Coordinates”, Asiacrypt 1998, Lecture Notes in Computer Science vol. 1514, pp. 51-65, Springer-Verlag, 1998 (document [CMO98]) by H. Cohen, A. Miyaji, and T. Ono, it is reported that the computation time required for elliptic addition in the projective coordinates system on the prime field is 12M+2 S, and the calculation time for elliptic doubling is 7+5 S, where 1M, 1 S respectively express the computation time required for one multiplication, one squaring in the prime field.  
         [0097]     One type of projective coordinates system is the Jacobian coordinate system. In the Jacobian coordinates, points on an elliptic curve of GF (pˆm) are expressed in the form of (X:Y:Z). However, it is assumed that a point (X:Y:Z) and a point (r 2 ×X:r 3 ×Y:r×Z) with respect to the element r on GF (pˆm) (where r≠0) are identified to the same point to each other. The equation of an elliptic curve in the Jacobian coordinates system is expressed as below by substituting X/Z 2  for x, and Y/Z 3  for y in the original equation. 
 
E:  Yˆ 2 ×Z=Xˆ 3 +a×X×Zˆ 4 +b×Zˆ 6 
 
         [0098]     When using the Jacobian coordinate system, all the points on an elliptic curve can be expressed in the form of (X:Y:Z). The infinite point ∞=(0:1:0).  
         [0099]     In the document [CMO98], it is reported that the computation time required for the elliptic addition in the Jacobian coordinates system on the prime field is 12M+4 S, and the computation time required for the elliptic doubling is 4M+6 S, where 1M, 1 S respectively express the computation time required for one multiplication, one squaring in the prime field.  
       (b) Implementation Example of Embodiment  
       [0100]     Hereinafter, a method of an elliptic-curve cryptosystem operation according to an embodiment of the present invention is explained for the case when the method is applied to an elliptic curve on the finite field GF (p) where the element number is p (where p is an integer equal to or greater than 5).  
         [0101]     The elliptic curve E on GF (p) can be expressed in the equation below, 
 
E:  yˆ 2 =xˆ 3 +a×x+b  
 
 where a, b, x, and y are the elements of GF (p), and satisfy the condition below. 
 
4 ×aˆ 3+27 ×bˆ 2≠0 
 
         [0102]      FIG. 3  shows a configuration of the main portion of an elliptic-curve cryptosystem device  11  according to the present invention.  
         [0103]     The elliptic-curve cryptosystem device  11  comprises, as shown in  FIG. 3 , an operation unit (processor)  12  and a storage unit  16 . The storage unit  16  stores operation programs for performing elliptic addition, elliptic doubling and the like (will be described later) for the elliptic-curve cryptosystem.  
         [0104]     The operation unit  12  comprises an operator element  13 , a register group  14 , and an operation result output register group  15 . The operator element  13  executes the elliptic curve cryptographic program stored in the storage unit  16  by using the register group  14 , and outputs the operation result to the operation result output register group  15 .  
         [0105]     The register group  14  and the operation result output register group  15  respectively consist of a plurality of registers, and values used for operations, results of the operations, addresses on memory units of program codes currently executed, and the status of the CPU are stored in these registers. The calculation results obtained in particular by the operator element  13  are stored in the operation result output register group  15 .  
         [0106]      FIG. 4  is a block diagram showing a function configuration of the elliptic-curve cryptographic device  11  according to one embodiment of the present invention.  
         [0107]     The elliptic-curve cryptosystem device  11  comprises, as shown in  FIG. 4 , a random number generation unit  21 , a scalar multiplication process unit  22 , and a randompoint( ) function process unit  23 . The elliptic-curve cryptographic device  11  receives a base point P and a scalar d multiplied by the base point, and outputs the point ┌d×P┘ on an elliptic curve that has been scalar multiplied. The random number generation unit  21  generates random numbers to be used for randomizing values that are used by the scalar multiplication process unit  22  for the operations. The randompoint( ) function process unit  23  is a processing unit for generating coordinate values of random points on an elliptic curve on the basis of random numbers generated by the random number generation unit  21 .  
         [0108]     Implementation examples in which an embodiment of the present invention is applied to the elliptic-curve cryptosystem in the above Algorithms 1′, 2′ 3, and 4 are explained. Hereinafter, a method of an embodiment of the present invention is referred to as RIP.  
         [0109]     First, an implementation example combined with the binary method (LSB) is shown (Algorithm 6).  
         [0110]     (8) Algorithm 8 (RIP (LSB, 0))  
                                                                 S1: R           randompoint( )           S2: T[0]           R, T[2]           P           S3: for i = 0 upto n-1 {                S4:   T[1]           ┌T[0] + T[2]┘           S5:   T[2]           ┌2*T[2]┘           S6:   T[0]           T[d[i]]           S7: }           S8: return ┌T[0] − R┘ ,                      
 
 where R, T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d. Also, the function randompoint ( ) is a function that generates random points on an elliptic curve. In this example, the operations in the algorithm are the same as those in the above binary method (LSB); however, a random value is given as the value to be used in operation. This random value is generated by the function randompoint( ) for each operation; accordingly, even when operations are performed on the basis of an algorithm on a point on the same elliptic curve, the hamming weight whose power value is observed via a power analysis attack differs each time. Accordingly, it is possible to reduce the risk of important information being illegally accessed via a power analysis attack. Additionally, when the process in step S 7  is terminated, the value of T[0] is ┌┌d×P┘+R┘. Next, the method of realizing the function randompoint( ) in Algorithm 6 is explained. 
 
 (Method 1: Generation of Value of X Coordinate at Random) 
 
         [0111]     When generating the point R, the x coordinate is generated at random and it is checked whether or not there is a corresponding y coordinate value. Specifically, when the equation for an elliptic curve on a finite field whose characteristic is equal to or greater than 5 is used as below, 
 
 yˆ 2 =xˆ 3 +a×x+b  
 
 the value of r for the x coordinate is generated at random. Then, the value of rˆ3+a×r+b (the result of substituting r for x included on the right side of the equation) is obtained, and it is checked whether or not this value has square roots. When the value has the square root, the value of the square root is obtained as the y coordinate, and r and this square root are output. When the value does not have the square root, the process restarts from the step of obtaining the random value r. 
 
 (Method 2: Utilization of Table) 
 
         [0112]     A set of random points that are candidates for R is held as a table, and R is selected and output at random from the table each time the function is called.  
         [0000]     (Method 3: Random Number-Fold of Fixed Point) A fixed point Q is held, a random value r is generated each time the function is called, scalar multiplication ┌r×Q┘ is performed, and ┌r×Q┘ is output as R.  
         [0000]     (Method 4: Utilization of Fixed Point)  
         [0113]     The projective coordinates expression for a fixed point Q is held as (X:Y:Z), a random value r is generated each time the function is called, and the result of (r×X:r×Y:r×Z) that is obtained by multiplying r by the respective coordinate values is output as R. The same effect can be attained by using the Jacobian coordinates system.  
         [0000]     (Method 5)  
         [0114]     A fixed point R is held, R is output in response to a call of the function, and an update is performed after the call such that R←┌2×R┘.  
         [0115]     Next, an implementation example that is combined with the binary method (MSB) is shown (Algorithm 7).  
                                                                 (9) Algorithm 7 (RIP (MSB, 0))                                    S1: R           randompoint( )           S2: T[0]           R, T[2]           P           S3: for i = n-1 downto 0 {                S4:   T[0]           ┌2*T[0]┘           S5:   T[1]           ┌T[0] + T[2]┘           S6:   T[0]           T[d[i]]           S7:   R           ┌2*R┘                S8: }           S9: return ┌T[0] − R┘ ,                      
 
 where R, T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d. Also, the function randompoint ( ) is a function that generates random points on an elliptic curve, and this algorithm can be implemented in the same manner as it is in methods 1 through 5. In Algorithm 7, the method of operations of the algorithm are the same as in the above binary method (MSB); however, Algorithm 7 is different from the binary method in that the calculations of random points are included. 
 
         [0116]     In this case, similarly to the above case, resistance to a power analysis attack is realized by including the random point R in the operation. When the process in step S 8  is terminated, the value of T[0] is ┌d×P+R┘.  
         [0117]     Another implementation example combined with the binary method (MSB) is shown below (Algorithm 7′).  
                                                                 (10) Algorithm 7′ (RIP (MSB, 0)′)                                    S1: (R, R′)           randompoint( )           S2: T[0]           R, T[2]           P           S3: for i = n-1 downto 0 {                S4:   T[0]           ┌2*T[0]┘           S5:   T[1]           ┌T[0] + T[2]┘           S6:   T[0]           T[d[i]]                S7: }           S8: return ┌T[0] − R′┘ ,                      
 
 where R, R′, T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d. Also, the function randompoint ( ) is a function that generates a random point and a point related to the random point on an elliptic curve. The method of implementation of the function will be described later. This algorithm operates in a similar manner to the way it does in the binary method (MSB); however, the manner of using the random point is different. The function randompoint( ) generates the value of R required for realizing the tamper resistance and the value of R′ required for removing extra values that are elliptically added to the operation result in step S 7 . In the above algorithm, when the process in step S 7  is terminated, the value of T[0] is ┌d×P+2ˆn×R┘. 
 
         [0118]     As a method of obtaining R′, the following method can be employed.  
         [0000]     (Methods 1′ through 5′)  
         [0119]     In these methods, the point R is obtained by using the respective methods 1 through 5 for each call of the function, and the point R′=┌2ˆn×R┘ is calculated by using this point R′ in order to output the pair of points R and R′.  
         [0000]     (Method 6′)  
         [0120]     In this method, a fixed point R and another fixed point R′(R′=┌2ˆn×R┘) are held, and the pair of points (R, R′) is output in response to the call of the function. After the call, an update is performed in such a manner that R←┌2×R┘ and R′←┌2×R′┘.  
         [0121]     Next, an implementation example combined with the Montgomery method is shown (Algorithm 8).  
                                                                 (11) Algorithm 8 (RIP (Mon, 0+1))                                    S1: (R,R′)           randompoint( )           S2: T[0]           ┌P + R┘, T[1]           ┌┌2*P┘ + R┘           S3: for i = n-2 downto 0 {                S4:   T[2]           ┌2*T[d[i]]┘           S5:   T[1]           ┌T[0] + T[1]┘           S6:   T[0]           T[2-d[i]]           S7:   T[1]           T[1+d[i]]                S8: }           S9: return ┌T[0] − R′┘                      
 
 where R, R′, T[0], T[1], and T[2] represent temporary variables, d represents a scalar value in n bits, and d[i] represents a value of the lower i-th bit of d. Also, the function randompoint ( ) is a function that generates a random point R and a point R′ related to the random point on an elliptic curve. The following method can be employed as the method of implementation of the function. This algorithm operates in a similar manner to the way it operates in the above Montgomery method; however, random points are used. Similarly to Algorithm 7, the function randompoint (generates the value of R required for realizing the tamper resistance and the value of R′ required for obtaining the right value after the operation. In the above algorithm, when the process in step S 8  is terminated, the value of T[0] is ┌d×P+2ˆn×R┘. 
 
         [0122]     The following method can be employed as a method of generating R′.  
         [0000]     (Methods 1″ through 5″)  
         [0123]     In these methods, the point R is obtained by using the respective methods 1 through 5 for each call of the function, and the point R′=┌2ˆ(n−1)×R ┘ is calculated by using this point R in order to output the pair of points R and R′.  
         [0000]     (Method 6″)  
         [0124]     In this method, a fixed point R and another fixed point R=┌2ˆ(n−1)×R┘ are held, and the pair of points (R, R′) is output in response to a call of the function. After the call, an update is performed in such a manner that R←┌2×R┘ and R′ ←┌2×R′┘.  
         [0125]     Next, an implementation example combined with the Window method (four-bit width) is shown (Algorithm 9).  
                                                                                         (12) Algorithm 9 [RIP (W) (four-bit width)]                                    S1: R           randompoint( )           S2: W[0]           0, W[1]           P           S3: for i = 2 upto 15 {                S4:   W[i] = ┌W[i-1] + P┘           S5: }                S6: T[0]           ┌R + W[d[n-1,n-4]]┘           S7: for i = n-5 downto 3 step -4 {                S8:   T[0]           ┌16*T[0]┘           S9:   T[0]           ┌T[0] + W[d[i,i-3]]┘                S10: }           S11: return ┌T[0] − R┘ ,                      
 
 where it is assumed that d represents a scalar value in n bits and n represents a multiple of 4. It is also assumed that d[i, i−3] is a value in four bits starting from the lower i-th bit through the (i−3)th bit of d. W[i] represents a table used in the window method. The function randompoint( ) is a function that generates a random point on an elliptic curve. This algorithm can be implemented by using methods 1 through 5 above. 
 
         [0126]     This algorithm operates in a similar manner to the way it operates in the above Window method; however, random points are used. In this case, when the process in step S 10  is terminated, the value of T[0] is ┌┌d×P┘+R┘; accordingly, in step S 11 , R is deleted from T[0].  
         [0127]     These explanations have been given for cases where p is a prime number equal to or greater than 5, and where the invention is applied to the Elliptic curve E on the finite field GF (p) where p is the element count in the above respective embodiments. However, the scope of the present invention is not limited to these explanations, and the present invention can be implemented while allowing various alterations without departing from the spirit of the present invention.  
         [0128]     Further, these explanations have been given for cases where the present invention is applied to elliptic-curve cryptosystem in the above respective embodiments. However, the present invention can also be applied to RSA cryptosystem while allowing for various alterations without departing from the spirit of the present invention. Here, as one of the alterations, the elliptic-curve cryptosystem operation is replaced with an RSA cryptosystem operation (modular operation on the finite field) as described below.  
         [0000]     elliptic addition ┌P+Q┘→modular multiplication p*q (mod n)  
         [0000]     elliptic doubling ┌2×P┘→square modular pˆ2 (mod n)  
         [0000]     scalar multiplication ┌d×P┘→modular exponentiation operation pˆ2 (mod n)  
         [0000]     inverse element ┌−P┘→p that satisfies the relationship of p*q=1 (mod n) (this q is referred to as pˆ(−1))  
         [0129]     Further, with the present invention being disclosed to the public, it is possible for those skilled in this field of art to implement or produce an elliptic-curve cryptosystem device, an elliptic-curve cryptosystem method, an elliptic-curve cryptosystem program, or a computer readable storage medium storing the elliptic-curve cryptosystem program according to the present invention.  
         [0130]      FIG. 5  shows a hardware environment of a cryptographic device according to an embodiment of the present invention.  
         [0131]     A program stored in an external storage device  33  for realizing embodiments of the present invention is copied onto memory  32  through a bus  39 , and is executed by a CPU  31 . Users&#39; inputs are input through an input device  36 . The input device  36  may be a keyboard, a mouse, a template or the like. Information is displayed to the users through an output device  37 . The output device  37  may be a display device or the like. Additionally, this program can be stored in a transportable storage medium  35  such as a diskette, a CD-ROM, a DVD or the like, and can be executed by the CPU  31  after being copied into the memory  32  by using a medium driving device  34 . Alternatively, it is also possible to read information in the transportable storage medium  35  by using the medium driving device  34  and to perform decryption processes on the information in order to verify users with the above described smart card used as the transportable storage medium  35 . A network connection device  38  connects a cryptographic device to a network. It is also possible for the cryptographic device to receive, through the network, data to be encrypted or to be decrypted in order to process such data. Alternatively, it is also possible for the program to be downloaded to the external storage device  33  via the network and to be installed in the cryptographic device in order for the processes in the embodiments of the present invention to be realized.  
         [0132]     In “Efficient Countermeasures against RPA, DPA and SPA”, CHES 2004, Lecture Notes in Computer Science Vol. 3156, pp. 343-356, Springer-Verlag, 2004, written by H. Mamiya, A. Miyaji, H. Morimoto, (document [MMM04]), the calculation time for one bit is estimated to be 16M+10 S when the exponential division is performed as the scalar multiplication algorithm having resistance to the SPA, DPA, RPA, and ZVA, and an elliptic curve on the prime field is used where 1M and 1 S respectively express the calculation time required for one calculation of the multiplication and squaring on the prime field.  
         [0133]     All of the above described embodiments are resistant to SPA, DPA, RPA, and ZVA. And, the calculation time for one bit is 13M+4 S when the implementation example of the Montgomery method is employed while using an elliptic curve on the prime field where 1M and 1 S respectively express the calculation time required for one calculation of the multiplication and squaring on the prime field. The ratio between 1M and 1 S varies in accordance with calculation environments. However, when the conversion value of 1 S=0.8 S assumed in the document [MMM04] is used, the calculation time required for conventional techniques is 24M, and the calculation time required for the present invention is 16.2 S. Accordingly, in the present invention, the calculation becomes faster by approximately 30%.  
         [0134]     As described above, a cryptographic device according to the present invention is useful for processing RSA cryptosystem and elliptic-curve cryptosystem, and is effective against side channel attacks.