Binary-Ternary Plus-Minus Modular Inversion in RNS

被引：6
作者：
Bigou, Karim [1 ,2 ]
Tisserand, Arnaud [1 ,2 ]
机构：
[1] Univ Rennes 1, CNRS, IRISA Lab, F-22300 Lannion, France
[2] INRIA, Ctr Rennes Bretagne Atlantique, F-22300 Lannion, France
来源：
IEEE TRANSACTIONS ON COMPUTERS | 2016年 / 65卷 / 11期
关键词：
Residue number system; modular arithmetic; extended Euclidean algorithm; ECC; FPGA; MULTIPLICATION;
D O I：
10.1109/TC.2016.2529625
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
A fast RNS modular inversion for finite fields arithmetic has been published at CHES 2013 conference. It is based on the binary version of the plus-minus Euclidean algorithm. In the context of elliptic curve cryptography (i.e., 160550 bits finite fields), it significantly speeds-up modular inversions. In this paper, we propose an improved version based on both radix 2 and radix 3. This new algorithm leads to 30 percent speed-up for a maximal area overhead about 4 percent on Virtex 5 FPGAs.
引用
收藏
页码：3495 / 3501
页数：7
相关论文
共 35 条
  • [11] Bigou K., 2014, THESIS
  • [12] Single Base Modular Multiplication for Efficient Hardware RNS Implementations of ECC
    Bigou, Karim
    Tisserand, Arnaud
    [J]. CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS - CHES 2015, 2015, 9293 : 123 - 140
  • [13] Bigou K, 2013, LECT NOTES COMPUT SC, V8086, P233, DOI 10.1007/978-3-642-40349-1_14
  • [14] SYSTOLIC VLSI ARRAYS FOR POLYNOMIAL GCD COMPUTATION
    BRENT, RP
    KUNG, HT
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1984, 33 (08) : 731 - 736
  • [15] On-the-Fly Multi-Base Recoding for ECC Scalar Multiplication without Pre-Computations
    Chabrier, Thomas
    Tisserand, Arnaud
    [J]. 2013 21ST IEEE SYMPOSIUM ON COMPUTER ARITHMETIC (ARITH), 2013, : 219 - 228
  • [16] Cheung RCC, 2011, LECT NOTES COMPUT SC, V6917, P421, DOI 10.1007/978-3-642-23951-9_28
  • [17] Ciet M, 2003, PROCEEDINGS OF THE 46TH IEEE INTERNATIONAL MIDWEST SYMPOSIUM ON CIRCUITS & SYSTEMS, VOLS 1-3, P806
  • [18] Crandall Richard E., 1992, Worldwide Applications for Publication, Patent No. [5159632, 5150969A, 5150969]
  • [19] RNS arithmetic in F-pk and application to fast pairing computation
    Duquesne, Sylvain
    [J]. JOURNAL OF MATHEMATICAL CRYPTOLOGY, 2011, 5 (01) : 51 - 88
  • [20] An Algorithmic and Architectural Study on Montgomery Exponentiation in RNS
    Gandino, Filippo
    Lamberti, Fabrizio
    Paravati, Gianluca
    Bajard, Jean-Claude
    Montuschi, Paolo
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 2012, 61 (08) : 1071 - 1083
1234