solution

Để ký nhanh hơn, nhiều hệ thống RSA tính chữ ký bằng Định lý phần dư Trung Hoa (CRT): với $n = p \cdot q$, thay vì tính trực tiếp $s = m^{d} \bmod n$, người ta tính hai phần riêng trên $p$ và $q$

$s_p = m^{d \bmod (p-1)} \bmod p, \qquad s_q = m^{d \bmod (q-1)} \bmod q$

rồi ghép lại bằng CRT để được $s \equiv m^d \pmod n$ (nhanh hơn nhiều vì $p, q$ chỉ bằng nửa số bit của $n$).

Lỗi Bellcore (fault attack): Nếu do lỗi phần cứng/nhiễu điện, một trong hai phép tính CRT bị sai (giả sử $s_q$ bị tính sai thành $s_q'$, còn $s_p$ vẫn đúng), chữ ký ghép ra $s'$ sẽ thoả:

$s' \equiv s_p \equiv s \pmod p \qquad \text{nhưng} \qquad s' \not\equiv s \pmod q$

Nghĩa là $p \mid (s - s')$ nhưng $q \nmid (s - s')$. Do đó nếu kẻ tấn công có được một chữ ký đúng $s$ và một chữ ký lỗi $s'$ của cùng một thông điệp (cùng khoá), hắn phân tích được $n$ ngay lập tức mà không cần bất kỳ thuật toán phân tích thừa số nào:

$p = \gcd(|s - s'|,\ n), \qquad q = n / p$

Từ $p, q$ và số mũ công khai $e$, tính được $\varphi(n) = (p-1)(q-1)$ và khoá riêng $d = e^{-1} \bmod \varphi(n)$.

Yêu cầu: Cho $n$, $e$, chữ ký đúng $s$ và chữ ký lỗi $s'$ (cùng ký một thông điệp, lỗi xảy ra ở nhánh CRT theo $q$), hãy tìm lại $p, q$ (với $p < q$) và khoá riêng $d$.

Ví dụ: Với $(n, e, s, s')$ ở input mẫu, kết quả in ra là ba số $p\ q\ d$ thoả $p \cdot q = n$ và $e \cdot d \equiv 1 \pmod{(p-1)(q-1)}$.