Очевидный способ атаковать это (и мы сокращаем $\text{SHA256}(м)$ как $S(м)$ :
Для большого количества сообщений $m_i$, вычислить $S(m_i)$, и учтите это. Если оно гладкое, запишите сообщение и простые множители в таблицу; если он не гладкий, откажитесь от него
Когда вы записали в свою таблицу достаточно сообщений (и простых множителей), выполните исключение в таблице простых множителей, чтобы найти набор сообщений и множителей, в котором все простые числа выбранных сообщений при умножении на множители дают в сумме 0.
Если у нас есть такое произведение (и множитель, соответствующий одному из сообщений, скажем, $S(m_0)$, равно 1), то имеем (где $p_i$ это множитель, который мы присвоили сообщению $я$):
$$S(m_1)^{-p_1} \cdot S(m_2)^{-p_2} \cdot ... \cdot S(m_n)^{-p_n} \equiv S(m_0)$$
Итак, требуйте подписи $m_1, m_2, ..., m_n$; из этого вы можете вывести подпись для $m_0$.
Итак, насколько это осуществимо? Что ж, основная часть логики напоминает то, что делается в квадратичном полевом сите (QFS); размер (256 бит) примерно соответствует тому, что вы получаете, применяя QFS к 512-битному модулю. QFS может реально разложить 512-битные модули; Я делаю вывод, что этот алгоритм также будет выполним.
