椭圆曲线密码中一种多标量乘算法

A Multiple Scalar Multiplications Algorithm in the Elliptic Curve Cryptosystem

标量乘和多标量乘是实现椭圆曲线密码体制的核心运算,其运算速度从整体上决定了椭圆曲线密码体制的实现效率.提出了一种多标量乘算法,该算法的基本思想是,将标量用带符号的整数阶乘展开式表示,并结合固定基窗口标量乘算法,使得实现多标量乘算法只需做点加运算即可.这不仅突破了传统求多标量乘算法的模式,而且提高了多标量乘的计算速度.同时,还对算法正确性和复杂度进行了分析.由实验结果可知,在m=2的情况下,该算法在计算效率上比已有的多标量乘算法提高了约47.8%~56.5%.

The main operations of elliptic curve cryptosystems（ECCs） are scalar multiplications and multi-scalar multiplications,which heavily determined the overall implementation of the efficiency of ECC.This algorithm extends the fixed-base window method by using the signed integer factorial expansions of scalar.The main characteristic of this method is that only a point addition computation is required,and it greatly improves the computational performance of a multi-scalar.Furthermore,the correctness proof and complexity analysis of the new algorithm are presented.At last,experimental results show that the computational efficiency increases about 47.8% to 56.5% when compared with other existing methods in the case m=2.