Rabin has proposed a public key signature scheme, based on the RSA cryptosystem, in which the difficulty of forging signatures is equivalent to the difficulty of factoring integers. Although there is an apparent cleartext attack on the scheme, this can be thwarted by perturbing the bits of the message before it is sent. (Rabin’s suggested perturbation is: if the number n to factor is assumed to be 500 bits long, to add 60 random bits to the message, and then to compress the message with a one-way function.)

The possible problem with this scheme is the temptation not to compress if the message, after the random bits have been added, is still less than 500 bits (this could be the case for a logon procedure, for example). The authors show that if compression is not done, the method can be as easy to attack (given the above parameters of number of bits) as factoring 120-bit numbers (36 decimal digits), something which is essentially trivial even on a VAX. Their attack would be successful unless most of the bits of the original message have been perturbed by the various transformations. This paper is short, clear, complete, and well worth reading.