RSA encryption and decryption using the redundant number system on the FPGA

The main contribution of this paper is to present efficient hardware algorithms for the modulo exponentiation P^E mod M used in RSA encryption and decryption, and implement them on the FPGA. The key ideas to accelerate the modulo exponentiation are to use the Montgomery modulo multiplication on the redundant radix-64 K number system in the FPGA, and to use embedded 18 times 18-bit multipliers and embedded 18 k-bit block RAMs in effective way. Our hardware algorithms for the modulo exponentiation for R-bit numbers P, E, and M can run in less than (2R + 4)(R/16 + 1) clock cycles and in expected (1.5R + 4)(R/16 +1) clock cycles. We have implemented our modulo exponentiation hardware algorithms on Xilinx VirtexII Pro family FPGA XC2VP30-6. The implementation results shows that our hardware algorithm for 1024-bit modulo exponentiation can be implemented to run in less than 2.521 ms and in expected 1.892 ms.