Subsection simultaneous fast scalar multiplication algorithm based on Montgomery algorithm

doi:10.3778/j.issn.1002-8331.2010.06.032

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (6): 112-115.DOI: 10.3778/j.issn.1002-8331.2010.06.032

• 网络、通信、安全 • Previous Articles Next Articles

Subsection simultaneous fast scalar multiplication algorithm based on Montgomery algorithm

ZHAO Geng^1，2，PENG Cheng-pei^1，2，LI Xiao-dong¹，ZHANG Dong^1，2

1.Beijing Electronic Science and Technology Institute，Beijing 100070，China
2.College of Communication Engineering，Xidian University，Xi’an 710071，China

Received:2008-09-25 Revised:2009-04-01 Online:2010-02-21 Published:2010-02-21
Contact: ZHAO Geng

基于Montgomery的分段并行标量乘快速算法

赵耿^1，2，彭程培^1，2，李晓东¹，张栋^1，2

1.北京电子科技学院，北京 100070
2.西安电子科技大学通信工程学院，西安 710071

通讯作者: 赵耿

Abstract

Abstract: In the elliptic curve binary field，it needs less computation amount for that the Montgomery algorithm only computes the x coordinate in the whole course and gets the y coordinate in the last step.A new computational algorithm based on the Montgomery subsection method is proposed to enhance the efficiency further for computer kP，the computation amount decreases 25% for the new algorithm of two subsection and 37% for the new algorithm of three subsection compared with the original algorithm.The efficiency of the new algorithm is proved to be improved by the program implementation.The new algorithm possesses good performance on elliptic curve scalar multiplication.

Key words: elliptic curve, scalar multiplication, Montgomery algorithm

摘要： 在椭圆曲线二进制域上，Montgomery算法利用在计算kP过程中只需计算x坐标，在最后才恢复y坐标的特性，使该算法的计算量更少。在此基础上提出基于Montgomery的分段并行标量乘算法来更进一步提高算法的效率，经分析，将整数标量分两段并行计算，算法效率可提高约25%，将其分三段时其效率可提高约37%。通过编程实现验证了新算法的效率确实有明显提高，新算法对椭圆曲线标量乘快速实现有实际意义。

关键词: 椭圆曲线, 标量乘, Montgomery方法

CLC Number:

TP309.7

ZHAO Geng^1，2，PENG Cheng-pei^1，2，LI Xiao-dong¹，ZHANG Dong^1，2. Subsection simultaneous fast scalar multiplication algorithm based on Montgomery algorithm[J]. Computer Engineering and Applications, 2010, 46(6): 112-115.

赵耿^1，2，彭程培^1，2，李晓东¹，张栋^1，2. 基于Montgomery的分段并行标量乘快速算法[J]. 计算机工程与应用, 2010, 46(6): 112-115.

[1]	CHEN Hong, LIU Yumeng, XIAO Chenglong, GUO Pengfei, XIAO Zhenjiu. Improved RC4 Algorithm Based on BBS Generator and Elliptic Curve [J]. Computer Engineering and Applications, 2020, 56(8): 87-95.
[2]	DENG Xiaohong, ZHU Nianhong, HUANG Lei, WANG Zhiqiang, WANG Junbin. Research on Identity Trusteeship Model Based on Blockchain [J]. Computer Engineering and Applications, 2020, 56(4): 24-30.
[3]	LI Yanjun, WANG Shubei, YANG Xiaotong, CAO Yisen. Lightweight NFC Security Authentication Scheme Based on Mobile Terminal [J]. Computer Engineering and Applications, 2020, 56(16): 84-89.
[4]	XIAO Shuai, WANG Xu’an, PAN Feng. Elliptic Curve Digital Signature Algorithm Without Modular Inverse Operation [J]. Computer Engineering and Applications, 2020, 56(11): 118-123.
[5]	ZHANG Ping, LI Yamin. Forward Secure Elliptic Curve Digital Signature Scheme [J]. Computer Engineering and Applications, 2020, 56(1): 115-120.
[6]	LIU Shuanggen, ZHAO Hui. Fast and Secure Scalar Multiplication Based on Pell Sequence [J]. Computer Engineering and Applications, 2019, 55(4): 125-129.
[7]	XU Yong1, LIU Fen2. Research of scheme for preventing man-in-middle attack in heterogeneous sensor networks [J]. Computer Engineering and Applications, 2018, 54(22): 99-106.
[8]	ZHANG Weizhe, GAO Dezhi, LI Yan. Hidden identity ring signature scheme using ECC [J]. Computer Engineering and Applications, 2017, 53(23): 88-90.
[9]	LIU Shuanggen1, YAO Huatong1, LI Fagen2. SPA resistant scalar multiplication on Edwards curve [J]. Computer Engineering and Applications, 2017, 53(1): 103-106.
[10]	LI Ming. Novel two-party authenticated key agreement protocol in Wireless Sensor Network [J]. Computer Engineering and Applications, 2016, 52(3): 100-102.
[11]	LIU Shuanggen1, LI Huan1, LI Fagen2. Error detection algorithm of resistance to fault attack on Montgomery algorithm [J]. Computer Engineering and Applications, 2016, 52(24): 19-22.
[12]	LAI Zhongxi, ZHANG Anjie, ZHANG Zhanjun. Improved algorithms for computing 7P and 7kP on elliptic curves [J]. Computer Engineering and Applications, 2016, 52(1): 29-32.
[13]	XIE Tianyi1, HUANG Kai1, XIU Siwen2, TANG Congxue3, YAN Xiaolang1. VLSI implementation of elliptic curve cryptographic accelerator over [GF(p)] [J]. Computer Engineering and Applications, 2016, 52(1): 89-94.
[14]	LIAO Junguo, TAN Yongzhou. Bilateral authentication and key agreement protocol based on lightweight CA for wireless mesh networks [J]. Computer Engineering and Applications, 2016, 52(1): 95-99.
[15]	LAI Zhongxi, LIN Junhuan, ZHANG Zhanjun. Study on fast method of scalar multiplication on elliptic curves over Prime field [GF(P)] [J]. Computer Engineering and Applications, 2015, 51(4): 100-104.

Subsection simultaneous fast scalar multiplication algorithm based on Montgomery algorithm

基于Montgomery的分段并行标量乘快速算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics