改进的蒙哥马利模乘算法及FPGA实现

Improved Montgomery Modular Multiplication Algorithm and FPGA Implementation

为了保障用户线上信息的安全,常采用公钥密码系统对数据信息进行加密。大整数模乘运算作为公钥密码系统的核心操作,其计算效率对公钥密码系统的性能至关重要。文中基于经典的蒙哥马利模乘算法,提出一种多项式展开的交叉蒙哥马利模乘算法。通过分解大位宽逻辑运算,以多项式展开来交叉执行模乘法和模约简运算,有效提高了大整数模乘运算的计算效率,降低了硬件实现的资源消耗。FPGA实验验证表明,相比于其它方法,文中所提方法分别减少96.5%和69%的面积时间积AT1与AT2,更好地实现了计算时间和硬件开销的平衡,有较高的灵活性和通用性,适合具有大量加密需求的成本敏感型应用。

In order to ensure the online information security of users,the public key cryptosystem is used to encrypt the data information.As the core operation of public key cryptosystem,the computation efficiency of large integer modular multiplication is very important to the performance of public key cryptosystem.In this study,a polynomial expanded cross Montgomery modular multiplication algorithm is proposed,which is based on the classical Montgomery modular multiplication algorithm.By decomposing large bit-width logic operations,and performing modular multiplication and modular reduction operations with polynomial expansion,this algorithm can effectively improve the calculation efficiency of large integer modular multiplication operations,and reduce the resource consumption of hardware implementation.FPGA experiment verification shows that compared with other methods,the proposed algorithm can reduce AT1 and AT2(the products of area and time)by 96.5%and 69%respectively,indicating that the proposed method achieves the balance between computing time and hardware overhead,has high flexibility and universality,and is suitable for cost-sensitive applications with a large number of encryption requirements.