一种模2k求逆算法的改进及实现

Improvement and implementation of mode 2k modular inversion algorithm

模2k求逆算法是RSA密码体系的核心运算之一。通过分析现有算法及RSA算法中求逆运算的特点,在扩展Euclidean算法基础上,提出了一种改进的模2k求逆算法。该算法与原算法相比迭代次数减少1/3,不仅简化加法进位的处理,而且省去了部分大数加减法操作。同时给出新算法硬件电路结构及数据验证方法,并实现了2 048位模2k求逆硬件电路设计。仿真验证结果表明,改进后的算法与原算法相比,电路面积减小了18.5%,运算速度提高了34.2%。

Mode 2k modular 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 2k modular inver- sion algorithm which is based on extended Euclidean algorithm. Compared with the original algorithm, the number of itera- tions 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 veri- fication method, and designs the 2048 - bit mode 2k modular inversion hardware circuit. Simulation results show that, com- pared to the original algorithm, the circuit area is reduced by 18.5% and the computation speed is increased by 34.2%.