APPARATUS AND METHOD FOR MODULAR MULTIPLICATION USING CHHINESE REMAINDER THEOREM AND CARRY SAVE ADDER

摘要

A modular multiplication device based on CRT and a CSA, and a method thereof are provided to perform RSA public key encryption at high speed, and realize a small area and low power consumption by using the CRT and the CSA. A multiplier register(130) stores and shifts a multiplier to right. A booth recorder(140) outputs a multiplicand determined according to a condition by using information inputted from the multiplier register and multiplicand information. The CSA comprises the first CSA(110) adding the multiplicand output from the booth recorder to a sum/carry of a previous round and the second CSA(120) adding a modular partial sum of a redirection table(160) to the sum/carry output from the first CSA. 2-bit adders(150,170) calculate and reflect carry generation to the next round. A plurality of multiplexers control a 1-bit input value according to an input signal. Two w-bit adders(180) calculate the final result value from an interim result value of the CSA.