基于多基表示的滑动窗口椭圆曲线多标量乘算法

标量乘运算从整体上决定了椭圆曲线密码体制的快速实现效率，在一些椭圆曲线公钥密码体制中需要计算多标量乘。多基数链的标量表示长度更短、非零比特数目更少，较好地适用于椭圆曲线标量乘的快速计算。为了提高椭圆曲线密码的效率，在已有的二进制域和素域的标量乘算法的基础上，结合滑动窗口技术、多基算法，提出新的更高效的多标量乘算法。实验结果表明，新算法与传统Shamir算法和交错NAF算法相比，其所需的运算量更少，能有效地提高椭圆曲线多标量乘算法的效率，使多标量乘的运算更高效。相比于其他算法，新算法的计算效率比已有的多标量乘算法提高了约7.9%~20.6%。

Multi-scalar Multiplication Algorithm for Elliptic Curve Based on MBNS and Sliding Window

Scalar multiplication heavily determines the overall implementation efficiency of Elliptic Curve Cryptography(ECC), some elliptic curve cryptosystems of public keys require multi-scalar multiplication. Multi-base number system is very suitable for efficient computation of scalar multiplications of elliptic curves because of shorter representation length and less Hamming weight. In order to improve the efficiency of ECC, this paper proposes an efficient multi-scalar multiplication based on the existing scalar multiplication algorithm in binary fields and prime fields. This new algorithm is a combination of sliding window method and multi-base scalar multiplication algorithm. The experimental results show that the new algorithm costs less compared with Shamir’s trick and interleaving with NAF’s method. The new approach can effectively improve the efficiency of scalar multiplication algorithm, so that the scalar multiplication is more efficient. Compared to other algorithms, the new approach is improved about 7.9%~20.6%.