Implementations of Montgomery Multiplication Algorithms in Machine Languages.
E. Celebi, Mesut Gözütok, Levent Ertaul · Security and Management · 2008
Software implementations of public-key algorithms such RSA and Diffie-Hellman are often desired because of their flexibility and cost effectiveness. In order to obtain the required level of performance on a selected platform, developers turn to implement efficient algorithms in machine (assembly) languages for basic (kernel) operations. Among these basic operations, modular multiplication and exponentiation operations play an important role. This study concerns with fast software implementations of the Montgomery multiplication algorithms. Montgomery multiplication algorithms, which are the most popular algorithms used in public-key cryptography, serve as efficient algorithms for modular multiplication and exponentiation operations. In this paper implementations of five well known algorithms of Montgomery multiplication are given. Algorithms are implemented in assembly languages of Intel Pentium family and Sun Sparc family microprocessors. In order to get comprehensive performance results, they run on Windows 95, Windows 98, Windows NT 4.0, and Solaris 2.5.1 operating systems. The performance results are summarized with a comparison of the algorithms based on their software performances. Index Terms — Montgomery Multiplication, RSA and Diffie-Hellman Cryptosystems, Public-key cryptography.