International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 03 September 2012

Lidong Han, Wei Wei, Mingjie Liu
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.