Lecture Notes in Computer Science, No. 1403, pp. 211-220, Springer-Verlag, 1998.
Gérard COHEN (*), Antoine LOBSTEIN (*), David NACCACHE (#), Gilles ZÉMOR (*)
(*) Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
(#) Gemplus Card International
34 rue Guynemer, 92447 Issy-les-Moulineaux cedex, France
Abstract. In this paper we present a method for improving the performance of RSA-type exponentiations. The scheme is based on the observation that replacing the exponent $d$ by $d' = d + k \phi (n)$ has no arithmetic impact but results in significant speed-ups when $k$ is properly chosen. Statistical analysis, verified by extensive simulations, confirms a performance improvement of 9.3% for the square-and-multiply scheme and 4.3% for the signed binary digit algorithm. However, the most attractive feature of our method seems to be the fact that in most cases, existing exponentiation black-boxes can be accelerated by simple external one-time pre-computations without any internal code or hardware modifications.