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

doi:10.3778/j.issn.1002-8331.2010.06.032

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (6): 112-115.DOI: 10.3778/j.issn.1002-8331.2010.06.032

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

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

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

收稿日期:2008-09-25 修回日期:2009-04-01 出版日期:2010-02-21 发布日期:2010-02-21
通讯作者: 赵耿

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

摘要/Abstract

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

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

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

中图分类号:

TP309.7

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

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]	陈虹，刘雨朦，肖成龙，郭鹏飞，肖振久. 基于BBS产生器和椭圆曲线的改进RC4算法[J]. 计算机工程与应用, 2020, 56(8): 87-95.
[2]	邓小鸿，朱年红，黄磊，王智强，王俊彬. 基于区块链的身份托管模型研究[J]. 计算机工程与应用, 2020, 56(4): 24-30.
[3]	李艳俊，汪书北，杨晓桐，曹贻森. 基于移动端的轻量级NFC安全认证方案[J]. 计算机工程与应用, 2020, 56(16): 84-89.
[4]	肖帅，王绪安，潘峰. 无模逆运算的椭圆曲线数字签名算法[J]. 计算机工程与应用, 2020, 56(11): 118-123.
[5]	张平，栗亚敏. 前向安全的椭圆曲线数字签名方案[J]. 计算机工程与应用, 2020, 56(1): 115-120.
[6]	刘双根，赵辉. 基于Pell型序列的快速安全标量乘算法[J]. 计算机工程与应用, 2019, 55(4): 125-129.
[7]	许勇1，刘芬2. 异构传感网中避免中间人攻击的方案研究[J]. 计算机工程与应用, 2018, 54(22): 99-106.
[8]	张伟哲，高德智，李彦. 一个基于ECC的隐匿身份环签名方案[J]. 计算机工程与应用, 2017, 53(23): 88-90.
[9]	刘双根1，姚华童1，李发根2. Edwards曲线上抗SPA快速标量乘算法[J]. 计算机工程与应用, 2017, 53(1): 103-106.
[10]	李明. 新的适用于WSN网络的双方认证密钥协商协议[J]. 计算机工程与应用, 2016, 52(3): 100-102.
[11]	刘双根1，李欢1，李发根2. 一种抵抗Montgomery错误攻击的检错算法[J]. 计算机工程与应用, 2016, 52(24): 19-22.
[12]	赖忠喜，张安洁，张占军. 椭圆曲线中一种计算7P和7kP的改进算法[J]. 计算机工程与应用, 2016, 52(1): 29-32.
[13]	谢天艺1，黄凯1，修思文2，唐从学3，严晓浪1. 素数域椭圆曲线密码加速器的VLSI实现[J]. 计算机工程与应用, 2016, 52(1): 89-94.
[14]	廖俊国，谭永洲. WMN中基于轻量级CA的双向认证和密钥协商协议[J]. 计算机工程与应用, 2016, 52(1): 95-99.
[15]	赖忠喜，林君焕，张占军. 素数域[GF(P)]上椭圆曲线快速标量乘算法的研究[J]. 计算机工程与应用, 2015, 51(4): 100-104.

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

Subsection simultaneous fast scalar multiplication algorithm based on Montgomery algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics