Ciphertext X and a constant C having relationships C>p and C>q with respect to secret keys p and q are input, and correction values C.sup.-dp and C.sup.-dq (dp=d mod (p-1), dq=d mod (q-1)) are obtained. Then, the ciphertext X is multiplied by the constant C. A remainder operation using the secret key p or q as a remainder value is conducted with respect to the multiplication result. A modular exponentiation operation based on a Chinese remainder theorem is conducted with respect to the remainder operation result, and a correction operation using a correction value C.sup.-dp or C.sup.-dq is conducted. Thereafter, plaintext Y before being encrypted is calculated.