FPGA-based Hardware Architecture For Montgomery Modular Exponentiation Algorithm*

With the explosive growth in data communications and internet services, public key cryptography such as RSA is crucial for information privacy and security. As an important research topic, RSA can support confidentiality, authentication, data integrity and non-reputation for networks. In the process of the RSA algorithm, modular arithmetic is a fundamental operator, which requires a long time to execute, especially since the size of modular is at least 256 bits for long-term security. Montgomery Modular Multiplication (MMM) algorithm and Montgomery Modular Exponentiation (MME) algorithm are the two most popular solutions to implement modular arithmetic efficiently. But the execution time of modular arithmetic is still too long under some of the conditions. To further accelerate the modular arithmetic, this paper proposes a FPGA-based hardware architecture for MMM and MME algorithm, in which the size of the modular is 256 bits. The delay of the adder’s long carry propagation in MMM algorithm is eliminated by using carry-lookahead adder. In addition, the architexture contains a finite state machine to implement the MME algorithm and repeatedly execute the MMM algorithm. To verify the performance of the hardware architecture, the hardware design is mapped to a special device. And execution time is compared between FPGA and CPU. The result shows hardware implementation is executed 1752.5 and 628.9 times faster than the software implementation for MMM algorithm and MME algorithm respectively.