面向多椭圆曲线的高速标量乘法器设计与实现

Design and implementation of high-speed scalar multiplier for multi-elliptic curve

针对现有标量乘法器不能适用于多椭圆曲线且运算开销较大的问题,设计了一种能应用于两类素数域椭圆曲线的高速标量乘法器。首先,在标量乘算法上,对secp256r1曲线的基点采用Comb算法,对普通点采用Shamir算法,对Curve25519曲线使用蒙哥马利阶梯算法;然后,优化了点加和倍点运算的操作步骤,并对点加中Z=1的情况进行简化设计,有效减少计算周期数;最后,采用快速模约简实现模乘,设计了Curve25519的快速模约简算法。整个设计充分考虑复用,在55 nm CMOS工艺下需1022×10^3个等效门,在secp256r1和Curve25519上计算普通点标量乘,运算速度分别为15.3万次/秒和15.8万次/秒,其中secp256r1上的运算速度是现有设计的1.9倍。

Aiming at the problem that the existing scalar multiplier cannot be applied to multi-elliptic curve and the cost is expensive,a high-speed scalar multiplier was designed,applicable to two types of elliptic curves over prime fields.Firstly,in terms of the scalar multiplication,secp256r1 base points were processed with the comb algorithm,and the Shamir algorithm for ordinary points,and the Montgomery ladder algorithm for Curve25519.Secondly,the operation of point addition and point doubling was optimized,and the condition of Z=1 in point addition was simplified,thereby effectively reducing the number of calculation cycles.Lastly,a fast modular reduction algorithm of Curve25519 was designed for modular multiplication.Multiplexing was an important factor in the entire designing process.A 1022K equivalent gate was selected for the 55 nm CMOS process.This allowed ordinary point scalar multiplications performed on secp256r1 and Curve25519 respectively,calculating at the speeds of 153000 times per second and 158000 times per second,with the speed for secp256r11.9 times that of the existing designed one.