A full RNS implementation of RSA

被引：156

作者：

Bajard, JC ^{[1
]}

Imbert, L ^{[1
]}

机构：

[1] LIRMM, Lab Informat Robot & Microelect Montpellier, F-34392 Montpellier 5, France

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2004年 / 53卷 / 06期

关键词：

cryptography; RSA; Montgomery multiplication; Residue Number Systems;

D O I：

10.1109/TC.2004.2

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present the first implementation of RSA in the Residue Number System (RNS) which does not require any conversion, either from radix to RNS beforehand or RNS to radix afterward. Our solution is based on an optimized RNS version of Montgomery multiplication. Thanks to the RNS, the proposed algorithms are highly parallelizable and seem then well suited to hardware implementations. We give the computational procedure both parties must follow in order to recover the correct result at the end of the transaction (encryption or signature).

引用

页码：769 / 774

页数：6

共 17 条

[1] Modular multiplication and base extensions in residue number systems [J].

Bajard, JC ;

Didier, LS ;

Kornerup, P .

ARITH-15 2001: 15TH SYMPOSIUM ON COMPUTER ARITHMETIC, PROCEEDINGS, 2001, :59-65

[2]

BAJARD JC, 2003, 03021 LIRMM

[3]

Brickell E.F., 1990, P ADV CRYPT CRYPTO 8, P368

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

ELDRIDGE, SE ;

WALTER, CD .

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

[5]

Garner HarveyL., 1959, IRE Transactions on Electronic Computers, VEC -8, P140, DOI DOI 10.1109/TEC.1959.5219515

[6]

Kawamura S, 2000, LECT NOTES COMPUT SC, V1807, P523

[7] Analyzing and comparing Montgomery multiplication algorithms [J].

Koc, CK ;

Acar, T ;

Kaliski, BS .

IEEE MICRO, 1996, 16 (03) :26-33

[8]

Menezes A. J, 1997, HDB APPL CRYPTOGRAPH

[9]

MONTGOMERY PL, 1985, MATH COMPUT, V44, P519, DOI 10.1090/S0025-5718-1985-0777282-X

[10]

NOZAKI H, 2001, P 3 INT WORKSH CRYPT, P364

← 1 2 →