Patent ID: 8327156

Claim:
A cryptographic processing device, comprising: a memory circuit; a Montgomery modular multiplication operation circuit performing a Montgomery modular multiplication operation plural times for a value set having f-bit values s, t, n, and h and a w-bit value n′ to store them in the memory circuit (where f and w are natural numbers); and a fault attack detection circuit determining whether or not a fault attack occurred for each of at least some parts of the Montgomery modular multiplication operations performed plural times, wherein the Montgomery modular multiplication operation is y=REDC(s, t, n)=s×t×2 −f (mod n) (where y is an f-bit value and REDC is a Montgomery reduction algorithm), the fault attack detection circuit determines that a fault attack occurred when a digit in lower f bits of the value of s×t+h×n calculated by the Montgomery modular multiplication operation circuit involves a value that is not zero, and values in the mathematical expressions satisfy h=s×t×n ′(mod 2 f ), and n′=−n −1 (mod 2 f ).