Radix-4 modular multiplication and exponentiation algorithms for the RSA public-key cryptosystem

Jin Hua Hong, Cheng Wen Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)

Abstract

We propose a radix-4 modular multiplication algorithm based on Montgomery's algorithm, and a radix-4 cellular-array modular multiplier based on Booth's multiplication algorithm. The radix-4 modular multiplier can be used to implement fast RSA cryptosystem. Due to reduced number of iterations and pipelining, our modular multiplier is four times faster than the cellular-array modular multiplier based on the original Montgomery's algorithm. The time to calculate a modular exponentiation is about n2 clock cycles, where n is the word length, and the clock cycle is roughly equal to the delay time of a full adder. The utilization of the multiplier is 100% by interleaving consecutive exponentiations. Locality, regularity, and modularity make the proposed architecture suitable for VLSI implementation.

Original languageEnglish
Title of host publicationProceedings of the 2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000
Pages565-570
Number of pages6
DOIs
Publication statusPublished - 2000 Dec 1
Event2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000 - Yokohama, Japan
Duration: 2000 Jan 252000 Jan 28

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Conference

Conference2000 Asia and South Pacific Design Automation Conference, ASP-DAC 2000
CountryJapan
CityYokohama
Period00-01-2500-01-28

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Radix-4 modular multiplication and exponentiation algorithms for the RSA public-key cryptosystem'. Together they form a unique fingerprint.

Cite this