JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2019, Vol. 54 ›› Issue (1): 96-102.doi: 10.6040/j.issn.1671-9352.2.2018.017

Previous Articles    

Ternary Montgomery algorithm on Hessian curve over GF(3m)

  

  1. School of Communication and Information Engineering, Xian University of Posts and Telecommunications, Xian 710121, Shaanxi, China
  • Published:2019-01-23

PDF (PC)

592

Abstract: To raise the efficiency of scalar multiplication on Hessian elliptic curves, a scalar multiplication algorithm on Hessian curve over GF(3m)is proposed by expressing the scalar k in ternary form and combining with the original Montgomery algorithm, and the formulas for fast point addition, point doubling and point tripling are used on the bottom layer. The analysis results show that compared with the original Montgomery ladder algorithm in different coordinate systems, the new algorithm is improved by 20.5% on average. Compared with the scalar multiplication algorithm based on Co-Z operation, the improvement is 34.8%. Compared with signed width-4 sliding windows on the same curve, the improved efficiencies in JacIntersect coordinates and standard projective coordinates are 2.03% and 13.8%, respectively. In different projective coordinates, the new algorithm on the Hessian curve is 33.3% ~ 48% faster than on the Weierstrass curve.

Key words: Hessian elliptic curve, Montgomery algorithm, scalar multiplication, characteristic three

CLC Number: 

  • TP309
[1] KOBLITZ N. Elliptic curve cryptosystems [J]. Mathematics of Computation, 1987, 48(177): 203-209.
[2] MILLER V S. Use of elliptic curves in cryptography[C] //Conference on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1985: 417-426.
[3] LIU Hengzhuang, DONG Qianhui, LI Yibing. Efficient ECC scalar multiplication algorithm based on symmetric ternary in wireless sensor networks[C] //Progress in Electromagnetics Research Symposium-Fall. Singapore: Springer, 2017: 879-885.
[4] MONTGOMERY P L. Speeding the pollard and elliptic curve methods of factorization[J]. Mathematics of Computation, 1987,48(177): 243-264.
[5] LOPEZ J, DAHAB R. Fast multiplication on elliptic curves over GF(2m)without precomputation[C] //International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 1999: 316-327.
[6] JÓYE M, QUISQUATER J J. Hessian elliptic curves and side-channel attacks[C] //Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2001: 402-410.
[7] SMART N P. The hessian form of an elliptic curve[C] //International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2001: 118-125.
[8] SMART N P, WESTWOOD E J. Point multiplication on ordinary elliptic curves over fields of characteristic three[J]. Applicable Algebra in Engineering Communication & Computing, 2003, 13(6): 485-497.
[9] HISIL H, CARTER G, DAWSON E. New formulae for efficient elliptic curve arithmetic[C] //Cryptology, International Conference on Progress in Cryptology. Berlin: Springer, 2007: 138-151.
[10] KIM K H, KIM S I, CHOE J S. New fast algorithms for arithmetic on elliptic curves over finite fields of characteristic three[J/OL]. Cryptology ePrint Archive, Technical Report 2007/179.(2007-05-12). https://eprint.iacr.org/2007/179.
[11] ZHANG Baohua, YIN Xinchun. A new generic algorithm for scalar multiplication[C] //International Workshop on Education Technology and Computer Science. New York: IEEE, 2009: 650-654.
[12] LI Leibo, ZHAN Tao. Co-Z addition operation of hessian curve[C] //Seventh International Conference on Computational Intelligence and Security. New York: IEEE, 2011: 915-919.
[13] FARASHAHI R R, WU Hongfeng, ZHAO Changan. Efficient arithmetic on elliptic curves over fields of characteristic three[C] //International Conference on Selected Areas in Cryptography. Berlin: Springer, 2013: 135-148.
[14] LI Weixuan, YU Wei, WANG Kunpeng. Improved tripling on elliptic curves[C] //Revised Selected Papers of the International Conference on Information Security and Cryptology. New York: Springer, 2015: 193-205.
[15] CHO S M, SEO S C, KIM T H, et al. Extended elliptic curve Montgomery ladder algorithm over binary fields with resistance to simple power analysis[J]. Information Sciences, 2013, 245(10): 304-312.
[16] SAQIB N A, FRANCISCO R H, ARTURO D P. A parallel architecture for computing scalar multiplication on hessian elliptic curves[C] //International Conference on Information Technology: Coding and Computing. New York:IEEE, 2004: 493.
[17] 赖忠喜, 张占军. Hessian椭圆曲线上基于Co-Z运算的标量乘算法[J]. 科技通报, 2016, 32(2): 28-33. LAI Zhongxi, ZHANG Zhanjun. Scalar multiplication on Hessian curves based on Co-Z operations [J]. Bulletin of Science and Technology, 2016, 32(2): 28-33.
[18] COHEN H, MIYAJI A, ONO T. Efficient elliptic curve exponentiation using mixed coordinates[C] //Proceedings of the Advances in Cryptology-ASIACRYPT’98. Berlin: Springer, 1998: 51-65.
[19] 刘双根, 姚华童, 李发根. Edwards曲线上抗SPA快速标量乘算法[J]. 计算机工程与应用, 2017, 53(1): 103-106. LIU Shuanggen, YAO Huatong, LI Fagen. SPA resistant scalar multiplication on Edwards curve[J].Computer Engineering and Applications, 2017, 53(1): 103-106.
[20] OLIVEIRA T, LOPEZ J, FRANCISCO R H. The Montgomery ladder on binary elliptic curves[J]. Journal of Cryptographic Engineering, 2017(5): 1-18.
[21] 李杨, 王劲林, 曾学文, 等. 抵抗SPA攻击的分段Montgomery标量乘算法[J]. 计算机工程与科学, 2017, 39(1): 92-102. LI Yang, WANG Jinlin, ZENG Xuewen, et al. A segmented Montgomery scalar multiplication algorithm with resistance to simple power ananlysis SPA attacks[J]. Computer Engineering and Science, 2017, 39(1): 92-102.
[22] VELEGALAT R, YALLA P. Differential power analysis attacks[J].Application Research of Computers, 2014, 31: 1-6.
[23] 于伟, 李宝, 王鲲鹏, 等. 特征3有限域上椭圆曲线的Co-Z Montgomery算法[J]. 计算机学报, 2017, 40(5): 1121-1133. YU Wei, LI Bao, WANG Kungpeng, et al. Co-Z Montgomery algorithm on elliptic curves over finite fields of characteristic three[J]. Chinese Journal of Computers, 2017, 40(5): 1121-1133.
[24] 端木庆峰, 张雄伟, 王衍波,等. 3特征域椭圆曲线群点的快速计算算法[J]. 解放军理工大学学报(自然科学版), 2011, 12(1): 1-6. DUANMU Qingfeng, ZHANG Xiongwei, WANG Yanbo, et al. Fast arithmetic operations of elliptic curve over GF(3m)[J]. Journal of PLA University of Science and Technology(Natural Science Edition), 2011, 12(1): 1-6.
[1] Zhao-xia WU,Jia-qi WANG. Wireless single spectrum secure auction algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 51-55.
[2] YAN Yan, HAO Xiao-hong. Differential privacy partitioning algorithm based on adaptive density grids [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 12-22.
[3] JIAO Hong-ru, QIN Jing. Quantum secret sharing scheme realizing all hyperstar quantum access structure [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 62-68.
[4] XU Li-dong, WANG Ming-qiang. A meet-in-the-middle attack on 10-round AES-128 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 39-45.
[5] ZHANG Jian-biao, LI Zhi-gang, LIU Guo-jie, WANG Chao, WANG Wei. Process active dynamic measurement method for Windows environment [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 46-50.
[6] CUI Zhao-yang, SUN Jia-qi, XU Song-yan, JIANG Xin. A secure clustering algorithm of Ad Hoc network for colony UAVs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 51-59.
[7] LIU Zheng, NIU Fang-lin, QIAN Da-xing, CAI Xi-biao, GUO Ying. Design of anti-eavesdropping code based on fountain codes [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 60-64.
[8] LIU Ming-ming, ZHANG Min-qing, LIU Jia, GAO Pei-xian. Steganalysis method based on shallow convolution neural network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(3): 63-70.
[9] RUAN Shu-hua, WENG Jun-hao, MAO Hui, CHEN Xue-lian. Metric model for cloud computing security risk assessment [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(3): 71-76.
[10] KANG Hai-yan, HUANG Yu-xuan, CHEN Chu-qiao. Enhancing privacy for geographic information based on video analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 19-29.
[11] MENG Bo, LU Jin-tian, WANG De-jun, HE Xu-dong. Survey of security analysis of security protocol implementations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 1-18.
[12] TAN Ren, YIN Xiao-chuan, JIAO Xian-long, LIAN Zhe, CHEN Yu-xin. Software defined APT attack moving target defense network architecture [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 38-45.
[13] SUN Ze-rui, WANG Ji-jun, LI Guo-xiang, XIA Guo-en. New reversible data hiding algorithm based on interpolation images [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 46-52.
[14] SUN Liang, CHEN Xiao-chun, ZHONG Yang, LIN Zhi-peng, REN Tong. Secure startup mechanism of server based on trusted BMC [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 89-94.
[15] YAO Ke, ZHU Bin-rui, QIN Jing. Verifiable public key searchable encryption protocol based on biometrics [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(11): 11-22.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd