This paper provides a new countermeasure against fault analysis for exponentiation and RSA. It consists in a {\em self-secure} exponentiation algorithm, namely an exponentiation algorithm that provides a direct way to check the result coherence. An RSA implemented with our solution hence avoids the use of an extended modulus (which slows down the computation) as in several other countermeasures. Moreover, our exponentiation algorithm involves $1.65$ multiplications per bit of the exponent which is significantly less than the $2$ required by other self-secure exponentiations.
Category / Keywords: implementation / Publication Info: Updated version of the paper published in the proceedings of CT-RSA 2009. A few misprints have been corrected. Some remarks concerning practical security have been added (Section 5). A minor mistake has been corrected in the time complexity analysis (Section 7.2). Some mistakes in the atomic algorithms have been fixed (Appendix B) . Date: received 9 Apr 2009, last revised 28 Jul 2009 Contact author: m rivain at oberthur com Available format(s): PDF | BibTeX Citation Version: 20090728:100001 (All versions of this report) Short URL: ia.cr/2009/165 Discussion forum: Show discussion | Start new discussion