Novel algorithms and hardware architectures for Montgomery Multiplication over GF(p)

This report describes the design and implementation results in FPGAs of a scalable hardware architecture for computing modular multiplication in prime fields GF(p), based on the Montgomery multiplication (MM) algo-rithm. Starting from an existing digit-serial version of the MM algorithm, a novel digit-digit based MM algorithm is derived and two hardware architec-tures that compute that algorithm are described. In the proposed approach, the input operands (multiplicand, multiplier and modulus) are represented using as radix β = 2k. Operands of arbitrary size can be multiplied with modular reduction using almost the same hardware since the multiplier’s kernel module that performs the modular multiplication depends only on k. The novel hardware architectures proposed in this paper were verified by modeling them using VHDL and implementing them in the Xilinx FPGAs Spartan and Virtex5. Design trade-offs are analyzed considering differen