On the Multiple Fault Attack on RSA Signatures with LSBs of Messages Unknown
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.