Tabulated Modular Exponentiation (TME) Algorithm for Enhancing RSA Public  Key Encryption Speed

Hamza Ali and Hamed Fawareh

Department of Computer Science, Zarka Private University, Jordan

Abstract: Improving software algorithms is not an easy task, especially for increasing operating speed and reducing complexity. Different algorithms implemented in cryptosystems used the exponentiation modular arithmetic; they however, suffer very long time complexity. Therefore, faster algorithms are strongly sought. This paper provides fast algorithms for modular multiplication and exponentiation that are suitable for implementation in RSA and DSS public key cryptographic schemes. A comparison of the time complexity measurements for various widely used algorithms is performed with the aim of looking for an efficient combination for the implementation of RSA cryptosystem. Two such algorithms were proposed in this work. The first is a modified convolution algorithm for modular multiplication while the second is a Tabulated Modular Exponentiation (TME) algorithm based on the modified sign-digit algorithm. They are found to give significant overall improvement to modular exponentiation over that of the fastest algorithms studied.

 Keywords: Data security, cryptography, authentication, algorithms, RSA, DSS. 

Received February 2, 2003; accepted May 11, 2003