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
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
-
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},
url = {https://eprint.iacr.org/2009/165}
}
