6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ There is already RSA-FDH that this answer covers your needs. $\endgroup$
    – kelalaka
    Commented Mar 1, 2022 at 6:17
  • 4
    $\begingroup$ 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] $\endgroup$
    – fgrieu
    Commented Mar 1, 2022 at 7:03

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ @fgrieu: better??? $\endgroup$
    – poncho
    Commented Mar 2, 2022 at 13:58
  • 1
    $\begingroup$ Yes. But even a mod can't upvote twice! $\endgroup$
    – fgrieu
    Commented Mar 2, 2022 at 17:13

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.