An Implementation of Montgomery Modular Multiplication on FPGAs

Modular multiplication is one of the most important operations in the public key cryptographic algorithms. In order to design a high-performance modular multiplier, we present a novel hybrid Montgomery modular multiplier over GF(p) on FPGAs, which employs Karatsuba and Knuth multiplication algorithms in different levels to implement large integer multiplication. A 9-stage pipeline full-word multiplier is proposed for the 256-bit multiplication with 4-level recursion. The performance of our modular multiplier is improved through optimizing the pipeline and reducing carry-chain latency of the modular adder. On average, our modular multiplier can perform one 256-bit modular multiplication in 3 cycles. We can integrate 13 modular multipliers on a Xilinx Virtex-6 V6VSX475T FPGA. The experimental results show that the throughput of 856.9 million modular multiplications per second can be achieved and the hybrid Montgomery modular multiplier has an outstanding performance in the situations which need continuous multiplications.