Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
