Paper 2012/491

On the Multiple Fault Attack on RSA Signatures with LSBs of Messages Unknown

Lidong Han, Wei Wei, and Mingjie Liu


In CHES 2009, Coron, Joux, Kizhvatov, Naccache and Paillier(CJKNP) introduced a fault attack on RSA signatures with partially unknown messages. They factored RSA modulus $N$ using a single faulty signature and increased the bound of unknown messages by multiple fault attack, however, the complexity multiple fault attack is exponential in the number of faulty signatures. At RSA 2010, it was improved which run in polynomial time in number of faults. Both previous multiple fault attacks deal with the general case that the unknown part of message is in the middle. This paper handles a special situation that some least significant bits of messages are unknown. First, we describe a sample attack by utilizing the technique of solving simultaneous diophantine approximation problem, and the bound of unknown message is $N^{\frac1{2}-\frac1{2\ell}}$ where $\ell$ is the number of faulty signatures. Our attacks are heuristic but very efficient in practice. Furthermore, the new bound can be extended up to $N^{\frac1{2}^{1+\frac1{\ell}}}$ by the Cohn-Heninger technique. Comparison between previous attacks and new attacks with LSBs of message unknown will be given by simulation test.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Fault AttacksRSA SignaturesLeast Significant Bits (LSBs)ISOIEC} 9796-2LLL Algorithm
Contact author(s)
hanlidong @ mail tsinghua edu cn
2012-09-03: received
Short URL
Creative Commons Attribution


      author = {Lidong Han and Wei Wei and Mingjie Liu},
      title = {On the Multiple Fault Attack on RSA Signatures with LSBs of Messages Unknown},
      howpublished = {Cryptology ePrint Archive, Paper 2012/491},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.