A New Montgomery Modular Multiplication Algorithm and its VLSI Design for RSA Cryptosystem

Modular exponentiation for RSA cryptosystem is usually accomplished by repeated modular multiplications on large integers, which is considerably time-consuming. To speed up the operation, the Montgomery modular multiplication algorithm is employed to eliminate the trial division, and the carry-save addition is used to alleviate the carry propagation delay. In this paper, we propose a unified Montgomery modular multiplication algorithm that can be applied to fulfil either the conventional modular multiplication or squaring operation in carry-save form so as to achieve area-efficient design of modular exponentiation. Meanwhile, we reduce the number of input operands for carry-save addition by mathematical manipulation to minimize the resulting critical path delay. Compared with the existing works, our modular exponentiation design obtains the least hardware complexity and outperforms them in terms of area-time (AT) complexity.