Chữ ký RSA sử dụng SHA-256 có an toàn không?

Một cách rõ ràng để tấn công điều này (và chúng tôi đang rút ngắn $\text{SHA256}(m)$ như $S(m)$ :

• Đối với một số lượng lớn các tin nhắn $m_i$, tính toán $S(m_i)$, và yếu tố đó. Nếu trơn thì ghi tin và các thừa số nguyên tố vào bảng; nếu nó không trơn tru, từ chối nó

• Khi bạn đã ghi đủ thông báo (và các thừa số nguyên tố) trong bảng của mình, hãy loại bỏ trên bảng thừa số nguyên tố để tìm một tập hợp các thông báo và thừa số trong đó tất cả các số nguyên tố của các thông báo đã chọn, khi nhân với các thừa số, đều có tổng bằng 0.

Nếu chúng ta có một sản phẩm như vậy (và hệ số nhân tương ứng với một trong các thông báo, giả sử, $S(m_0)$, là 1) thì ta có (trong đó $p_i$ là số nhân chúng tôi đã gán cho tin nhắn $i$):

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

Vì vậy, xin chữ ký của $m_1, m_2, ..., m_n$; từ đó, bạn có thể suy ra chữ ký cho $m_0$.

Vì vậy, làm thế nào khả thi là điều này? Chà, phần lớn logic gợi nhớ đến những gì được thực hiện trong Sàng trường bậc hai (QFS); kích thước (256 bit) là khoảng những gì bạn nhận được khi áp dụng QFS cho mô-đun 512 bit. QFS có thể tính toán mô đun 512 bit một cách khả thi; Tôi kết luận rằng thuật toán này cũng sẽ khả thi.