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.

  • 1
    $\begingroup$ 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) $\endgroup$ – poncho Sep 19 '14 at 4:40
  • $\begingroup$ I am talking about hashed, padded message, i.e. the number to be taken to the power of d. $\endgroup$ – updogliu Sep 19 '14 at 4:50
  • $\begingroup$ 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$. $\endgroup$ – fgrieu Sep 19 '14 at 5:34
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Sep 19 '14 at 13:49
  • 1
    $\begingroup$ @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). $\endgroup$ – poncho Sep 19 '14 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.