Modular exponential accelerator chip based on precomputations for RSA cryptography application

Victor William Ramschie; Alex Hariz; Malcolm R. Haskard

doi:10.1117/12.368446

8 October 1999 Modular exponential accelerator chip based on precomputations for RSA cryptography application

Victor William Ramschie, Alex Hariz, Malcolm R. Haskard

Proceedings Volume 3893, Design, Characterization, and Packaging for MEMS and Microelectronics; (1999) https://doi.org/10.1117/12.368446
Event: Asia Pacific Symposium on Microelectronics and MEMS, 1999, Gold Coast, Australia

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 n²(1 + 1(2l)) cycles to execute one n-bit modular exponentiation. The memory size to accommodate the pre- computed exponents is a 2^l-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.

Citation Download Citation

Victor William Ramschie, Alex Hariz, and 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); https://doi.org/10.1117/12.368446

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available