Systolic multiplier for Montgomery’s algorithm

✍ Scribed by Keon-Jik Lee; Kee-Young Yoo

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 246 KB
• Volume: 32
• Category: Article
• ISSN: 0167-9260
• DOI: 10.1016/s0167-9260(02)00044-5

✦ Synopsis

A new processing element (PE) structure and serial-in-serial-out systolic multiplier are proposed for the efficient implementation of Montgomery's modular multiplication algorithm in RSA cryptosystem. By reorganizing and analyzing the recursive equation of Montgomery algorithm at the Boolean operator level, the critical path delay of the proposed PE is shorter compared with other designs. The critical path delay of the proposed PE is reduced by 9% and 36% when compared to a Walter PE and Guo's bit-serial PE, respectively. Furthermore, the area requirement of the proposed PE is 16% smaller than that of a Walter PE. With a continuous data input, the proposed array can produce multiplication results at a rate of one per n þ 3 cycles with a latency of 3n þ 6 cycles, where n is the bit size of the modulus. The proposed architecture includes the features of regularity, modularity, local interconnection, and unidirectional data flow. Accordingly, it is well suited to VLSI implementation.