Edwards曲线快速标量乘算法研究

Research on fast scalar multiplication algorithm for Edwards curve

标量乘法是椭圆曲线密码算法中最核心的运算,其运算速度影响着整个密码体制的实现效率。首先,详细地介绍了Edwards曲线的基本概念。其次,为了提高标量乘法的运算速度,针对椭圆曲线标量乘算法进行了研究,引入了一种可以用来计算连续倍点2^mP的算法CDA。为了提高CDA的计算效率,提出了将标量k表示为4-NNAF形式以减少k的长度,再结合CDA计算标量乘法可以有效地减少运算量。最后根据算法的运算量分析和具体例子得出,减少标量k长度后的计算效率提高了13%以上。为了进一步加快运算速度,又提出了对CDA中乘法运算和模逆运算采用并行结构来减少标量乘法的运算次数。计算结果表明,并行后的计算效率提高了36%以上。

Scalar multiplication is the most core operation in the elliptic curve cryptography algorithm,and its operation speed affects the efficiency of the entire cryptosystem. Firstly,this paper introduced the basic concept of Edwards curve in detail.Secondly,in order to improve the operation of scalar multiplication,this paper studied the elliptic curve scalar multiplication algorithm,and introduced an algorithm CDA( continues doubling algorithm) which could be used to calculate 2^mP of continuous doubling points. In order to improve the computational efficiency of CDA,it proposed expressing the scalar k as the 4-NNAF form to reduce the length of k and combined with CDA to calculate scalar multiplication could effectively reduce the amount of computation. Finally,according to the analysis of the computational complexity of the algorithm and the concrete examples,the computational efficiency is improved by more than 13% after reducing the length of scalar k. In order to further speed up the operation,this paper proposed to use a parallel structure for multiplication and modular inverse operations in CDA to reduce the number of operations of scalar multiplication. The calculation result shows that the parallel computing efficiency is improved by more than 36%.