As the number of computer systems and networks increase, their security becomes one of the most important problems. An efficient method of protecting information is to construct a cryptosystem, and to make the intercepter be unable to get information from the data being transmitted. An public-key cryptosystem is the efficient method for secure key distribution among cryptosystems, so it is studied by many reseachers.
A modular exponentiation is one of the most important operations in public-key cryptography. It takes much time because the modular exponentiation deals with very large operands as 512-bit integers. The modular exponentiation is composed of repetition of modular multiplications. Therefore, we can reduce the execution time by reducing the number of repetitions or by reducing the execution time of each modular multiplication. In this paper, we propose an addition-chain heuristic and two fast modular multiplication algorithms. Of two modular multiplication algorithms, one is for modular multiplications between different integers, and the other is for modular squarings.
The proposed addition-chain heuristic finds the shortest addition-chain among exisiting algorithms. Two proposed modular multiplication algorithms require single-precision multiplications fewer than those of Montgomery modular multiplication algorithms which are the fastest algorithms among existing ones by 1/2 and 1/3 times, respectively. Implementing on PC, proposed algorithms reduce execution times by 50% and 30% compared with Montgomery algorithms, respectively.
