Research On High Performance Elliptic Curve Scalar Multiplication Algorithm

The rapid development of the Internet is directly related to scientific and technological innovation,the development of the information industry and the rise of the knowledge economy.Information network is becoming the basis for economic prosperity,social stability and national development.Informatization has seriously affected the integration of the world economy,the adjustment of national strategies and the change of security concepts.Under such a global information background,China has ushered in valuable opportunities for its development.While developing,national security is also facing severe challenges.Cryptography plays a role of security,confidentiality,integrity and not being tampered with in the communication process,so this paper focuses on the research and analysis of Elliptic Curve Cryptography(ECC),one of the branches of cryptosystem.In this paper,a low complexity scalar multiplication algorithm is designed through the research of ECC scalar multiplication algorithm,and the overall hardware design and implementation of the algorithm are carried out.Because prime field is more secure than binary field,this paper selects P521,P384 and P256 prime field curves recommended by NIST as the curves used in hardware design and implementation.The main contents of the paper are as follows:(1)The scalar multiplication algorithm is divided into non precomputing algorithm and precomputing algorithm,and the algorithm with precomputing is analyzed.It is concluded that although the precomputing algorithm can achieve good results,there are still problems such as inapplicability to large window width,more registers used,and too much prediction computation.To solve the above problems,this paper improves the window width Non Adjacent Form(w NAF)algorithm and designs an improved w NAF algorithm with low complexity.To ensure the correctness of the algorithm,it is verified on the Python version2021.3.2.PC-213.6777.50 Compared with w NAF algorithm,when the window width is 11,the pre calculated points are reduced by 98.83% respectively;The computational complexity of scalar multiplication is optimized by 78.23%.(2)An ECC processing unit oriented to three prime field curves is designed.First,modular multiplication unit,modular addition and subtraction unit and modular inversion unit are designed.Secondly,this paper uses the mode of parallel operation of one modular addition unit and two modular multiplication units to complete the architecture design of point addition and multiple points.This design can not only complete point addition and multiple point operations in less cycles,but also improve the operation speed of scalar multiplication,Moreover,the modular addition unit and modular multiplication unit are fully utilized to reduce resource waste.The hardware architecture diagram of ECC processing unit is obtained through coordinate conversion of modular inversion unit and storage of intermediate results by memory.Finally,the designed processing unit is modeled by Verilog,and modelsim is used for simulation and DC logic synthesis.