Abstract

  Modular arithmetic is the most dominant part of the computation which is performed in the RSA public-key cryptosystem and key exchange scheme for cryptographic applications. Namely, most modern cryptographic protocols, which require a large number of multiplications, are based on modular arithmetic. Efficient algorithm design, redundancy elimination and numerical analyses for performing modular multiplication operation, which is crucial to cryptosystem and authentication schemes, are important in today’s needs of secure communications .Modular exponentiation of long integers is required in a number of public-key cryptosystem. The operands are considerably large. Performing modular exponentiation is computationally very complexity. In several public-key cryptosystems, the main operation consists of the modular exponentiation, which is performed using successive modular multiplications. In order to better reduce the execution time in these cryptosystems, the total number of modular multiplications must be reduced. In this paper, we propose an efficient method for computing modular exponentiation with the addition chain technique and a different base recoding. This algorithm can be proved useful and practical for information security usage such as key-exchange scheme and public-key cryptosystems.

Keywords: Information security, exponentiation, complexity analysis, algorithm, cryptography.

Associated Professor Chia-Long Wu is in the Department of Aviation Communication & Electronics, Chinese Air Force Technology, Taiwan, R.O.C. (chialongwu@seed.net.tw).

© 2008 Crisis Management Society, Taiwan, R.O.C.  Manuscript received 22, March, 2008; accepted 22, July., 2008              JCM080900955IFS