A Low-Latency Optimization for FPGA-Based Modular Multiplication in Public-Key Algorithm

Large-integer modular multiplication (LMM) is a core operation in public-key algorithms, which serve as critical safeguards for information security. Although much effort has been made to improve its efficiency, traditional FPGA-based implementations of LMM still suffer from high complexity, data dependencies, and long latency. To address these issues, this paper proposes an optimized method based on the conventional CIOS (Coarsely Integrated Operand Scanning) modular multiplication algorithm. This proposal eliminates the data dependency between the quotient and the partial product by strategically shifting one operand of LMM. Besides, through asymmetric partitioning of internal operands, our proposal can efficiently exploit the computing power of FPGA by making full use of the embedded asymmetric multipliers, which are not suitable for traditional methods. Experimental evaluations on two widely adopted FPGA platforms demonstrate significant advantages of our proposal in both latency and area efficiency compared to state-of-the-art implementations. Our fastest version can achieve latencies of 0.52µs and 0.26µs for 2048-bit LMM and 1024-bit LMM, respectively, which saves 17% and 21% over the state-of-the-art implementation.