基于FPGA的Edwards曲线标量乘法改进与实现

Improvement and Implementation of Scalar Multiplication on Edwards Curve Based on FPGA

点加是Edwards曲线标量乘法的基本运算,当点加算法确定后,通过减少点加运算次数来提高标量乘法运算效率是一种有效的方法。首先,根据标量乘法在椭圆曲线公钥密码中的使用特点,将标量乘法分成固定点标量乘法、随机点标量乘法和多点标量乘法;其次,采用预计算和窗口法来减少标量乘法中的点加运算次数;最后,在复旦微的JFM7K325T的现场可编程门阵列(FieldProgrammableGateArray,FPGA)中进行了实现和测试。结果表明,与原有实现方法相比,改进算法计算256比特固定点标量乘法速度提升了450%,计算随机点标量乘法速度提升了39%,计算多点标量乘法速度提升了66%。

Point addition is the basic operation of scalar multiplication on Edwards curves.Once the point addition algorithm is determined,reducing the number of point addition operations to improve the efficiency of scalar multiplication is an effective method.Firstly,based on the usage characteristics of scalar multiplication in elliptic curve public key cryptography,scalar multiplication is divided into fixed point scalar multiplication,random point scalar multiplication,and multi-point scalar multiplication;Secondly,precomputing and windowing methods are used to reduce the number of point addition operations in scalar multiplication;Finally,the implementation and testing were carried out in the Field Programmable Gate Array(FPGA)of JFM7K325T at Fudan Microelectronics.The results show that compared with the original implementation method,the improved algorithm has increased the speed of 256 bit fixed point scalar multiplication by 450%,the speed of random point scalar multiplication by 39%,and the speed of multi-point scalar multiplication by 66%.