Improving software algorithms are not easy task, especially for increasing operating speed, and reducing complexity. Different algorithms implemented in cryptosystems used the exponentiation modular arithmetic, however, they 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.

[1] Diffie W. and Hellman M.E., “New Direction in Cryptography,” IEEE Trans. Information Theary, vol. IT-22, no. 6, pp. 644-654, 1976.

[2] Rivest, R., Shamir A., and Adleman L., “Method for obtaining Digital Signature and Public Key Cryptosystem,” Comm. of ACM, vol. 21, no. 2, 1978.

[3] Mohan S. B., “Fast Algorithm for Implementing RSA Public-Key Cryptosystem,” Electronic Letters, vol. 21, no. 17, 1985.

[4] Robert S., Algorithms, Addison Wesley, USA, 1983.

[5] Selby A., “Algorithms for Software Implementation of RSA,” vol. 136, no. 3, 1989.

[6] Sloan, K. R., “A Computer Algorithm for Calculating A*B mod M,” IEE Trans. on Computers, vol. C-34, no. 3, 1985.

[7] Davis D. W., Security for Computer Networks, Wiley, UK, 1989.

[8] Saloma A., Public-Key Cryptography, Springer, 1996.

[9] Jedwab J. and Mitchell C. J, “Minimum Weight Modified Signed-Digit Representations and Fast Exponentiation”, Electronic Letters, vol. 25, no. 17, 1989.

[10] ElGamal T., “A Public Key Cryptosystem in a Signature Scheme Based on Discrete Logarithm,” IEEE Trans Information Theory, vol. IT-31, no. 4, 1985.

[11] Boneh D. and Franklin M., “Efficient Generation of Shared RSA Keys,” J. of ACM, vol. 48, no. 4, pp. 702-722, 2001.

[12] Schneier B., Applied Cryptography, John Wiley & Son, 1996.

[13] Naini S. R. and Wang H., “Broadcast authentication for Group Communication,” Theoretical Computer Science, vol. 269, pp. 1- 21, 2001.

[14] Rashid A. M. T., “Software Inplementation of RSA Public-Key Cipher for Microcomputer Protection and Authentication,” MSc Thesis, Basrah University, 1992.

[15] Campbell R., “Basics of Computational Number Theory,” http://www.math.umbc.edu.~campbell/ NumbThy/Basic NumberThy.html, last visited 11/5/2002.

[16] Cornam T., Leiserson C.E. and Rivest, R. L., Introduction to Algorithms, McGraw Hill Company, 1999.

[17] Bellare M; Garang J. A. and Rabin T., ³Fast Batch Verification for Modular Exponentiation and Digital Signature,´ Advances in Cryptography, Eurocrypt98 Proceedings, Lecture Notes in Computer Science, vol. 1403, 1998.

[18] Aho A., Hopcroft J. and Ullman J., The Design and Analysis of Computer Algorithms, Addison- Wesley, 1974.

[19] Blum T. and Paar C., ³High-Radix Montgomery Modular Exponentiation on Reconfigurable Hardware, ´ IEEE Trans. on Computers, http://www.computer.org/tc/tc2001/t0759abs.htm Hamza Ali received his BSc in physics from University of Basrah in 1968, MSc in electronics from University of London in 1973 and PhD in computer engineering from University of London in 1977. Previously he worked in Basrah University, Iraq, one year in Aizu University, Japan and currently associate professor at the Computer Science Department, Zarka Private University, Jordan. His research interest includes computer security and authentication, pattern recognition and neural networks. Hamed Fawareh received his PhD in software engineering from University Putra Malaysia, 2001. Currently, he is an assistance professor at the Department of Computer Science, Zarka Private University, Jordan. His research areas include software engineering, algorithm security, and Biocomputing.