8 October 1999 Modular exponential accelerator chip based on precomputations for RSA cryptography application
Author Affiliations +
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.
© (1999) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Victor William Ramschie, Victor William Ramschie, Alex Hariz, Alex Hariz, Malcolm R. Haskard, Malcolm R. Haskard, } "Modular exponential accelerator chip based on precomputations for RSA cryptography application", Proc. SPIE 3893, Design, Characterization, and Packaging for MEMS and Microelectronics, (8 October 1999); doi: 10.1117/12.368446; https://doi.org/10.1117/12.368446

Back to Top