基于NAF_w的二进制域乘法算法

Multiplication Algorithm on Binary Field Based on NAF_w

椭圆曲线上的乘法运算速度是提高椭圆曲线加密(ECC)性能的一个关键;分析了宽度w的非相邻表示型(NAF)算法和多项式乘法算法,提出了一个基于NAFw的二进制域乘法算法;算法减少了运算中的异或运算次数和预计算个数,缩短了运算时间且节省了存储空间;经建模仿真,结果表明本算法运算效率较comb多项式乘法平均快14.7%左右,预计算只需要计算2w-1-1个,从存储预计算个数和时间消耗综合考虑w=4也是较优的窗口宽度选择。

The speed of multiplication on elliptic curves is a key to improving performance of Elliptic Curve Cryptography（ECC）. This paper analyzes the non-adjacent form （NAF） algorithm of the width w and the polynomial multiplication algorithm and proposes a multiplication algorithm on binary field based on NAFw. This algorithm reduces the XOR operation in the frequency and the number of precomputation, decreasing the computation time and saving storage space. The modeling and simulation results show that its average efficiency is approximate 14.7% faster than the comb polynomial multiplication and it only needs 2w-1- 1 precomputation, Based on the number of precomputation to storage and time consumption, w = 4 is better choice to the width of the window.