Published Articles >> Table of Contents >> Abstract

16th Annual Computer Security Applications Conference (ACSAC'00)   p. 384
The Chinese Remainder Theorem and its application in a high-speed RSA crypto chip
J. Groβchadl, Inst. for Appl. Inf. Process. & Commun., Graz Univ. of Technol., Austria

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ACSAC.2000.898893
Send link to a friend

Abstract
The performance of RSA hardware is primarily determined by an efficient implementation of the long-integer modular arithmetic and the ability to utilize the Chinese Remainder Theorem (CRT) for the private key operations. This paper presents the multiplier architecture of the RSA/spl gamma/ crypto-chip, a high-speed hardware accelerator for long-integer modular arithmetic. The RSA/spl gamma/ multiplier datapath is reconfigurable to execute either one 1024-bit modular exponentiation or two 512-bit modular exponentiations in parallel. Another significant characteristic of the multiplier core is its high degree of parallelism. The actual RSA/spl gamma/ prototype contains a 1056/spl times/16-bit word-serial multiplier which is optimized for modular multiplications according to P. Barret's (1987) modular reduction method. The multiplier core is dimensioned for a clock frequency of 200 MHz and requires 227 clock cycles for a single 1024-bit modular multiplication. Pipelining in the highly parallel long-integer unit allows one to achieve a decryption rate of 560 kbit/s for a 1024-bit exponent. In CRT-mode, the multiplier executes two 512-bit modular exponentiations in parallel, which increases the decryption rate by a factor of 3.5 to almost 2 Mbit/s.
Back to Top Additional Information
Index Terms- public key cryptography; microprocessor chips; reconfigurable architectures; multiplying circuits; clocks; pipeline arithmetic; Chinese Remainder Theorem; RSA/spl gamma/ crypto-chip; RSA encryption scheme; hardware performance; long-integer modular arithmetic; private key operations; multiplier architecture; high-speed hardware accelerator; reconfigurable multiplier datapath; modular exponentiations; parallelism; word-serial multiplier; modular multiplications; modular reduction method; multiplier core; clock frequency; pipelining; decryption rate; 200 MHz; 560 kbit/s; 2 Mbit/s Citation:  J. Groβchadl, "The Chinese Remainder Theorem and its application in a high-speed RSA crypto chip," acsac, p. 384,  16th Annual Computer Security Applications Conference (ACSAC'00),  2000