A novel radix-4 bit-level modular multiplier for fast RSA cryptosystem
Jinhua Hong, Bin-Yan Tsai, Liang-Te Lu, Shao-Hui Shieh · 2004
Based on modified Booth's algorithm, a radix-4 cellular-array modular multiplier to fulfill the radix-4 modular multiplication algorithm is designed. We implement the modular multiplier in bit level and get rid of the extra control signals shown in by using the concept of guard bits. The radix-4 modular multiplier can be used to implement fast RSA cryptosystem. Due to reduced number of iterations and pipelining, our modular multiplier is four times faster than the cellular-array modular multiplier based on the original Montgomery's algorithm. The time to calculate a modular exponentiation is about n/sup 2/ clock cycles, where n is the word length, and the clock cycle is roughly equal to the delay time of a full adder. The utilization of the multiplier is 100% by interleaving consecutive exponentiations.