On double exponentiation for securing RSA against fault analysis

Abstract

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φ(N)-d) and then check that the output pair satisfies the consistency relation: md · m φ(N)-d ≡ 1 mod N. The author then proposed an efficient heuristic to derive an addition chain for the pair (d, φ(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. © 2014 Springer International Publishing.