A systolic linear array for modular multiplication

Author

Gai, Weixin ; Chen, Hongyi

Author_Institution

Inst. of Microelectron., Tsinghua Univ., Beijing, China

fYear

1996

fDate

21-24 Oct 1996

Firstpage

171

Lastpage

174

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;

fLanguage

English

Publisher

ieee

Conference_Titel

ASIC, 1996., 2nd International Conference on

Conference_Location

Shanghai

Print_ISBN

7-5439-0940-5

Type

conf

DOI

10.1109/ICASIC.1996.562779

Filename

562779