8 October 1999 Modular exponential accelerator chip based on precomputations for RSA cryptography application
Author Affiliations +
Abstract
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, Alex Hariz, 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
PROCEEDINGS
12 PAGES


SHARE
Back to Top