What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures? I am attempting to determine the strength of an incorrectly implemented 1024 bit RSA signature scheme. The weakness in the implementation is that the padding data lacks random numbers. As a result, for every message signed, only 160 bits of data are changed (cryptographic hash).

How does one determine the resulting reduction of strength in the scheme, and how many signed messages would be necessary to make a 1024 bit private key a mathematically feasible operation to recover?
Well, there are no necessary 'reduction in strength', for two reasons:


You ask about how many signatures you'd need to recover the private key.  Well, even with unrestricted Oracle access to the private operation, there's no known way to recover the private key (or equivalently, factor the modulus) that's more efficient than just ignoring the Oracle and attacking the modulus directly.  Hence, giving the attacker access to a limited number of signatures cannot help him recover the private key.
What the attacker might be able to do with some padding methods is deduce the value of other signature operations; this would be generating a forgery without the private key.  Now, there are certainly known padding methods (such as a naive 'zero fill' method) that are prone to this.  On the other hand, there are deterministic padding methods (such as the PKCS #1.5 RSASSA-PKCS1-v1_5 method) for which there is no known method of generating forgeries easier than finding collisions in the hash function.


So, if the system is using, say, the above PKCS method, there is no known weakness, even if the attacker has access to huge numbers of signatures.