基于预计算和周期性的ECC标量乘法算法

在研究二进制、带符号的二进制(NAF,Non-Adjacent Form)等常见标量乘法算法的基础上,结合椭圆曲线基点的周期特性和预计算倍点序列方式,提出了一种新的标量乘法算法,并给出了新算法的详细步骤.点的周期性和系数决定了直接进行标量乘法运算还是转化为求其逆元,预计算倍点序列方式避免了椭圆曲线密码体制(ECC,Elliptic Curve Cryptosystem)加解密过程中大量的重复运算.为验证算法的正确性,采用密钥长度为192 bit椭圆曲线,给出了一个具体实例.实例结果和算法分析表明:与二进制和NAF算法相比,新算法虽占用了一些存储空间,但省去了倍点运算的时间开销,同时减少了点加的运算次数,极大地提高了标量乘法运算的效率.该算法的提出对完善ECC理论和加快ECC在实际中的应用具有重要意义.

Scalar multiplication algorithm of ECC based on precomputation and periodicity

Based on the binary method, non-adjacent form (NAF) method, etc., a new scalar multiplication algorithm was proposed, which uses the periodicity of based point and the precomputation mean. Meanwhile, the steps of new algorithm were given. The periodicity of based point and the coefficient of scalar multiplication determine performing the operation of scalar multiplication directly or computing its inverse element. The precomputation mean can void a quantity of repeat computation during the encryption and decryption processes of elliptic curve cryptosystem (ECC). To verify the correctness of new algorithm, a concrete experiment was offered with an elliptic curve, whose key length is 192 bit. The experimental results and algorithm analyses show that comparing with binary and NAF methods, although the new algorithm requires a little extra space to store precomputed points, it does not need the operation of point doublings and reduces the operation times of point addition. Therefore, the new algorithm can improve the efficiency of scalar multiplication sharply. The research achievement is significant for completing the theory of ECC and accelerating its application in practice.