Efficient high radix modular multiplication for high-speed computing in re-configurable hardware

RSA is one of the most widely used public key cryptosystems, where modular multiplications are the computing intensive kernel of modular exponentiations constitute. An efficient fast modular multiplication algorithm is proposed to notably reduce the overall computation time of the modified Montgomery's algorithm. Simulation results show consistent improvements for a wide range of bit widths and radix k values with approximately 50% reduction in the computation time when compared to existing method. The proposed algorithm was ported to FPGA for bit widths ranging from 128 to 2048. Our results shows, for a bit width of 2048 with k = 1 significant speed-up in the computation can be realized when the proposed technique is ported to FPGA.