Cellular-array modular multiplier for fast RSA public-key cryptosystem based on modified Booth's algorithm
| Autor: | Jin-Hua Hong, Cheng-Wen Wu |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Modular exponentiation
Modular arithmetic Cycles per instruction Tonelli–Shanks algorithm Multiplier (Fourier analysis) Hardware and Architecture Cryptosystem Algorithm design Booth's multiplication algorithm Hardware_ARITHMETICANDLOGICSTRUCTURES Electrical and Electronic Engineering Arithmetic Software Mathematics |
| Zdroj: | IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 11:474-484 |
| ISSN: | 1557-9999 1063-8210 |
| DOI: | 10.1109/tvlsi.2003.812308 |
| Popis: | We propose a radix-4 modular multiplication algorithm based on Montgomery's algorithm, and a fast radix-4 modular exponentiation algorithm for Rivest, Shamir, and Adleman (RSA) public-key cryptosystem. By modifying Booth's algorithm, a radix-4 cellular-array modular multiplier has been designed and simulated. The radix-4 modular multiplier can be used to implement the RSA cryptosystem. Due to reduced number of iterations and pipelining, our modular multiplier is four times faster than a direct radix-2 implementation of Montgomery's algorithm. The time to calculate a modular exponentiation is about n/sup 2/ clock cycles, where n is the word length, and the clock cycle is roughly the delay time of a full adder. The utilization of the array multiplier is 100% when we interleave consecutive exponentiations. Locality, regularity, and modularity make the proposed architecture suitable for very large scale integration implementation. High-radix modular-array multipliers are also discussed, at both the bit level and digit level. Our analysis shows that, in terms of area-time product, the radix-4 modular multiplier is the best choice. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|