A decryption processor for calculating a plaintext through decryption of a ciphertext c includes, a first part that calculates m′p through modular exponentiation modulo a first prime number p wherein an exponent is a shifted value of d(mod(p−1)), and a base is a value of c(mod p); a second modular exponentiation part that calculates m′q through modular exponentiation modulo a second prime number q, wherein an exponent is a value of d(mod(q−1)) and a base is a value of c(mod q); a composition part that calculates ms through calculation of ((u×(m′q−m′p)(mod q))×p+m′p by using the values m′p and m′q and a private key u corresponding to p−1(mod q); and a shift release part that calculates the plaintext m through calculation of ms×(cs(mod n))(mod n) by using the value ms.