Title :
A systolic linear array for modular multiplication
Author :
Gai, Weixin ; Chen, Hongyi
Author_Institution :
Inst. of Microelectron., Tsinghua Univ., Beijing, China
Abstract :
In this paper, a novel systolic, linear-array modular multiplier is presented which ideally performs the algorithm of P.L. Montgomery (1985). The total execution time for an n-bit modular multiplication is 4n+1 cycles. With only one full adding in one pipeline stage and the purely nearest neighbor communication, it can operate at a high clock frequency. On the other hand, every processing element is simple, mainly consisting of one full adder and five flip-flops. For n-bit modular multiplication, the cost of implementation is 29n gates. So our designed systolic array for modular multiplication is a speed and area efficient system suitable for the VLSI implementation of modular exponentiation which is a kernel operation used in many public-key cryptosystems such as RSA. With clock frequency of 200 megahertz which is practical in 0.8 μm CMOS processing, the throughput can be 64k bits per second
Keywords :
CMOS logic circuits; VLSI; application specific integrated circuits; multiplying circuits; parallel algorithms; pipeline arithmetic; public key cryptography; systolic arrays; 0.8 micron; 200 MHz; 64 kbit/s; CMOS processing; RSA; VLSI implementation; area efficient system; flip-flops; full adder; high clock frequency; modular exponentiation; modular multiplication; nearest neighbour communication; pipeline stage; public-key cryptosystems; systolic linear array; Clocks; Costs; Flip-flops; Frequency; Kernel; Nearest neighbor searches; Pipelines; Public key cryptography; Systolic arrays; Very large scale integration;
Conference_Titel :
ASIC, 1996., 2nd International Conference on
Conference_Location :
Shanghai
Print_ISBN :
7-5439-0940-5
DOI :
10.1109/ICASIC.1996.562779
