论文部分内容阅读
很多基于椭圆曲线的密码协议如ECDSA签名验证,都需要计算多标量乘法kP+IQ。目前常见的多标量乘算法有:Shamir多标量乘算法,interleaving多标量乘算法等,它们的效率主要取决于标量的(联合)海明权值。但它们都是基于radix-2编码表示的,无论采用何种编码,倍点运算的次数都不变,减少的只是点加(或点减)运算的次数。提出一个基于radix-4表示的新的编码方法,并给出一个基于radix-4表示的多标量乘算法,通过用四倍点运算代替倍点运算,且编码是从左到右(即从最高位向最低位)进行,编码和主计算可以合并,提高实现效率并节省内存空间。
Many elliptic curve-based cryptographic protocols, such as ECDSA signature verification, require the computation of multi-scalar multiplication kP + IQ. The common multi-scalar multiplication algorithms are: Shamir multi-scalar multiplication, interleaving multi-scalar multiplication and so on. Their efficiency mainly depends on the (joint) Hamming weight of scalar. However, they are based on the radix-2 encoding. No matter what encoding is adopted, the number of times of the multiplication is the same, reducing the number of times of adding (or subtracting) operations. A new encoding method based on radix-4 representation is proposed. A multi-scalar multiplication algorithm based on radix-4 representation is given. The quadruple point operation replaces the double point operation, and the encoding is from left to right (from the highest Bit to the lowest bit), encoding and main calculations can be merged to improve the efficiency and save memory space.