Double Counting in 2 t -ary RSA Precomputation Reveals the Secret Exponent

Double Counting in 2t -ary RSA Precomputation Reveals the Secret Exponent

Abstract— A new fault attack, double counting attack (DCA), on the precomputation of 2 -ary modular exponentiation for a classical RSA digital signature < Final Year Projects 2016 > i.e., RSA without the Chinese remainder theorem >is proposed. The 2t -ary method is the most popular and widely used algorithm to speed up the RSA signature process. Developers can realize the fastest signature process by choosing optimum t . For example, t = 6 is optimum for a 1536-bit classical RSA implementation. The 2t -ary method requires precomputation to generate small exponentials of message. Conventional fault attack research has paid little attention to precomputation, even though precomputation could be a target of a fault attack. The proposed DCA induces faults in precomputation using instruction skip technique, which is equivalent to replacing an instruction with a no operation in assembly language. This paper also presents a useful position checker tool to determine the position of the 2t -ary coefficients of the secret exponent from signatures based on faulted precomputations.