Improvement and implementation of mode 2~k modular inversion algorithm
Cui Chenq · Journal of Chongqing University of Posts and Telecommunications · 2015
Mode 2kmodular inversion operation is one of the core operations in RSA cryptography. By analyzing the existing algorithms and inverse operation characteristics of RSA algorithm,this paper presents an improved mode 2kmodular inversion algorithm which is based on extended Euclidean algorithm. Compared with the original algorithm,the number of iterations reduces one-third,the new algorithm can not only simplify the processing of carry adder,but also avoid some addition and subtraction operations of large numbers. At the same time,the paper gives the hardware circuit structure and data verification method,and designs the 2048- bit mode 2kmodular inversion hardware circuit. Simulation results show that,compared to the original algorithm,the circuit area is reduced by 18. 5% and the computation speed is increased by 34. 2%.