An Efficient Parallel CMM-CSD Modular Exponentiation Algorithm by Using a New Modified Modular Multiplication Algorithm

This paper presents a new modified Montgomery modular multiplication algorithm based on canonical signed-digit (CSD) representation, and sliding window method. In this modified Montgomery modular multiplication algorithm, signed-digit recoding technique is used in order to increase probability of the zero bits. Also sliding window method is used in order to reduce the multiplication steps considerably. In addition, a new efficient modular exponentiation algorithm based on this new modular multiplication algorithm, CMM method and parallel structure is presented. In this new CMM-CSD modular exponentiation algorithm, not only the common part of modular multiplication is computed once rather than several times but also the modular multiplication and modular squaring operations is performed in parallel. Using this new modular exponentiation algorithm, the security of the cryptosystem increased considerably. The results show that the average number of multiplication steps in the proposed CMM-CSD exponentiation algorithm is reduced considerably. Therefore, the efficiency of the proposed CMM-CSD modular exponentiation algorithm increased considerably in compare with Dusse-Kaliski’s Montgomery algorithm, Ha-Moon’s improved Montgomery algorithm, Wu’s CMM-MSD Montgomery algorithm, Wu et al.’s CMM-SDR Montgomery algorithm and Wu’s CMM-CSD Montgomery algorithm

Keywords:

public-key cryptography , security , fast modular exponentiation , Montgomery modular multiplication , signed-digit recoding