Hardware Complexity of Modular Multiplication and Exponentiation

Large integer modular multiplication (MM) and modular exponentiation (ME) are the foundation of most public-key cryptosystems, specifically RSA, Diffie-Helleman, EIGamal, and the elliptic curve cryptosystems. Thus, MM algorithms have been studied widely and extensively. Most of the work is based on the well-known Montgomery multiplication method and its variants, which require standard multiplication operations. Despite their better complexity orders, Karatsuba and FFT algorithms seem to rarely be used for hardware implementation. In this paper, we review their hardware complexity and propose original implementations of MM and ME that become useful for 24-bit operators (Karatsuba algorithm) or 373-bit operators (FFT algorithm).

1 Introduction

The ever-increasing needs in data communication and the expansion of Internet services, namely, financial applications and electronic commerce, have made security a major concern. Private-key cryptography is unfortunately impractical for such applications because of its main drawback: the Key Distribution Problem. Public-key cryptography [1], introduced in 1976, was the first bright solution and so far has been shown to be the only convenient security technique for such applications.