401 stores, in 302, key d′ obtained by subtracting random number 2r held in 201 from key d held in 105. When an operation starts, the values “−C” and “−C2” are calculated respectively, and the resultant values are stored in a multiplication table memory 205 together with value “C”. In a first operation cycle, 107 selects and outputs an intermediate value 108 held in an in-operation data register 103, and thereby makes a modular-multiplication operation circuit 104 perform squaring. In the second operation cycle, 107 selects and outputs one of three values held in 205 in accordance with the combination of key bit value d′i and random number bit value ri, and thereby makes the modular-multiplication operation circuit 104 perform multiplication. Thereby, a cryptographic processing device that requires a short operation time period, small circuit scale, and has sufficient security can be realized.