TY - JOUR

T1 - Cellular-array modular multiplier for fast RSA public-key cryptosystem based on modified booth's algorithm

AU - Hong, Jin Hua

AU - Wu, Cheng Wen

N1 - Funding Information:
Manuscript received December 9, 2001; revised April 9, 2002. This work was supported in part by the National Science Council, R.O.C., under Contract NSC91-2215-E-390-001. J.-H. Hong is with the Department of Electrical Engineering, National University of Kaohsiung, Kaohsiung, Taiwan, R.O.C. C.-W. Wu is with the Department of Electrical Engineering, National Tsing Hua University, Hsinchu, Taiwan, R.O.C. (e-mail: cww@ee.nthu.edu.tw). Digital Object Identifier 10.1109/TVLSI.2003.812308

PY - 2003/6/1

Y1 - 2003/6/1

N2 - We propose a radix-4 modular multiplication algorithm based on Montgomery's algorithm, and a fast radix-4 modular exponentiation algorithm for Rivest, Shamir, and Adleman (RSA) public-key cryptosystem. By modifying Booth's algorithm, a radix-4 cellular-array modular multiplier has been designed and simulated. The radix-4 modular multiplier can be used to implement the RSA cryptosystem. Due to reduced number of iterations and pipelining, our modular multiplier is four times faster than a direct radix-2 implementation of Montgomery's algorithm. The time to calculate a modular exponentiation is about n2 clock cycles, where n is the word length, and the clock cycle is roughly the delay time of a full adder. The utilization of the array multiplier is 100% when we interleave consecutive exponentiations. Locality, regularity, and modularity make the proposed architecture suitable for very large scale integration implementation. High-radix modular-array multipliers are also discussed, at both the bit level and digit level. Our analysis shows that, in terms of area-time product, the radix-4 modular multiplier is the best choice.

AB - We propose a radix-4 modular multiplication algorithm based on Montgomery's algorithm, and a fast radix-4 modular exponentiation algorithm for Rivest, Shamir, and Adleman (RSA) public-key cryptosystem. By modifying Booth's algorithm, a radix-4 cellular-array modular multiplier has been designed and simulated. The radix-4 modular multiplier can be used to implement the RSA cryptosystem. Due to reduced number of iterations and pipelining, our modular multiplier is four times faster than a direct radix-2 implementation of Montgomery's algorithm. The time to calculate a modular exponentiation is about n2 clock cycles, where n is the word length, and the clock cycle is roughly the delay time of a full adder. The utilization of the array multiplier is 100% when we interleave consecutive exponentiations. Locality, regularity, and modularity make the proposed architecture suitable for very large scale integration implementation. High-radix modular-array multipliers are also discussed, at both the bit level and digit level. Our analysis shows that, in terms of area-time product, the radix-4 modular multiplier is the best choice.

UR - http://www.scopus.com/inward/record.url?scp=0042466579&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0042466579&partnerID=8YFLogxK

U2 - 10.1109/TVLSI.2003.812308

DO - 10.1109/TVLSI.2003.812308

M3 - Article

AN - SCOPUS:0042466579

SN - 1063-8210

VL - 11

SP - 474

EP - 484

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IS - 3

ER -