Efficient and Scalable Hardware Implementation of Montgomery Modular Multiplication

Modular multiplication (MM) is an important arithmetic operation in public key cryptography (PKC). In this paper, we present the FPGA implementation of the MM using Montgomery MM (MMM) algorithm. The execution performances of this operation depend on the radiz-r and the operands length. In fact, when increasing the radix-r, the MMM algorithm requires multiplications of digit by operand. On the other hand, when a long modulus is used, the hardware implementation of the MMM needs a large area. Our objective in this work is to realize a scalable architecture able to support any operands length. In order to achieve a best trade-off between computation throughput and hardware resources, our implementation approach is based on the execution of the basic arithmetic operations in serial way. In addition, efficient parallel and pipelined strategies are realized at low-level abstraction for the optimization of the execution time. The implementations results on Virtex-7 circuit show that a 1024-bit MMM runs in 2.09 mu s and consumes 581 slices.