Information Security and Cryptology

In CHES 2009, Coron, Joux, Kizhvatov, Naccache and Paillier (CJKNP) introduced the multiple fault attack on RSA signatures with partially unknown messages. However, the complexity of their attack is exponential in the number of faulty signatures. At RSA 2010, this fault attack was improved, which runs in polynomial time in the number of faults. Both of the previous fault attacks deal with the general case. This paper considers the special situation that some least significant bits (LSBs) of messages are unknown. Because of this special case, our new multiple fault attack can handle a larger size of the unknown part of message. We provide two kinds of techniques to factor the RSA modulus N using the multiple faulty signatures. Comparisons between the previous attacks and the new attacks with a number of LSBs of the message unknown are given on the basis of the simulations.