The padding scheme for RSA signatures

The RSA scheme is used to sign messages; however, in order to avoid forgeries, a message can be padded with a fixed string of data <i>P</i>. De Jonge and Chaum showed in 1985 that forgeries can be constructed if the size of <i>P</i> (measured in bytes) is less than the size of <i>N/3</i>, where<i> N</i> is the RSA modulus. Girault and Misarsky then showed in 1997 that forgeries can be constructed if the size of <i>P </i>is less than the size of <i>N/2</i>. In 2001, Brier, Clavier, Coron and Naccache showed that forgeries can still be constructed when the size of <i>P</i> is less than two thirds the size of <i>N</i>. In this paper, we demonstrate that this padding scheme is always insecure; however, the complexity of actually finding a forgery is <i>O(N). </i>We then focus specifically on the next unsettled case, where <i>P</i> is less than 3/4 the size of <i>N </i>and show that finding a forgery is equivalent to solving a set of diophantine equations. While we are not able to solve these equations, this work may lead to a break-through by means of algebraic number theory techniques.