Selective Forgery of RSA Signatures Using Redundancy

We show the weakness of several RSA signature schemes using redundancy (i.e. completing the message to be signed with some additional bits which are fixed or message-dependent), by exhibiting chosen-message attacks based on the multiplicative property of RSA signature function. Our attacks, which largely extend those of De Jonge and Chaum [DJC], make extensive use of an affine variant of Euclid’s algorithm, due to Okamoto and Shiraishi [OS]. When the redundancy consists of appending any fixed bits to the message m to be signed (more generally when redundancy takes the form of an affine function of m), then our attack is valid if the redundancy is less than half the length of the public modulus. When the redundancy consists in appending to m the remainder of m modulo some fixed value (or, more generally, any function of this remainder), our attack is valid if the redundancy is less than half the length of the public modulus minus the length of the remainder. We successfully apply our attack to a scheme proposed for discussion inside ISO.