一种新的余数系统下快速计算素域椭圆曲线点乘的方法

J4 ›› 2014, Vol. 36 ›› Issue (10): 1839-1845.

• 论文 • 下一篇

一种新的余数系统下快速计算素域椭圆曲线点乘的方法

吴焘1，李树国2，刘理天2

（1.清华大学微电子与纳电子学系，北京 100084；2.清华大学微电子学研究所，北京 100084）

收稿日期:2013-04-19 修回日期:2013-06-25 出版日期:2014-10-25 发布日期:2014-10-25
基金资助:
国家863计划资助项目（2012AA011402）；国家自然科学基金资助项目（61073173）；清华大学自主科研发展规划（20111081040）

A new RNS approach for fast
Fp elliptic curve point multiplication

WU Tao1,LI Shuguo2,LIU Litian2

(1.Department of Microelectronics and Nanoelectronics,Tsinghua University,Beijing 100084;
2.Institute of Microelectronics, Tsinghua University,Beijing 100084,China)

Received:2013-04-19 Revised:2013-06-25 Online:2014-10-25 Published:2014-10-25

摘要/Abstract

摘要：

椭圆曲线密码运算主要是椭圆曲线点乘，后者由一系列的模乘构成。利用余数系统下的蒙哥马利模乘算法，素域中对阶取模余的模乘可以转化为对余数系统基底取模余。提出一种新的余数系统下的方法以加速计算椭圆曲线点乘。（1）与传统上取两个几乎对称的余数系统不同，该方法取了两个非对称的余数系统。其中，余数系统Γ包括两个模数{2L, 2 L-1}; 余数系统Ω包括八个模数，它们都具有如2L－2Ki+1的形式。这种选择使其模算术变得简单。（2）在上述非对称的余数系统中，大部分原来需要对椭圆曲线域特征值取模的模乘运算可以在余数系统中直接用乘法代替。此外，计算椭圆曲线点乘时用到了仅计算x坐标的蒙哥马利梯子。在每次并行的倍点和点加结束时，需要四次余数系统下的蒙哥马利模乘，以压缩中间结果的值域。因此，计算一个N位的椭圆曲线点乘，需要的时间约为55.5N·I, 其中，I是一个L/2位的乘法、一次保留进位加法、一个L/2位的加法的总延时。

关键词: 余数系统, 椭圆曲线点乘, 蒙哥马利梯子

Abstract:

The basic computation in Elliptic Curve Cryptography (ECC) is Elliptic Curve Point Multiplication (ECPM), which consists of a series of modular multiplications.Through Montgomery modular multiplications in Residue Number System (RNS),the modular multiplications inFpcan be transformed into modular arithmetic over RNS moduli.A new RNS approach is proposed to accelerate ECPM.Firstly,instead of almost two symmetric RNSs,two asymmetric RNSs are chosen,with 2 moduli {2L, 2 L-1} for RNS Γ and 8 moduli with the form of　2L－2Ki+1 for RNS Ω,which makes the modular reductions quite easy.Secondly,in the asymmetric RNSs,most modular multiplications can be performed by direct multiplications in RNS rather than modular multiplications in Fp.Especially,Montgomery ladder with only x coordinates is used for ECPM. At the end of every parallel point doubling and point addition,4 RNS Montgomery modular multiplications are performed to narrow the output range.As a result, the total time for an Nbit Fp ECPM is around 55.5N·I,with I being the time delay of a (L/2)bit multiplication,a carry save addition,and a (L/2)bit full addition.

Key words: RNS;elliptic curve point multiplication;Montgomery ladder

吴焘1，李树国2，刘理天2. 一种新的余数系统下快速计算素域椭圆曲线点乘的方法[J]. J4, 2014, 36(10): 1839-1845.

WU Tao1,LI Shuguo2,LIU Litian2. A new RNS approach for fast
Fp elliptic curve point multiplication [J]. J4, 2014, 36(10): 1839-1845.

参考文献［27］

［1］	Koblitz N. Elliptic curve cryptosystems［J］. Mathematics of Computation,1987, 48:203209.
［2］	Hankerson D,Menezes A,Vanstone S.Guide to elliptic curve cryptography［M］. New York:SpringerVerlag, 2004.
［3］	Brown M,Hankerson D,Lpez J,et al.Software implementation of the NIST elliptic curves over prime fields［C］∥Proc of Topics in CryptologyCTRSA 2001, 2001:250265.
［4］	Güneysu T, Paar C. Ultra high performance ECC over NIST primes on commercial FPGAs［C］∥Proc of International Workshop on Cryptographic Hardware and Embedded Software, 2008:6278.
［5］	Orlando G, Paar C. A scalable GF(p) elliptic curve processor architecture for programmable hardware［C］∥Proc of International Workshop on Cryptographic Hardware and Embedded Systems. Lecture Notes in Computer Science, 2001:348363.
［6］	rs S, Batina L, Preneel B. Hardware implementation of elliptic curve processor over GF(p)［C］∥Proc of IEEE International Conference on ApplicationSpecific Systems, Architectures, and Processors, 2003:433443.
［7］	Schinianakis D, Kakarountas A, Stouraitis T. A new approach to elliptic curve cryptography:An RNS architecture［C］∥Proc of IEEE MELECON, 2006:12411245.
［8］	Schinianakis D, Fournaris A, Kakarountas H M A, et al. An RNS implementation of an Fp elliptic curve point multiplier［J］. IEEE Transactions on Circuits and Systems, I:Regular Papers, 2009, 56(6):12021213.
［9］	Esmaeildoust M, Schinianakis D, Javashi H, et al. Efficient RNS implementation of elliptic curve point multiplication over GF(p)［J］. IEEE Transactions on Very Large Scale Integration(VLSI) Systems, 2013,21(8):15451549.
［10］	Guillermin N. A high speed coprocessor for elliptic curve scalar multiplications over Fp［C］∥Proc of International Workshop on Cryptographic Hardware and Embedded Systems, 2010:4864.
［11］	Wu T, Liu L. Elliptic curve point multiplication by generalized Mersenne numbers［J］. Journal of Electronic Science and Technology, 2012, 10(3):199208.
［12］	Posch K,Posch R.Modulo reduction in residue number system［J］. IEEE Transactions on Parrallel and Distributed Systems, 1995, 6(5):449454.
［13］	Kawamura S, Koike M, Sano F, et al. Coxrower architecture for fast parallel Montgomery multiplication［C］∥Proc of Advances in CryptologyEuroCrypt, 2000:523538.
［14］	Ciet M, Neve M, Peeters E, et al. Parallel FPGA implementation of RSA with residue number systemscan sidechannel threats be avoided?［C］∥Proc of the 46th IEEE Midwest Symposium on Circuits and Systems, 2003:806810.
［15］	Bajard J,Didier L,Kornerup P.An RNS Montgomery modular multiplication algorithm［J］. IEEE Transactions on Computers, 1998, 47(7):766776.
［16］	Bajard J, Didier L, Kornerup P. Modular multiplication and base extensions in residue number systems［C］∥Proc of the 15th IEEE Symposium on Computer Arithmetic, 2001:5965.
［17］	Bajard J, Imbert L. A full RNS implementation of RSA［J］. IEEE Transactions on Computers, 2004, 53(6):769774.
［18］	Soderstrand M, Jenkins W, Jullien G, et al. Residue number system arithmetic:Modern applications in signal processing［M］. New York:IEEE Press, 1986.
［19］	Shenoy A, Kumaresan R. Fast base extension using a redundant modulus in RNS［J］. IEEE Transactions on Computers, 1989, 38(2):292297.
［20］	Nozaki H, Motoyama M, Shimbo A. et al. Implementation of RSA algorithm based on RNS Montgomery modular multiplication［C］∥Proc of the 3rd International Workshop on Cryptographic Hardware and Embedded Systems, 2001:364376.
［21］	Bajard J, Duquenne S, Meloni N. Combining Montgomery ladder for elliptic curves defined over Fp and RNS representation［R］. Technical report,D683,France:LIRMM,2006.
［22］	Montgomery P L. Speeding the pollard and elliptic curve methods of factorization［J］. Mathematics of Computation, 1987, 48(177):243264.
［23］	Anto S, Bajard J, Sousa L. Elliptic curve point multiplication on GPUs［C］∥Proc of the 21st IEEE International Conference on Applicationspecific Systems, Architectures and Processors, 2010:192199.
［24］	Hiasat A. New efficient structure for a modular multiplier for RNS［J］. IEEE Transations on Computers, 2000, 49(2):170174.
［25］	Bajard J, Kaihara M, Plantard T. Selected RNS bases for modular multiplication［C］∥Proc of the 19th IEEE Symposium on Computer Arithmetic, 2009:2532.
［26］	Yang Tongjie, Dai Zibin, Yang Xiaohui, et al. An improved RNS Montgomery modular multiplier［C］∥Proc of International Conference on Computer Application and System Modeling, 2010:144147.
［27］	Gandino F, Lamberti F, Bajard JC, et al. A general approach for improving RNS Montgomery exponentiation using preprocessing［C］∥Proc of the 20th IEEE Symposium on Computer Arithmetic, 2011：2527.

一种新的余数系统下快速计算素域椭圆曲线点乘的方法

A new RNS approach for fast
Fp elliptic curve point multiplication

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献［27］

相关文章 0

编辑推荐

Metrics

本文评价

一种新的余数系统下快速计算素域椭圆曲线点乘的方法

A new RNS approach for fast Fp elliptic curve point multiplication

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［27］

相关文章 0

编辑推荐

Metrics

本文评价

A new RNS approach for fast
Fp elliptic curve point multiplication

参考文献［27］