We present a practical selective forgery attack against RSA signatures with fixed-pattern padding shorter than two thirds of the modulus length. Our result extends the practical existential forgery of such RSA signatures that was presented at Crypto 2001. For an n-bit modulus the heuristic asymptotic runtime of our forgery is comparable to the time required to factor a modulus of only 9/64n bits. Thus, the security provided by short fixed-pattern padding is negligible compared to the security it is supposed to provide.
|Title of host publication||Public key cryptography : proceedings PKC 2002, Paris, France, February 12-14, 2002|
|Editors||D. Naccache, P. Paillier|
|Place of Publication||Berlin|
|Publication status||Published - 2002|
|Name||Lecture Notes in Computer Science|