# RSA Signature using SHA-256 is secure?

Is following RSA signature scheme secure against forgery and prevents breaking text book RSA?

$$y = \operatorname{SHA-256}(m)$$ $$s = y^d\bmod N$$

where $$m$$ is message of arbitrary length, $$y$$ is the 256-bit hash of $$m$$ computed using SHA-256, $$d$$ is RSA private key, and $$N$$ is an RSA modulus with length 2048 or higher?

• SHA-256 is not wide enough that the security argument of RSA-FDH applies. On the contrary, the Desmedt and Odlyzko attack applies to some degree to break EUF-CMA. With how much work, well, that requires care... See this [link fixed]
– fgrieu
Mar 1, 2022 at 7:03

An obvious way to attack this (and we're shorten $$\text{SHA256}(m)$$ as $$S(m)$$ :

• For a large number of messages $$m_i$$, compute $$S(m_i)$$, and factor that. If it is smooth, record the message and the prime factors in a table; if it is not smooth, reject it

• When you have recorded enough messages (and prime factors) in your table, do elimination on the prime factor table to find a set of messages and factors where all the primes of the selected messages, when multiplied by the factors, all sum to 0.

If we have such a product (and the multiplier corresponding to one of the messages, say, $$S(m_0)$$, is 1), then we have (where $$p_i$$ is the multiplier we assigned to message $$i$$):

$$S(m_1)^{-p_1} \cdot S(m_2)^{-p_2} \cdot ... \cdot S(m_n)^{-p_n} \equiv S(m_0)$$

So, ask for the signatures of $$m_1, m_2, ..., m_n$$; from that, you can deduce the signature for $$m_0$$.

So, how feasible is this? Well, the bulk of the logic is reminiscent of what is done in the Quadratic Field Sieve (QFS); the size (256 bits) is about what you get when you apply QFS to a 512 bit modulus. QFS can factor 512 bit modulii feasibly; I conclude that this algorithm would also be feasible.

• @fgrieu: better??? Mar 2, 2022 at 13:58
• Yes. But even a mod can't upvote twice!
– fgrieu
Mar 2, 2022 at 17:13