《计算机应用研究》|Application Research of Computers

Edwards曲线快速标量乘算法研究

Research on fast scalar multiplication algorithm for Edwards curve

免费全文下载 (已被下载 次)  
获取PDF全文
作者 明娇娇,高献伟,董秀则,李江峰
机构 1.西安电子科技大学 通信工程学院,西安 710071;2.北京电子科技学院 电子与通信工程系,北京 100070
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2020)09-043-2776-05
DOI 10.19734/j.issn.1001-3695.2019.03.0151
摘要 标量乘法是椭圆曲线密码算法中最核心的运算,其运算速度影响着整个密码体制的实现效率。首先,详细地介绍了Edwards曲线的基本概念。其次,为了提高标量乘法的运算速度,针对椭圆曲线标量乘算法进行了研究,引入了一种可以用来计算连续倍点2<sup><i></sup>mP</i>的算法CDA。为了提高CDA的计算效率,提出了将标量<i>k</i>表示为4-NNAF形式以减少<i>k</i>的长度,再结合CDA计算标量乘法可以有效地减少运算量。最后根据算法的运算量分析和具体例子得出,减少标量<i>k</i>长度后的计算效率提高了13%以上。为了进一步加快运算速度,又提出了对CDA中乘法运算和模逆运算采用并行结构来减少标量乘法的运算次数。计算结果表明,并行后的计算效率提高了36%以上。
关键词 标量乘法; 椭圆曲线密码; Edwards曲线; 连续倍点算法
基金项目 国家自然科学基金资助项目(61701008)
中央高校基本科研业务费(328201801)
本文URL http://www.arocmag.com/article/01-2020-09-043.html
英文标题 Research on fast scalar multiplication algorithm for Edwards curve
作者英文名 Ming Jiaojiao, Gao Xianwei, Dong Xiuze, Li Jiangfeng
机构英文名 1.School of Communication Engineering,Xidian University,Xi'an 710071,China;2.Dept. of Electronic,Beijing Electronics Science & Technology Institute,Beijing 100070,China
英文摘要 Scalar multiplication is the most core operation in the elliptic curve cryptography algorithm, and its operation speed affects the efficiency of the entire cryptosystem. Firstly, this paper introduced the basic concept of Edwards curve in detail. Secondly, in order to improve the operation of scalar multiplication, this paper studied the elliptic curve scalar multiplication algorithm, and introduced an algorithm CDA(continues doubling algorithm) which could be used to calculate 2<sup><i></sup>mP </i>of continuous doubling points. In order to improve the computational efficiency of CDA, it proposed expressing the scalar <i>k</i> as the 4-NNAF form to reduce the length of <i>k</i> and combined with CDA to calculate scalar multiplication could effectively reduce the amount of computation. Finally, according to the analysis of the computational complexity of the algorithm and the concrete examples, the computational efficiency is improved by more than 13% after reducing the length of scalar <i>k</i>. In order to further speed up the operation, this paper proposed to use a parallel structure for multiplication and modular inverse operations in CDA to reduce the number of operations of scalar multiplication. The calculation result shows that the parallel computing efficiency is improved by more than 36%.
英文关键词 scalar multiplication; elliptic curve cryptography(ECC); Edwards curve; continues doubling algorithm
参考文献 查看稿件参考文献
 
收稿日期 2019/3/14
修回日期 2019/6/3
页码 2776-2780
中图分类号 TP309.7
文献标志码 A