基于青铜比例加法链的椭圆曲线标量乘算法

doi:10.6040/j.issn.1671-9352.0.2019.028

摘要/Abstract

摘要： 提出一种新的高效安全的椭圆曲线标量乘算法。基于广义的斐波那契数列,提出一个新的加法链,称之为青铜比例加法链(bronze ratio addition chain, BRAC)。该算法每次都迭代执行“3P1+P2”运算,天然具有抵抗简单功耗攻击的性质。BRAC链长较短,结合新的投影坐标,提高了运算效率。实验结果表明,BRAC的标量乘算法比黄金比例加法链(GRAC)快31.73%。

关键词: 标量乘, 青铜比例加法链, 简单功耗攻击, 效率

Abstract: A new efficient and secure elliptic curve scalar multiplication algorithm is proposed. There is an new addition chain based on generalized Fibonacci sequences, which is called bronze ratio addition chain(BRAC). Each iteration of this algorithm executes fixed “3P1+P₂” operation, which can resist the simple power analysis naturally. BRAC has a shorter chain length, combined with the new projection coordinates can improve efficiency of the previous ones. The experimental results show that the new algorithm is 31.73% faster than golden ratio addition chain(GRAC).

Key words: scalar multiplication, bronze ratio addition chain, simple power attack, efficiency

中图分类号:

TP309

刘双根,李丹丹,李潇. 基于青铜比例加法链的椭圆曲线标量乘算法[J]. 《山东大学学报(理学版)》, 2019, 54(11): 12-19.

LIU Shuang-gen, LI Dan-dan, LI Xiao. Elliptic curve scalar multiplication algorithm based on bronze ratio addition chain[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(11): 12-19.

参考文献

[1] KOBLITZ Neal. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(177):203-209.
[2] MILLER Victor. Use of elliptic curves in cryptography[J]. Advances in Cryptology-CRYPTO85, 1986, 19(3):173-193.
[3] RIVEST R, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 26(2):96-99.
[4] LITASARI L, RAHAADJO B. Design and implementation stegocrypto based on elgamal elliptic curve[C] //International Conferences on Information Technology.[S.l.] :[s.n.] , 2017: 95-99.
[5] ZHANG N, TAN S. Elliptic curve scalar multiplication based on Fibonacci number[C] //International Conference on Intelligent Networking and Collaborative Systems.[S.l.] :[s.n.] , 2013: 507-510.
[6] MELONI N. New point addition formulae for ECC applications[C] // International Workshop on the Arithmetic of Finite Fields.[S.l.] :[s.n.] , 2007: 189-201.
[7] 庞世春, 刘淑芬, 从福仲,等. 一种Montgomery型椭圆曲线的高效标量乘算法[J]. 电子学报, 2011, 39(4):865-868. PANG Shichun, LIU Shufen, CONG Fuzhong, et al. An efficient scalar multiplication algorithm on Montgomery-form elliptic curve[J]. ACTA Electronica Sinica, 2011, 39(4):865-868.
[8] KOCHER P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C] //International Cryptology Conference on Advances in Cryptology.[S.l.] :[s.n.] , 1996: 104-113.
[9] SHAH P G, ARA T, AMBAREEN J, et al. Prevention of simple power analysis attacks in elliptical curve cryptography on WSN platform[C] //International Conference on Emerging Trends in Engineering & Technolog.[S.l.] :[s.n.] , 2015: 51-55.
[10] LUO Chao, FEI Yunsi, KAELI David. Effective simple-power analysis attacks of elliptic curve cryptography on embedded systems[C] //International Conference on Computer-Aided Design(ICCAD).[S.l.] :[s.n.] , 2018: 1-7.
[11] SUTAR S A. Differential power attack analysis of ultra-lightweight block cipher BORON[C] //International Conference on Electronics, Communication and Aerospace Technology.[S.l.] :[s.n.] , 2018: 365-370.
[12] GOUNDAR R R, SHIOTA K, TOYONAGA M. SPA resistant scalar multiplication using golden ratio addition chain method[J]. Iaeng International Journal of Applied Mathematics, 2008, 38(2): 83-88.
[13] DOSSO Y, HERBAUT F, MELONI Nicolas, et al. Euclidean addition chains scalar multiplication on curves with efficient endomorphism[J]. Journal of Cryptographic Engineering, 2018, 8(4): 1-17.
[14] SRINATE P, CHIEWTHANAKUL B. A variant of the Schnorr signature using an elliptic curve over a field of characteristic two[C] // International Joint Conference on Computer Science and Software Engineering(JCSSE).[S.l.] :[s.n.] 2018: 1-5.
[15] RAMDANI M, BENMOHAMMED M, BENBLIDIA N. Distributed solution of scalar multiplication on elliptic curves over F_p for resource-constrained networks[C] //International Conference on Future Networks and Distributed.[S.l.] :[s.n.] , 2018.
[16] FARASHAHI R R, WU H, ZHAO C A. Efficient arithmetic on elliptic curves over fields of characteristic three[J]. Selected Areas in Cryptography, 2013(1):135-148.
[17] 邓勇. 基于广义Fibonacci和Lucas数的准循环矩阵研究[J]. 重庆师范大学学报(自然科学版), 2015, 32(6): 72-76. DENG Yong. Research of quasi-cyclic matrices based on generalized Fibonacci and Lucas numbers[J]. Journal of Chongqing Normal University(Natural Science), 2015, 32(6): 72-67.
[18] 张福玲. 广义Fibonacci数列的和公式[J]. 重庆师范大学学报(自然科学版), 2011, 28(5): 45-48. ZHANG Fuling. The finite sum formula for generalized Fibonacci numbers[J]. Journal of Chongqing Normal University(Natural Science), 2011, 28(5): 45-48.
[19] 《数学辞海》编辑委员会. 数学辞海[M]. 太原: 山西教育出版社, 2002. Editorial Board of Mathematical Cihai. Mathematical Cihai[M]. Taiyuan: Shanxi Education Press, 2002.
[20] LIU H, DONG Q, LI Y. Efficient ECC scalar multiplication algorithm based on symmetric ternary in wireless sensor networks[C] //Electromagnetics Research Symposium.[S.l.] :[s.n.] , 2017: 879-885.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed