Paper 2009/165

Securing RSA against Fault Analysis by Double Addition Chain Exponentiation

Matthieu Rivain

Abstract

Fault Analysis is a powerful cryptanalytic technique that enables to break cryptographic implementations embedded in portable devices more efficiently than any other technique. For an RSA implemented with the Chinese Remainder Theorem method, one faulty execution suffices to factorize the public modulus and fully recover the private key. It is therefore mandatory to protect embedded implementations of RSA against fault analysis. 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. 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) .
Contact author(s)
m rivain @ oberthur com
History
2009-07-28: revised
2009-04-10: received
See all versions
Short URL
https://ia.cr/2009/165
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/165,
      author = {Matthieu Rivain},
      title = {Securing RSA against Fault Analysis by Double Addition Chain Exponentiation},
      howpublished = {Cryptology ePrint Archive, Paper 2009/165},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/165}},
      url = {https://eprint.iacr.org/2009/165}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.