<p>Disclosed is an encryption processing device that is tamper-proof against special PAs that use chosen message pairs. A constant multiplier (3901) inputs a base and a modulo n, performs modular exponentiation modulo n with a prescribed constant as the exponent and with base a, and outputs the result of this calculation as base b. A personal key converter (3904) inputs a personal key (d) and calculates a personal key (d') as the quotient when d is divided by the prescribed constant. A correction key generator (3907) generates a correction key (d") as the remainder of the aforementioned division. A modular exponentiation unit (3905) performs modular exponentiation base b with d' as the exponent. A modular exponentiation unit (3906) performs modular exponentiation base a with d" as the exponent, and outputs a correction value. A correction calculation unit (3908) multiplies the outputs of the modular exponentiation units (3905 and 3906) and outputs the result as the encryption processing result.</p>
