High-Speed FPGA Implementation of Full-Word Montgomery Multiplier for ECC Applications

Abstract

Modular multiplication is the most crucial operation in many public-key crypto-systems, which can be accomplished by integer multiplication followed by a reduction scheme. The reduction scheme involves a division operation that is costly in terms of computation time and resource consumption both on hardware and software platforms. Montgomery modular multiplication is widely used to eliminate the costly division operation. This work presents an efficient implementation of full-word Montgomery modular multiplication. This incorporates the more efficient Karatsuba algorithm where the complexity of multiplication is reduced form O(n2) to O(n1.58). The Karatsuba algorithm recommends to split the operands into smaller chunks. Two methods of operand splitting are exploited: 1) Four Parts (FP) Splitting and 2) Deep Four Parts (DFP) Splitting. These methods are then used in the design of Integer Multiplier (IM) and Montgomery Multiplier (MM). The design is synthesized using Xilinx ISE 14.1 Design Suite for Virtex-5, Virtex-6 and Virtex-7. Compared with the traditional implementations, the proposed scheme outperforms all other designs in terms of throughput and area-delay product. Moreover, the proposed scheme utilizes the least hardware resources in the known literature. The proposed MM design is able to compute modular multiplication for the Elliptic Curve Cryptography (ECC) field sizes of 192-512 bits.