基于伪随机数生成器的标量乘改进算法

标量乘算法是椭圆曲线密码体制中最基本、最耗时的算法,包含点加和倍点两种运算.传统的改进方法通过改造标量表示形式减少非零元位数来降低标量乘中的点加运算次数.为了进一步提高标量乘算法效率,根据标量的生成方式,提出了一种结合伪随机数生成器改进算法.利用斐波那契数列生成器的的循环迭代相加可以将标量乘运算由反复的点加和倍点运算转化为单一的点加运算.实验结果表明,改进算法相比传统的窗口NAF算法能够降低60％以上的运算量.

Improved Algorithm of Scalar Multiplication Based on Pseudo-Random Number Generator

Scalar multiplication is the dominant and time consuming algorithm in elliptic curve cryptography, including point addition and point doubling. Traditional improved methods reduced the calculation of point addition by transforming the representation of scalar to reduce the number of non-zero bits. To further improve the efficiency of the scalar multiplication, this paper proposes an improved algorithm combining pseudo-random number generator according to the generation of the scalar. With cyclical iterative addition of lagged Fibonacci generator, scalar multiplication can be transformed into simplex operation of point addition from repetitive point addition and point doubling. Experimental results show that the improved algorithm compared to the traditional window NAF algorithm can reduce more than 60% of the amount of computation.