Patent ID: 7412474

Claim:
A Montgomery modular multiplier of a public-key cryptographic system that calculates a value congruent to “ABR −1 ” (mod M) used in the cryptographic system, where A and B are input n-bit numbers, R −1 is an inverse number of R modular-multiplied for “mod M”, and M is a modulus, the Montgomery modular multiplier comprising: an A-register storing a bit value a i (where ‘i’ denotes an integer in the range of 0 to n−1) of the number A, which is smaller than the modulus M; a B-register storing a bit value b i of the number B, which is smaller than the modulus M; an M-register storing a bit value m i of the modulus M, which is an odd number; a b i A calculation logic circuit multiplying the number A by the bit value b i to obtain b i A; a q i calculation logic circuit solving a Boolean logic equation “s 0 XOR c 0 XOR (b i AND a 0 )”, where s 0 is the least significant bit (LSB) of a sum S, c 0 is the LSB of a carry C, b i is the bit value of the number B, and a 0 is the LSB of the number A, to obtain a bit value q i ; a q i M calculation logic circuit multiplying the modulus M by the bit value q i to obtain q i M; a 4-2 compressor performing ‘n’ additions on the carry C, the sum S, the b i A, and the q i M to obtain interim values and summing the interim values to obtain a result using a carry propagation adder in response to a carry propagation adder signal; an S-register in which a bit value s i of the sum S is updated and stored; and a C-register in which a bit value c i of the carry C is updated and stored.