Patent ID: 8280042

Claim:
A decryption processor for calculating a plaintext m through decryption of a ciphertext c by using a first prime number p, a second prime number q, a public key e, and a private key d, the decryption processor comprising: a first modular exponentiation part that calculates a value m′ p through modular exponentiation modulo the first prime number p, wherein an exponent is a value obtained by shifting, with a numerical value s, a value d p calculated in accordance with d(mod(p−1)), and a base is a value c p calculated in accordance with c(mod p); a second modular exponentiation part that calculates a value m′ q through modular exponentiation modulo the second prime number q, wherein an exponent is a value obtained by shifting, with the numerical value s, a value d q calculated in accordance with d(mod(q−1)), and a base is a value c q calculated in accordance with c(mod q); a composition part that calculates a value m s through calculation of ((u×(m′ q −m′ p )(mod q))×p+m′ p by using the values m′ p and m′ q calculated respectively by the first modular exponentiation part and the second modular exponentiation part and a private key u corresponding to a calculation result of p −1 (mod q); and a shift release part that calculates the plaintext m through calculation of m s ×(c s (mod n))(mod n) by using the value m s calculated by the composition part.