Area and time efficient Montgomery multiplication and application to RSA

In present world Computer Systems, operations like Binary Multiplication have an extraordinary range of applications. Most of the applications and devices ranging from Computer processors to DSPs, ASICs and Embedded Controllers use the operation in a manner that is unique to the application. Hence several algorithms have been proposed each with modifications that are ideally suited for the target application. The Montgomery algorithm is one such multiplication algorithm that calculates products in the Modular domain. The final product in itself is not absolute and hence this algorithm is useful where one can utilize the redundant product form over several repetitive cycles typically a Multiply and Accumulate system. Since operations are performed in a Modular domain, the algorithm reduces very large numbers to mere Modulo-residues and the thereby the product also remains in the same format. Thus the Montgomery multiplication technique is used in applications, which require calculations on very large operands. The algorithm has been a subject of continuous optimization due to the large gains that are achieved in devices that use the same. The scope of the thesis includes a mathematical model of the Montgomery Multiplication algorithm and the proposed optimization to reduce hardware resources for the Implementation and improve speed. We discuss the implementation results, gains in area and waveform outputs. Encryption procedures like RSA are an ideal application for Montgomery multiplication. A brief introduction to the concept of RSA is presented. The multiplication algorithm implemented is used in an RSA encryption algorithm and synthesis, waveform output and gains in area are discussed. The design method used for both the modules is completely modular thereby making it easy to extend the architecture for larger designs.