# Is it possible (how difficult) to find MORE than one valid RSA signature?

Is it possible (how difficult) to find more than one valid RSA signatures for a given message m (after padded) and a public key e (with the private key d known). Apparently signing m with d gives one valid signature. My question is how difficult to find another one. Thanks.

• Depends entirely on the padding method. With any nondetermanistic padding method (e.g. PSS), it's easy. With, say, PKCS#1.5, well, I suppose you could generate distinct signatures by using different hash functions (say, SHA-256 and SHA-512) – poncho Sep 19 '14 at 4:40
• I am talking about hashed, padded message, i.e. the number to be taken to the power of d. – updogliu Sep 19 '14 at 4:50
• The answer depends on if A) signatures verifiable by different public keys count; B) the scheme is deterministic [e.g. ISO/IEC 9796-2 methods 1 and 3] or not; C) access to the private key function $x\to x^d\bmod N$ is available; D) details in the verifier definition/implementation, e.g. is $S+N$ just as valid as $S$. – fgrieu Sep 19 '14 at 5:34
• For a maliciously generated key with $\mathrm{GCD}(e, \phi(n))>1$ there should be several different values that become the same after raising to the $e$th power. – CodesInChaos Sep 19 '14 at 13:49
• @CodesInChaos: actually, if $\operatorname{GCD}(e, \phi(n)) > 1$, then it's more likely that no such signature exists. However, if one does exist, it is likely that many others do as well (if $e$ is prime, both $e$ and $e^2$ total are possible). – poncho Sep 19 '14 at 14:12