A high-speed modular multiplier architecture based on modified Montgomery's multiplication algorithm

Many public-key cryptographic schemes make extensive use of modular exponentiation of long integers as its core arithmetic. Modular exponentiation can be accomplished by a sequence of modular multiplication. Therefore, the quest for intrinsic schemes to fast modular multiplication becomes the foremost need to real time encryption and decryption. In this thesis Montgomery's algorithm is revised such that modular multiplication can be executed nearly two times faster. The proposed algorithm is implemented by a two's complement Baugh-Wooley multiplier and a modular shifter-adder, both of which are designed as linear cellular arrays. The local interconnection, regularity and modularity make the proposed architecture suitable for VLSI implementation. The proposed modular multiplier would be simulated using VHDL (Very High Speed Integrated Circuits Hardware Description Language) followed by an implementation on a FLEX10K FPGA chip using MaxPlus II software.