Two fast RSA implementations using high-radix montgomery algorithm

Abstract

This paper presents two semi-custom VLSI implementations of 1024-bit RSA public-key cryptosystem in radix-4 and radix-16. These implementations are both based on the same design methodology, in which The R-L binary method and Montgomery algorithm are used for exponentiation and modular multiplication, respectively. The squaring and multiplication operations in the exponentiation are performed in parallel in a systolic modular multiplication unit. Both designs are implemented using AMI semiconductor 0.35 /spl mu/m CMOS technology. Radix-4 implementation resulted in 3.97 ns worst-case clock period with /spl sim/n/sup 2/ worst-case number of cycles (237 Kbps) and 132 K gate count. Radix-16 implementation resulted in 5.1 ns worst-case clock period with /spl sim/n/sup 2//2 worst-case number of cycles (377 Kbps) and 155 K gate count.