Patent ID: 8638927

Claim:
A cryptographic processing method that repeatedly executes a modular-multiplication operation in which multiplication and a remainder operation are performed with respect to a first input and a second input so as to perform a modular-exponentiation operation that is expressed by: M=C d mod N where C represents an input value, d represents key data, M represents output data, and mod N represents a remainder operation based on modulus N so as to perform encryption and decryption, the method comprising: inputting random number data and the key data d, and of calculating key data d′ by subtracting the random number data r from the key data d; calculating values −C and −C 2 with respect to the input data C, and of storing the values C, −C, and −C 2 when an operation starts; and executing the modular-multiplication operation using a result of a previously repeated operation as the first input and the second input in a first operation cycle which is sequentially and repeatedly executed starting from significant bits corresponding to respective bit values d i (0≦i≦n−1) that constitute the key data d, selectively reading one of the stored values C, −C, and −C 2 in accordance with the combination of bit value d′ i corresponding to the bit value d i that constitutes the key data d′ and the bit value r i corresponding to the bit value d i that constitutes the random number data r so as to use the read value as the second input, and executing the modular-multiplication operation using the result of the previously repeated operation as the first input or by skipping the modular-multiplication operation so as to obtain the result of the currently repeated operation in a second operation cycle subsequent to the first operation cycle, wherein in the second operation cycle in the repeated modular-multiplication operation: skipping the modular-multiplication operation when the bit value d′ i =0 and the bit value r i =0 are satisfied; reading a value of the stored value −C to use the value as the second input, using a result of the previously repeated operation as the first input, and executing the modular-multiplication operation when the bit value d′ i =0 and the bit value r i =1 are satisfied; reading a value of the stored value C to use the value as the second input, using a result of the previously repeated operation as the first input, and executing the modular-multiplication operation when the bit value d′ i =1 and the bit value r i =0 are satisfied; and reading a value of the stored value −C 2 to use the value as the second input, using a result of the previously repeated operation as the first input, and executing the modular-multiplication operation when the bit value d′ i =1 and the bit value r i =1 are satisfied.