Area and time efficient modular multiplication of large integers

被引：18

作者：

Bunimov, V ^{[1
]}

Schimmler, M ^{[1
]}

机构：

[1] Tech Univ Braunschweig, Inst Comp & Commun Network Engn, D-3300 Braunschweig, Germany

来源：

IEEE INTERNATIONAL CONFERENCE ON APPLICATION-SPECIFIC SYSTEMS, ARCHITECTURES, AND PROCESSORS, PROCEEDINGS | 2003年

关键词：

Modular multiplication; Montgomery algorithm; interleaved modular multiplication; MSB-first arithmetic; carry save addition; redundant number arithmetic;

D O I：

10.1109/ASAP.2003.1212863

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A new modular multiplication algorithm and its corresponding architecture is presented. It is optimised with respect to hardware complexity and latency. Based on the data flow of the well known interleaved modular multiplication the product of two n-bit-integers X and Y modulo M is computed by n iterations of a simple loop. The loop consists of one single carry save addition, a comparison of constant complexity, and a table lookup, where the table contains 6 precomputed values and two constants. By this construction the arithmetical complexity of the modular multiplication is reduced to n additions without carry propagation in total which leads to a speedup of at least two in comparison to all methods previously known. The paper consists of a first algorithm A2 implementing the new idea of combining carry save addition and constant time comparison. A2 is not optimal with respect to area and time. Its correctness is proven. By use of a small amount of precomputing the loop of A2 can be modified such that the effort within the loop is minimised. This leads to the algorithm A3. Its verification concludes the paper.

引用

页码：400 / 409

页数：10

共 26 条

[1]

[Anonymous], RSA HARDWARE IMPLEME

[2] An RNS Montgomery modular multiplication algorithm [J].

Bajard, JC ;

Didier, LS ;

Kornerup, P .

IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (07) :766-776

[3]

BLAKLEY GR, 1983, IEEE T COMPUT, V32, P497, DOI 10.1109/TC.1983.1676262

[4] High-radix montgomery modular exponentiation on reconfigurable hardware [J].

Blum, T ;

Paar, C .

IEEE TRANSACTIONS ON COMPUTERS, 2001, 50 (07) :759-764

[5]

BLUM T, 1999, 14 IEEE S COMP AR AR

[6]

BRICKELL EF, 1983, P CRYPTO 82, P51

[7]

BUNIMOV V, 2002, ISCA 02 WORKSH COMPL

[8] HARDWARE IMPLEMENTATION OF MONTGOMERY MODULAR MULTIPLICATION ALGORITHM [J].

ELDRIDGE, SE ;

WALTER, CD .

IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (06) :693-699

[9] VLSI array algorithms and architectures for RSA modular multiplication [J].

Jeong, YJ ;

Burleson, WP .

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 1997, 5 (02) :211-217

[10]

KIM YS, IMPLEMENTATION 1024

← 1 2 3 →