一个新的基于radix-4多标量乘算法

很多基于椭圆曲线的密码协议如ECDSA签名验证,都需要计算多标量乘法kP IQ。目前常见的多标量乘算法有:Shamir多标量乘算法,interleaving多标量乘算法等,它们的效率主要取决于标量的(联合)海明权值。但它们都是基于radix-2编码表示的,无论采用何种编码,倍点运算的次数都不变,减少的只是点加(或点减)运算的次数。提出一个基于radix-4表示的新的编码方法,并给出一个基于radix-4表示的多标量乘算法,通过用四倍点运算代替倍点运算,且编码是从左到右(即从最高位向最低位)进行,编码和主计算可以合并,提高实现效率并节省内存空间。

A New Radix-4 Representation Based Multiple Scalar Multiplication Algorithm

Many elliptic curve based cryptographic protocols,such as ECDSA signature verification require computation of multiple scalar multiplications such as kP IQ.Common methods to compute it are the Shamir method and the interleaving method whereas their speed mainly depends on the (joint) Hamming weight of the scalars.The common drawback of these algorithms is that they are based on the radix-2 representations.So 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 is proposed.A new radix-4 representation based scalar multiplication algorithm is given. This method adopts point quadruple instead of point doubling,and examines the integer from left to right (from the most significant digit to the least significant digit).This results in the merging of recoding and evaluation stages.So the proposed algorithm can improve the performance and reduce the memory consumption of scalar multiplication operation.