一个新的基于radix-4从左到右编码的标量乘算法

椭圆曲线标量乘是椭圆曲线密码系统中最关键、最耗时的运算,因此如何快速高效实现标量乘运算是研究的重点。目前常见的标量乘算法有:double-and-add算法,NAF算法,MOF算法等,但它们都是基于radix-2编码表示的,无论采用何种编码,倍点运算的次数都不变,减少的只是点加(或点减)运算的次数。提出一个基于radix-4表示的新的编码方法,并提出一个基于radix-4表示的标量乘算法,通过用四倍点运算代替倍点运算,且编码是从左到右(即从最高位向最低位)进行,编码和主计算可以合并,提高实现效率并节省内存空间。实验结果表明,该算法较经典的double-and-add算法能够提高效率30%以上。

A New Radix-4 Representation Based Left-to-Right Scalar Multiplication Algorithm

The scalar multiplication dominates the execution time of elliptic curve cryptographic schemes, so various methods have been studied to enhance the performance of this operation. The double -and -add algorithm, the NAF algorithm and the MOF algorithm are the frequently used methods implementing this operation, but the common drawback of these algorithms is that they are based on the radix-2 representations. Therefore, no matter what recording is used, only the number of point addition (or subtraction) can be diminished, but the number of point doubling can not be diminished. In this paper, a new recoding method based on the radix-4 representation was proposed. A new radix -4 representation based scalar multiplication algorithm was given. This method adopted point quadruple instead of point doubling, and examined the integer from left to right (from the most significant digit to the least significant digit). This resulted in the mergingof recoding and evaluation stages. So the proposed algorithm can improve the performance and reduce the memory consumption of scalar multiplication operation. The result of the experiment showed that performance was enhanced over 30% than that of the algorithm using double-and -add method.