One high-efficiency full-word modular multiplier based on multi-layer Karatsuba algorithm

As the core algorithm of many cryptosystems, modular multiplication typically is a computation-intensive task and often the bottleneck of the system. To attack this problem, various modular multiplication oriented specific accelerator have been proposed. In order to further improve the circuit performance, a full-word Montgomery modular multiplier based on multi-layer Karatsuba algorithm theory for large number multiplication is proposed, which effectively increases the high radix computing efficiency for large number calculation. The proposed structure of multi-layer Karatsuba multiplier effectively reduces the granularity of multiplication operation and achieves the highest hardware utilization efficiency to continuously carry out large number multiplication, as well as effectively improves the running circuit frequency by utilizing piecewise calculation approach according to the data bit-width. The synthesis results based on Virtex 7 FPGA demonstrates that the clock frequency of the proposed circuit reaches 250 MHz, and 256 bit Montgomery multiplication is carried out in 33 cycles with 132 ns latency. To best of our knowledge, the proposed full-word Montgomery modular multiplier outperforms the state of art designs. The proposed design provides a generally practical reference for how to reduce both area and critical path latency of hardware multiplier through multi-layer Karatsuba algorithm.