JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2019, Vol. 54 ›› Issue (11): 12-19.doi: 10.6040/j.issn.1671-9352.0.2019.028

Previous Articles     Next Articles

Elliptic curve scalar multiplication algorithm based on bronze ratio addition chain

LIU Shuang-gen, LI Dan-dan, LI Xiao   

  1. School of Telecommunication and Information Engineering, Xian University of Posts and Telecommunications, Xian 710121, Shaanxi, China
  • Published:2019-11-06

PDF (PC)

416

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+P2” 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

CLC Number: 

  • TP309
[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 Fp 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.
[1] . Ternary Montgomery algorithm on Hessian curve over GF(3m) [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(1): 96-102.
[2] SU Bin-ting, XU Li, FANG He, WANG Feng. Fast authentication mechanism based on Diffie-Hellman for wireless mesh networks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(9): 101-105.
[3] LI Sheng-dong, LÜ Xue-qiang, SUN Jun, SHI Shui-cai. Improvement of Lucene full-text indexing efficiency [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(07): 76-79.
[4] YU Li. ε-strongly subdifferential of set-valued mapping and application [J]. J4, 2013, 48(3): 99-105.
[5] LI Wei, XU Wen-feng, LI Hong-yu. Study on fuzzy DEA model based on independent subsystems [J]. J4, 2012, 47(9): 78-83.
[6] GUO Xiao-dong1, DU Peng1, ZHANG Xue-fen2. A energy-efficient distributed detection and power allocation algorithm in wireless sensor networks [J]. J4, 2012, 47(9): 60-64.
[7] CUI Yu-quan1, MA Li-jie2, ZHAO Jing3, BAI Jin-yan4. Application of DEA method on identifying a portfolio [J]. J4, 2011, 46(2): 82-88.
[8] ZHOU Xiao-shuang1,2. Relative efficiencies of Bayes estimator and generalized least square estimator under misspecified prior assumption [J]. J4, 2010, 45(9): 70-73.
[9] LI Gui-qing, GAO Zhong-he, WANG Nan-nan. A directed diffusion protocol based on cluster head-set for wireless sensor networks [J]. J4, 2010, 45(11): 37-42.
[10] SI Xiao-hui,YUE Qin-yan*,GAO Bao-yu,WANG Xiao-na,WEI Jin-cheng,LULei . Synthesis of P(DMDAAC-AM) as cationic polymeric flocculants by dispersion polymerization [J]. J4, 2008, 43(1): 28-32 .
[11] MA Li-jie,DENG Wei,ZHAO Yi-jun . Ranking DMUs under interval DEA model [J]. J4, 2006, 41(6): 61-64 .
[12] LI Sen,MA Jun,ZHAO Yan,LEI Jing-sheng . The study on automitic classification of digital documents of scientific papers [J]. J4, 2006, 41(3): 81-84 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZHENG Jing-zhu, YANG Hai-ning, SU Ye, QIN Jing. A blindly public verifiable outsourcing scheme for matrix multiplication[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(11): 1 -11 .
[2] WU Zheng-xiang, LI Bao-ku. Equilibrium strategies of dual-channel supply chain considering the retailers social comparison behavior[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(11): 20 -34 .
[3] LU Zheng-yu, ZHOU Wei, YU Huan-huan, ZHAO Na. Dynamic analysis of game model considering advertising spillover effect[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(11): 63 -70 .
[4] XIONG Xing-guo, LU Ling-xia. MV-algebra valued metric-based fuzzy rough sets[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(11): 81 -89 .
[5] ZHANG Ke-yong, LI Chun-xia, YAO Jian-ming, LI Jiang-xin. Decision-making and coordination of green supply chain with risk aversion under government subsidies[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(11): 35 -51 .
[6] CAO Hui-rong , ZHOU Wei, CHU Tong, ZHOU Jie. Dynamic analysis of Bertrand game model about taxation of government and subsidy[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(11): 52 -62 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd