Recent attacks using differential power analysis (DPA) have shown how good equipment and poor implementation might be applied to break a single use of RSA on a smart card. The attacks are based on recognising the re-use of operands in the standard square-and-multiply, m-ary or sliding windows exponentiation schemes. A new algorithm is presented which avoids such operand re-use and consequently provides much greater resistance to DPA. It is based on generating random addition chains. Unlike the easier process of generating addition/subtraction chains (which have been applied to ECC), the algorithm does not require the computation of an inverse, and so is also applicable to RSA.
The talk will concentrate on two aspects of the algorithm, namely its efficiency and its security against side channel leakage. The former establishes performance akin to that of 4-ary exponentiation. The latter will assume the attacker can distinguish between squares and multiplies, and perhaps recognise re-use of operands. Under such attacks, it still appears to be computationally infeasible to recover the secret exponent.