High-performance scalable architecture for modular multiplication using a new digit-serial computation

• A new scalable Montgomery modular multiplication architecture is proposed.
• Variable-radix design with one clock cycle delay in data flow is presented.
• The complexity of high-radix multiplication is reduced to binary multiplication.
• The proposed architecture has area×time complexity and performance advantages.

Modular multiplication with a large modulus plays a vital role in many Public-Key Cryptosystems (PKCs) such as RSA and Elliptic Curve Cryptosystem (ECC). Montgomery modular multiplication algorithm is an efficient multiplication algorithm to simplify the quotient computation. The scalable architecture has been employed to perform the Montgomery modular multiplication with any precision of the modulus. This paper presents and evaluates a novel scalable modular multiplication algorithm/architecture with variable-radix. The proposed algorithm/architecture, which is based on a new digit-serial computation technique, parallelizes the data path to shorten the critical data path. It also reduces the complexity of the high-radix partial multiplications to binary partial multiplications. In this paper, we present implementation results on 0.18-µm ASIC technology, and on Xilinx Spartan 3, Virtex 2 and Virtex 6 FPGA. The results demonstrate that the proposed algorithm/architecture has area×time complexity and performance advantages compared to related algorithms/architectures.