High-performance modular exponentiation algorithm by using a new modified modular multiplication algorithm and common-multiplicand-multiplication method

Modular exponentiation is fundamental operation in the many cryptosystem such as RSA. This operation is implemented by repeating modular multiplication which is time consuming for large operands. This paper presents a new modified Montgomery modular multiplication algorithm based on multiple bit scan-multiple bit shift technique, sliding window method and signed-digit representation. This new algorithm skips from zero digit partial multiplication and the following required addition. Then it shifts the partial results by using Barrel shifter in only one cycle instead of several cycles. In addition, we proposed new modular exponentiation algorithm based on this new modular multiplication algorithm and common-multiplicand-multiplication method. In this new algorithm, the common part of modular multiplication is computed once rather than several times. So the security of the cryptosystem which used this new algorithm increased considerably. The analysis results show that the number of multiplication steps in the proposed exponentiation algorithm is reduced on average at about 72%-87%, 66%-84%, 15%-61% and 54%-79% in compare with Dusse-Kaliski's algorithm, Ha-Moon's algorithm, Wu et al.'s algorithm and Wu's algorithm respectively for d=3-8.