一种定点快速标量乘算法的优化

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (4): 80-82.

一种定点快速标量乘算法的优化

殷新春,侯红祥

扬州大学计算机科学与工程系，江苏扬州 225009

收稿日期:2007-06-25 修回日期:2007-08-31 出版日期:2008-02-01 发布日期:2008-02-01
通讯作者: 殷新春

Optimization of fast fixed point fast scalar multiplication algorithm

YIN Xin-chun,HOU Hong-xiang

Department of Computer Science and Engineering，Yangzhou University，Yangzhou，Jiangsu 225009，China

Received:2007-06-25 Revised:2007-08-31 Online:2008-02-01 Published:2008-02-01
Contact: YIN Xin-chun

摘要/Abstract

摘要： 标量乘法是实现椭圆曲线密码体制的瓶颈问题，利用NAF编码、预计算表法和Yen-Laih法分别在三个阶段对Lim-Lee算法进行优化，新的定点标量乘算法在赋值阶段动态扫描矩阵宽度为w的非全零列窗口，结合2^kP底层域快速算法和扩充过的预计算表来提高计算效率。当位长是160时，新算法效率比Lim-Lee算法提高22.7%，192时提高23%，224时提高23.3%。

关键词: ECC, 定点标量乘法, NAF编码, 预计算表法, Yen-Laih法

Abstract: Scalar multiplication is the bottleneck of ECC.This paper optimizes the Lim-Lee algorithm with NAF method，pre-compute table and Yen-Laih method in three stages separately.The new fixed-point scalar multiplication algorithm dynamicly scans the matrix to get nonzero windows with length limited in w in the evaluation stage，and integrates with 2^kP field fast algorithm and extended pre-compute table to improve compute efficiency.When digit length is 160，the efficiency of new algorithm improves about 22.7% than Lim-Lee algorithm，about 23% when 192 and 23.3% when 224.

Key words: EEC, fixed-point scalar multiplication, NAF method, pre-compute table, Yen-Laih method

殷新春,侯红祥. 一种定点快速标量乘算法的优化[J]. 计算机工程与应用, 2008, 44(4): 80-82.

YIN Xin-chun,HOU Hong-xiang. Optimization of fast fixed point fast scalar multiplication algorithm[J]. Computer Engineering and Applications, 2008, 44(4): 80-82.

[1]	许勇1，刘芬2. 异构传感网中避免中间人攻击的方案研究[J]. 计算机工程与应用, 2018, 54(22): 99-106.
[2]	冉沛，杨吉云，谭金勇. 一种新的Word电子文档完整性保护方案[J]. 计算机工程与应用, 2013, 49(13): 76-79.
[3]	王金荣^1,2. 一种基于优化正规基的域元素乘法改进算法[J]. 计算机工程与应用, 2008, 44(23): 62-64.
[4]	张春生姚绍文张险峰. 基于状态树的(t,n)门限密钥托管方案[J]. 计算机工程与应用, 2007, 43(4期): 146-149.
[5]	刘淳张凤元张其善. 基于智能卡的RSA与ECC算法的比较与实现[J]. 计算机工程与应用, 2007, 43(4期): 96-98.
[6]	张利华张有光吕善伟 . ＵＡＰ协议的安全性分析与改进[J]. 计算机工程与应用, 2006, 42(18期): 1-4.