Electronic Science and Technology ›› 2022, Vol. 35 ›› Issue (7): 58-63.doi: 10.16180/j.cnki.issn1007-7820.2022.07.010

Previous Articles     Next Articles

Improved Montgomery Modular Multiplication Algorithm and FPGA Implementation

CHENG Biqian,LIU Guangzhu,XIAO Hao   

  1. School of Microelectronics,Hefei University of Technology,Hefei 230009,China
  • Received:2021-02-10 Online:2022-07-15 Published:2022-08-16
  • Supported by:
    National Natural Science Foundation of China(61974039)


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.

Key words: Montgomery modular multiplication, modular multiplication of large integer, RSA cryptographic algorithm, public key cryptography algorithm, information security, FPGA, hardware acceleration, software-hardware co-design

CLC Number: 

  • TP309.7