# RSA-FDH Signature Scheme EUF-CMA

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?

• 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. – SEJPM Aug 25 '19 at 16:58
• Interesting... so even if it is a collision resistant hash, one could still forge a message? How is that even possible? – Yusuf Mohamedillahy Aug 25 '19 at 17:22
• 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. – SEJPM Aug 25 '19 at 17:57
• Welcome to Crypto.SE! By collision resistant you mean in case where we restrict $x$ to $\{0,\ldots, N-1\}$? – Marc Ilunga Aug 26 '19 at 18:24

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.