A new algorithm, Square-and-Multiply for Modular Exponentiation (SMME), is proposed to calculate a modular exponentiation that is the core arithmetic function in RSA cryptography. The SMME scans the exponent form its MSB and pre-computes a set of exponents to the maximum bit length of l. These pre-computed exponents are stored in a look-up table. By using the look-up table, the number of multiplications required for modular exponentiation can be reduced. Modular multiplications are performed using a modified Montgomery's algorithm. The SMME takes in the order of n2(1 + 1(2l)) cycles to execute one n-bit modular exponentiation. The memory size to accommodate the pre- computed exponents is a 2l-1 (n + 1)-bit RAM. The SMME, with its regularity and local connections in a systolic array, makes it suitable for VLSI implementation. A 64-bit modular exponentiation chip is being designed using a 0.8 micrometers CMOS standard cell library from AMS. The simulation result show that at 25 MHz, the throughput is approximately 236 KBps; and an estimation of 40 KBps for a 512-bit exponent.
|