Research On SM9 Algorithm And FPGA Implementation

With the widespread application of cryptography in the field of information security,the realization of cryptosystems and related cryptographic protocols has continuously become a research hotspot in the field of cryptography.Safe and efficient cryptography is also an important guarantee for national information security.SM9 is an identification-based cryptographic algorithm standard issued by my country in 2016.Its key operation is the calculation of bilinear pairing based on elliptic curves.The SM9 algorithm standard adopts the R-ate bilinear pairing algorithm.Aiming at the problem that the high computational complexity of the bilinear pairing restricts the efficiency of the entire SM9 algorithm,This paper analyzes and researches R-ate's algorithm,and optimizes key operations to improve the speed of algorithm implementation.After completing the FPGA implementation of Rate's algorithm,the digital signature and verification algorithm in the SM9 algorithm standard is further completed.This article first introduces the theoretical basis of R-ate bilinear pairing,mainly including the theoretical development of bilinear pairing and the research progress of software and hardware implementation,and introduces the application of bilinear pairing in SM9.Subsequently,the algorithm is optimized for the R-ate adopted by the SM9 standard,which mainly includes the Miller loop,the final modular exponentiation calculation,and the domain expansion calculation.The main research is as follows:1.In the Miller loop part,by converting the coordinate system to Jacobian coordinates,the point addition,point multiplication and linear function involved are calculated.Aiming at the feature of coefficient sparseness in linear function expressions,this paper designs a new sparse multiplication on the twelve-fold extension,which can reduce the calculation amount by 27% compared with the ordinary twelve-fold extension multiplication and 51%compared with the existing sparse multiplication,This algorithm can effectively improve the efficiency of Miller loop calculation.2.In the adjustment stage after the end of the Miller cycle,this article analyzes the element conversion between the second expansion and the twelfth expansion in detail.A parallel calculation method is designed so that the conversion process and Frobenius automorphism calculation only need 6 fundamental domain modular multiplication and 6fundamental domain modular addition and subtraction.In the final modular exponentiation part,the existing algorithm steps are optimized according to the power decomposition method,which can reduce the 12-fold base domain modular multiplication without increasing the temporary registered variables.3.In the study of expansion field operation,for the expression of the tower expansion field elements,the basic operations on different expansion fields are researched and designed from the two perspectives of ordinary polynomial multiplication and Karatsuba thought.Through the comparison of calculation amount,it is concluded that the use of Karatsuba's idea has advantages in reducing the amount of calculation.Modular operations on the underlying base field use variable step length Montgomery modular multiplication and binary modular inverse algorithms.On this basis,a secondary expansion field inversion algorithm is designed to make the expansion field inversion suitable for the Montgomery field.Finally,this article designs a suitable hardware architecture and uses Verilog language to write code.The R-ate algorithm code is simulated on the Modelsim platform,and the result is verified to be correct.Secondly,choose Xilinx Virtex-7 chip to synthesize on Synplify Pro platform,and it takes about 5.9ms to complete a R-ate pair calculation under the balance of speed and resources.Then combined with the R-ate algorithm module,write code to implement the digital signature and verification part of the SM9 algorithm standard and simulate,and the results of each step are verified correctly.