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
关键词
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 条
  • [1] Akhavi A, 2000, LECT NOTES COMPUT SC, V1853, P373
  • [2] [Anonymous], 2003, Modern Computer Algebra
  • [3] [Anonymous], 1862 FIPS NIST
  • [4] Bajard J.-C., 2005, P ADV SIGN PROC ALG, V5910, P247
  • [5] Bajard J.-.C., 2014, INT C SMART CARD RES, P139
  • [6] A full RNS implementation of RSA
    Bajard, JC
    Imbert, L
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 2004, 53 (06) : 769 - 774
  • [7] Bajard JC, 2004, LECT NOTES COMPUT SC, V3156, P62
  • [8] An RNS Montgomery modular multiplication algorithm
    Bajard, JC
    Didier, LS
    Kornerup, P
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (07) : 766 - 776
  • [9] RNS Arithmetic Approach in Lattice-based Cryptography Accelerating the "Rounding-off" Core Procedure
    Bajard, Jean-Claude
    Eynard, Julien
    Merkiche, Nabil
    Plantard, Thomas
    [J]. IEEE 22ND SYMPOSIUM ON COMPUTER ARITHMETIC ARITH 22, 2015, : 113 - 120
  • [10] Bigou K., 2013, P 15 S ARCH NOUV MAC, P1