Montgomery modular multiplier using a compressor and multiplication method

A method of performing a Montgomery modular multiplication in a Montgomery modular multiplier of a public-key cryptographic system, in which the Montgomery modular multiplier includes registers for storing bit values ai, bi, mi, ci, and si (where ‘i’ denotes an integer in the range of 0 to n−1) of a word A, a word B, a modulus M, a carry C, and a sum S, respectively, and calculates a value congruent to “ABR−1” (mod M), 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 method comprising:

• receiving the number A, the number B, and the modulus M;
• multiplying the number A by a bit value bi to obtain each bit of biA;
• solving a Boolean logic equation “s0 XOR c0 XOR (bi AND a0)”, where s0 is the least significant bit (LSB) of a sum S, c0 is the LSB of a carry C, bi is the bit value of the number B, and a0 is the LSB of the number A, to obtain a bit value qi;
• multiplying the modulus M by the bit value qi to obtain each bit of qiM;
• performing ‘n’ additions on the carry C, the sum S, the biA, and the qiM to obtain interim values for each bit of the sum S and the carry C in a carry save adder structure, in response to a carry propagation adder signal;
• and
• summing the interim values to obtain the final results of the sum S and the carry C in a carry propagation adder structure, in response to the carry propagation adder signal.

A Montgomery modular multiplier of a public-key cryptographic system, comprising:

• a multiplicand register, storing a bit value ai of a number A;
• a modulus register, storing a bit value mi of a modulus M;
• a multiplier register, storing a bit value bi of a number B;
• a biA calculation logic circuit multiplying the number A by a bit value bi to obtain each bit of biA;
• a qi calculation logic circuit solving a Boolean logic equation “s0 XOR c0 XOR (bi AND a0)”, where s0 is the least significant bit (LSB) of a sum S, c0 is the LSB of a carry C, bi is the bit value of the number B, and a0 is the LSB of the number A, to obtain a bit value qi (where ‘i’ denotes an integer in the range of 0 to n−1);
• a qiM calculation logic circuit multiplying the modulus M by the bit value qi to obtain each bit of qiM;
• and
• a t-s compressor, wherein t>3 and s>1, performing ‘n’ additions on the carry C, the sum S, the biA, and the qiM to obtain interim values for each bit of the sum S and the carry C in a carry save adder structure and summing the interim values to obtain final results of the sum S and the carry C in a carry propagation adder structure, in response to a carry propagation adder signal.

A system embodying a Montgomery modular multiplier of a public-key cryptographic system, the system comprising:

• an A-register storing a bit value ai (where ‘i’ denotes an integer in the range of 0 to n−1) of an n-bit number A;
• a B-register storing a bit value bi of an n-bit number B;
• an M-register storing a bit value mi of an n-bit modulus M;
• a biA calculation logic circuit multiplying the number A by the bit value bi to obtain biA;
• a qi calculation logic circuit solving a Boolean logic equation “s0 XOR c0 XOR (bi AND a0)”, where s0 is the least significant bit (LSB) of a sum S, c0 is the LSB of a carry C, bi is the bit value of the number B, and a0 is the LSB of the number A, to obtain a bit value qi;
• a qiM calculation logic circuit multiplying the modulus M by the bit value qi to obtain qiM;
• a compressor performing ‘n’ additions on the carry C, the sum S, the biA, and the qiM 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 si of the sum S is updated and stored;
• and
• a C-register in which a bit value ci of the carry C is updated and stored;
• wherein given that the number A is smaller than the modulus M, the number B is smaller than the modulus M, the modulus M is odd, and R−1 is an inverse number of R modular-multiplied for “mod M”, the system calculates a value congruent to “ABR−1” (mod M).