基于素数域上复合运算的快速标量乘算法

底层有限域上点群运算是影响椭圆曲线密码效率的主要因素, 利用混合坐标下快速复合运算2P+Q代替传统的点加运算作为基本计算单元, 对NAF标量乘算法进行改进, 改进后算法与基于最优坐标下的NAF标量乘算法相比, 效率提高7%。通过预计算对标量k进行分段编码, 提出基于复合运算的分段并行标量乘快速算法, 在基点和标量长固定的情况下, 该算法与原有NAF算法相比计算效率提高了46. 5%, 而且改进后算法仅需存储三个预计算点坐标, 存储空间小。

Efficient scalar multiplication of ECC based oncomposite operations over prime fields

The operations of the point on elliptic curves in the bottom finite field is the major factor which determines the efficiency of the cryptosystem. Using the new composite operations 2P+Q replace the traditional point addition to improve the scalar multiplication of NAF, which can be better 7% than the old one. This paper put forward an efficient simultaneous algorithm based on composite operations through precomputation, it improved new algorithm's efficiency by 46. 5% compared with the original algorithm. The improved algorithm has only three points to save, the space required is small.