Cryptanalysis of RSA Signatures with Fixed-Pattern Padding

A fixed-pattern padding consists in concatenating to the message m a fixed pattern P. The RSA signature is then obtained by computing P|md mod N where d is the private exponent and N the modulus. In Eurocrypt ’97, Girault and Misarsky showed that the size of P must be at least half the size of N (in other words the parameter configurations |P| < |N|/2 are insecure) but the security of RSA fixed-pattern padding remained unknown for |P| > |N|/2. In this paper we show that the size of P must be at least two-thirds of the size of N, i.e. we show that |P| < 2|N|/3 is insecure.