Edwards曲线快速标量乘算法的改进与FPGA实现  

Improvement of Fast Scalar Multiplication Algorithm on Edwards Curve and Implementation in FPGA

作　　者：高献伟[1] 明娇娇 张磊[1] 董秀则[1] 张青川 GAO Xianwei;MING Jiaojiao;ZHANG Lei;DONG Xiuze;ZHANG Qingchuan(Beijing Electronics Science and Technology Institute,Beijing 100070,P.R.China;National Engineering Laboratory for Agri-product Quality Traceability,Beijing Technology and Business University,Beijing 100048,P.R.China)

机构地区：[1]北京电子科技学院,北京市100070 [2]农产品质量安全追溯技术及应用国家工程实验室(北京工商大学),北京市100048

出　　处：《北京电子科技学院学报》2020年第1期1-12,共12页Journal of Beijing Electronic Science And Technology Institute

基　　金：农产品质量安全追溯技术及应用国家工程实验室开放课题(AQT-2018-YB5)。

摘　　要：针对Edwards曲线上标量乘法的运算效率问题,提出一种安全快速的标量乘算法。首先,详细地介绍了Edwards曲线的基本内容,引入了一种安全快速的标量乘算法EDSM(scalar multiplication on Edwards curve)。其次,为了减少标量乘法的运算量,对EDSM算法进行了改进。改进方案将标量k表示成四进制形式,根据k的表示设计出四进制形式的标量乘算法,经过理论分析和计算表明,改进后的EDSM算法的运算效率优于EDSM算法,标量乘法的计算速度提高了10%左右。最后,结合现场可编程门阵列(Field Programmable Gate Array,FPGA)并行计算的特点,在Xilinx Virtex5系列的XC5VLX20T芯片中运行结果表明,完成一次256位标量乘法仅需0.37ms。和高基Montgomery模乘流水化阵列结构相比,标量乘的运算速度提高了50%,而且运算中并没有使用器件内部的专用乘法器,所以具有良好的可移植性。To solve the problem of low operation efficiency when implementing scalar multiplication on Edwards curve,a scalar multiplication algorithm with high safety and speed is proposed.The basic content of the Edwards curve is first introduced in details,and a type of safe and fast scalar multiplication algorithm on Edwards curve named EDSM is introduced.To reduce the computation of the scalar multiplication,the EDSM algorithm is then modified,where the scalar k is expressed in quaternary form and a quaternary scalar multiplication algorithm is designed according to the expression of the k.Theoretical analysis and derivations show that the modified EDSM algorithm has a higher efficiency than the EDSM algorithm and the computation speed of scalar multiplication is increased by about 10%.Finally,utilizing the parallel computing characteristic of Field Programmable Gate Array(FPGA),we successfully implement the modified EDSM algorithm in an XC5 VLX20 T chip of Xilinx Virtex5 series.Experiment results show that only 0.37 ms is required to complete a 256-bit scalar multiplication.Compared with the pipelined array structure of modular multiplication in high-based Montgomery,the computation speed of scalar multiplication in the experiment is increased by 50%.Our method also has a good portability since there is no requirement for the dedicated multiplier inside the device in the experiment.

关 键 词：标量乘法 椭圆曲线密码 Edwards曲线 现场可编程门阵列 可移植性 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]