Area-Efficient Modular Multiplication on FPGA

Modular multiplication (MM) involves multiplica tion and modular reduction. In this brief, we explore an area-efficient modular reduction for MM on FPGA. We analyze and compare the equivalent LUT6 (ELUT6) cost when imple menting modular reduction using different memory strategies (BRAM/LUT6/LUT5), and adopt LUT5 (lowest ELUT6 cost) as the memory for this design. Then we propose an area-efficient compression strategy with a new (1,5;3) Generalized Parallel Counter (GPC), which reduces the LUT6 cost of compression operation in modular reduction compared to previous methods. Finally, we adopt the 4-term Karatsuba algorithm to reduce the area of multiplication, and explore the balance of hardware delay in MM. The proposed MM is implemented on the Xilinx Virtex-7 platform. Compared to the previous state-of-art pipeline design, the area of proposed MM is only 41.7%/47.6%/47.6%/50.0% of them when word-size w=32/64/128/256.

Index Terms—Cryptography, modular multiplication (MM), pipeline design, generalized parallel counter (GPC), FPGA