On Double Exponentiation for Securing RSA against Fault Analysis
Published in CT-RSA, 2014
Recommended citation: Duc-Phong Le, Matthieu Rivain, Chik How Tan. (2014). "On Double Exponentiation for Securing RSA against Fault Analysis." CT-RSA 2014. https://eprint.iacr.org/2015/657.pdf
At CT-RSA 2009, a new principle to secure RSA (and modular/group exponentiation) against fault-analysis has been introduced by Rivain. The idea is to perform a so-called double exponentiation to compute a pair ($m^d, m^{\phi(N) − d}$) and then check that the output pair satisfies the consistency relation: $m^d, m^{\phi(N) − d} \equiv 1 \bmod N$. The author then proposed an efficient heuristic to derive an addition chain for the pair $(d, \phi(N) − d)$. In this paper, we revisit this idea and propose faster methods to perform a double exponentiation. On the one hand, we present new heuristics for generating shorter double addition chains. On the other hand, we present an efficient double exponentiation algorithm based on a right-to-left sliding window approach.
Recommended citation: Duc-Phong Le, Matthieu Rivain, Chik How Tan. (2014). On Double Exponentiation for Securing RSA against Fault Analysis. CT-RSA 2014.