A power-residue calculating circuit includes: an I/F (interface) circuit with respect to an external bus; an e register holding a key e; a Y register holding a multiplier Y for Montgomery conversion; an N register holding a key N; a B2N register holding a value of (2B+N) calculated during the Montgomery conversion; an X register holding a plaintext X; a calculating circuit performing calculations for encryption and decryption; a P register holding a calculation result P; a power-residue control circuit serving as a state machine when the power-residue calculation is performed; a Montgomery multiplication residue/residue control circuit serving as a state machine when the Montgomery multiplication residue calculation and residue calculation are performed; and an addition/subtraction control circuit controlling calculations addition and subtraction.