Share Email Print
cover

Proceedings Paper

Modular exponential accelerator chip based on precomputations for RSA cryptography application
Author(s): Victor William Ramschie; Alex Hariz; Malcolm R. Haskard
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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.

Paper Details

Date Published: 8 October 1999
PDF: 12 pages
Proc. SPIE 3893, Design, Characterization, and Packaging for MEMS and Microelectronics, (8 October 1999); doi: 10.1117/12.368446
Show Author Affiliations
Victor William Ramschie, Univ. of South Australia (Australia)
Alex Hariz, Univ. of South Australia (Australia)
Malcolm R. Haskard, Univ. of South Australia (Australia)


Published in SPIE Proceedings Vol. 3893:
Design, Characterization, and Packaging for MEMS and Microelectronics
Bernard Courtois; Serge N. Demidenko, Editor(s)

© SPIE. Terms of Use
Back to Top