GF(3m)上Hessian曲线的三进制Montgomery算法

doi:10.6040/j.issn.1671-9352.2.2018.017

摘要/Abstract

摘要： 为了提高Hessian曲线标量乘算法的效率,通过将标量k表示成三进制形式,并与原始Montgomery算法相结合,提出了GF(3m)上Hessian曲线标量乘算法,且底层上采用快速点加、倍点和3倍点操作公式。分析结果表明,新算法与不同坐标系下的原始Montgomery阶梯算法相比,效率平均提高20.5%;与基于Co-Z运算的标量乘算法相比,效率提高34.8%;与同一曲线上signed width-4 sliding windows算法相比,在JacIntersect坐标和标准射影坐标下提高的效率分别为2.03%和13.8%。在不同射影坐标下,新算法在Hessian曲线上比Weierstrass曲线上快33.3% ~ 48%。

关键词: Hessian椭圆曲线, Montgomery算法, 标量乘, 特征3

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

中图分类号:

TP309

刘双根,王蓉蓉,李圣雨. GF(3m)上Hessian曲线的三进制Montgomery算法[J]. 《山东大学学报(理学版)》, 2019, 54(1): 96-102.

参考文献

[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.

相关文章 15

[1]	巫朝霞,王佳琪. 一种无线单频谱安全拍卖算法[J]. 《山东大学学报(理学版)》, 2018, 53(11): 51-55.
[2]	晏燕,郝晓弘. 差分隐私密度自适应网格划分发布方法[J]. 山东大学学报（理学版）, 2018, 53(9): 12-22.
[3]	焦鸿儒,秦静. 可实现全部超星量子存取结构的量子秘密共享方案[J]. 山东大学学报（理学版）, 2018, 53(9): 62-68.
[4]	许力冬,王明强. 对10轮AES-128的中间相遇攻击[J]. 山东大学学报（理学版）, 2018, 53(7): 39-45.
[5]	张建标,李志刚,刘国杰,王超,王玮. 面向Windows环境进程主动动态度量方法[J]. 山东大学学报（理学版）, 2018, 53(7): 46-50.
[6]	崔朝阳,孙甲琦,徐松艳,蒋鑫. 适用于集群无人机的自组网安全分簇算法[J]. 山东大学学报（理学版）, 2018, 53(7): 51-59.
[7]	刘政,牛芳琳,钱大兴,蔡希彪,郭颖. 基于喷泉码的防窃听编码设计[J]. 山东大学学报（理学版）, 2018, 53(7): 60-64.
[8]	刘明明,张敏情,刘佳,高培贤. 一种基于浅层卷积神经网络的隐写分析方法[J]. 山东大学学报（理学版）, 2018, 53(3): 63-70.
[9]	阮树骅,瓮俊昊,毛麾,陈雪莲. 云安全风险评估度量模型[J]. 山东大学学报（理学版）, 2018, 53(3): 71-76.
[10]	康海燕,黄渝轩,陈楚翘. 基于视频分析的地理信息隐私保护方法[J]. 山东大学学报（理学版）, 2018, 53(1): 19-29.
[11]	孟博,鲁金钿,王德军,何旭东. 安全协议实施安全性分析综述[J]. 山东大学学报（理学版）, 2018, 53(1): 1-18.
[12]	谭韧,殷肖川,焦贤龙,廉哲,陈玉鑫. 一种软件定义APT攻击移动目标防御网络架构[J]. 山东大学学报（理学版）, 2018, 53(1): 38-45.
[13]	孙泽锐,王继军,李国祥,夏国恩. 基于插值图像的可逆信息隐藏算法[J]. 山东大学学报（理学版）, 2018, 53(1): 46-52.
[14]	孙亮,陈小春,钟阳,林志鹏,任彤. 基于可信BMC的服务器安全启动机制[J]. 山东大学学报（理学版）, 2018, 53(1): 89-94.
[15]	姚克,朱斌瑞,秦静. 基于生物信息的可验证公钥可搜索加密协议[J]. 山东大学学报（理学版）, 2017, 52(11): 11-22.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed