FPGA Design And Implementation Of Edwards Curve Scalar Multiplication Algorithm

Elliptic Curve Cryptography(ECC)algorithm is a public key cryptography algorithm,which has the advantages of being shorter than RSA keys,higher security strength,less power consumption,less storage space,etc,and it is widely used Fast encryption,identity authentication,digital signature and other fields.At present,most researches on elliptic curves are directed to Weierstrass curves,but few studies on Edwards curves.This article focuses on the scalar multiplication algorithm on the Edwards curve.Scalar multiplication is the core operation on ECC,and its operation speed directly affects the efficiency of the entire cryptographic algorithm.The scalar multiplication algorithm implementation is a layered process from top to bottom,which is mainly composed of the modular operation on the bottom finite field and the point operation on the top elliptic curve layer.Modular multiplication in the underlying modular operation is a key operation.In this paper,the traditional Montgomery modular multiplication is improved.A serial-parallel hybrid structure with variable iteration steps is used to reduce the number of clocks in the modular multiplication operation.The occupancy gives the best number of iterations.Through simulation on FPGA platform,the modular multiplier designed in this paper only needs 0.38 us to complete a 256-bit prime domain modular multiplication.For the operation of points on elliptic curves,this paper studies separately from the affine coordinate system and the standard projective coordinate system.In these two coordinate systems,according to the calculation formula of point operation,the structural design of the point addition operation and the double point operation are studied,and the algorithm of continuous double point algorithm CDA(Continues Doubling Algorithm)is given in the affine coordinate system.Structural design,the algorithm can effectively reduce the number of modular inverse operations.In order to increase the calculation speed of point operation,the parallel call structure is used for the point addition operation and double point operation.The results show that the double point operation speed in the affine coordinate system is increased by 48%,and the point addition operation speed is increased by 46%.Similarly,the double point operation speed in the standard projective coordinate system is increased by 42%,and the point addition operation speed is increased by 35%.Research on the scalar multiplication algorithm.In the affine coordinate system,expressing the scalar k as a 4-NNAF form can reduce the length of k.Combining the continuous doubling point algorithm to calculate the scalar multiplication can effectively reduce the amount of calculation.This scheme makes the efficiency of scalar multiplication operation increased by more than 13%.In order to further improve the operation speed,it is proposed to use a parallel structure for the multiplication and modular inverse operations in CDA to reduce the number of scalar multiplication operations.The calculation results show that the computational efficiency after parallelization is improved by more than 36%.In the standard projective coordinate system,in order to reduce the calculation amount of scalar multiplication,the EDSM algorithm is improved,and an algorithm is designed to express the scalar k in quaternary form to calculate the scalar multiplication.The theoretical analysis and calculation show that the improvement The efficiency of the algorithm is better than the original algorithm,and the calculation speed is increased by about 10%.Combined with the characteristics of FPGA parallel computing,the running results in the XC5VLX20 T chip of Xilinx Virtex5 series show that it takes only 0.37 ms to complete a 256-bit scalar multiplication.By comparing with other literatures,the scalar multiplication algorithm designed in this paper is more efficient in operation,and the dedicated multiplier inside the device is not used in the operation,so it has good portability,which makes this algorithm can be used in other hardware platforms.