I am aware of attacks whereby an attacker is able to forge a message IF the hash of the original message is the same hash as their current message. The question is, is it still possible for RSA-FDH to be EUF-CMA IF the hash function in question is collision-resistant. Lets take the case of $H(x) = 3x \mod N$. 3 is a prime number and N is always going to be prime as well. The function, in this case, is collision-resistant but despite this, is it still possible to break the EUF-CMA of RSA-FDH?

  • $\begingroup$ Actually I the RSA-FDH proof asks for a random oracle and not just for a collision-resistant hash. So yes there is an "easy" forgery against this scheme. $\endgroup$
    – SEJPM
    Commented Aug 25, 2019 at 16:58
  • $\begingroup$ Interesting... so even if it is a collision resistant hash, one could still forge a message? How is that even possible? $\endgroup$ Commented Aug 25, 2019 at 17:22
  • $\begingroup$ Trivial counter example: $H(x)=x$, suffers from all the weaknesses of textbook RSA signatures. The RSA problem is only hard if $x$ in $c=x^e\bmod n$ is chosen uniformly at random. $\endgroup$
    – SEJPM
    Commented Aug 25, 2019 at 17:57
  • $\begingroup$ Welcome to Crypto.SE! By collision resistant you mean in case where we restrict $x$ to $\{0,\ldots, N-1\}$? $\endgroup$ Commented Aug 26, 2019 at 18:24

2 Answers 2


The function, in this case, is collision-resistant but despite this, is it still possible to break the EUF-CMA of RSA-FDH?

Yes, because the requirement for security is the hash function acting like a random oracle and not it being collision-resistant.

To illustrate this, consider the "hash function" $H(x)=x$ which is clearly collision resistant. Yet, RSA-FDH instantiated with this hash is not secure as it literally is textbook RSA, which suffers from the usual small-exponent and homomorphic attacks (which also apply when $H(x)=3x\bmod N$).

This could of course raise the question "why, do we need this stronger assumption?". And the main reason is that the "RSA problem" - extracting $x$ from $x^e\bmod N$ for appropriately chosen $N$ and $e$ - isn't always hard. It is only hard when $x$ is chosen uniformly at random, which is kind of what the hash function is supposed to do here.


Let me note that no particular function is a random oracle. Rather the assumption is that the function can be simulated by a random oracle.

It is indeed important to know which particular hash function might be safely used.

I think the major missing piece is that a cryptographic hash function not only needs to be collision-resistant but also one-way. The given example $x \mapsto 3x$ is not one-way.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.