High-performance montgomery modular multiplier with NTT and negative wrapped convolution

Modular multiplication plays a crucial role in modern cryptography. Montgomery modular multiplication(MMM), one of the most classic and practical modular multiplication algorithms, has been widely used in cryptographic algorithms such as RSA, Diffie-Hellman algorithm, and Elliptic Curve Cryptography. In this paper, we incorporate negative wrapped convolution (NWC) into the FFT-based Montgomery modular multiplication to avoid the issue of zero-padding and use carry-save arithmetics for parallel computation. By utilizing coefficient pairs (pos_part and neg_part), we reconstruct the final result and eliminate the restrictions imposed by nega-cyclic parts. Moreover, Karatsuba-like algorithm is introduced for building fine-grained large integer multipliers. We have modified the parameter specifications for our design to meet requirements from diverse application scenarios. We implement the design on Xilinx Virtex-7 FPGA under different conditions and compare the results with the state-of-the-art MMM designs. The comparisons confirm that our design has the following characteristics: low latency for process, competitive area-latency-product(ALP), efficient DSP usage, and constant delay, which enhances security against timing attacks.