FPGA-based Design of a Large Moduli Multiplier for Public-Key Cryptographic Systems

High secure cryptographic systems require large bit-length encryption keys which presents a challenge to their efficient hardware implementation especially in embedded devices. Modular multiplication is the core operation in well known cryptosystems like RSA and elliptic curve (ECC). Therefore, it is important to employ efficient modular multiplications techniques to improve the overall performance of the cryptographic system. We present a modular multiplier based on the ordinary Montgomery´s multiplication algorithm and a new array multiplication scheme to perform the multiplication. The new modular multiplier is scalable and can be used for large bit-lengths. We also implement the modular multiplier into the Virtex4 FPGA devices and we show that our technique has better performance when compared with other schemes. To implement large bit-length multiplications we used a novel partitioning and pipeline folding scheme to fit at least 512-bit modular multiplications on a single FPGA.