solution

Một người gửi dùng số mũ công khai nhỏ $e = 3$ (để mã hoá nhanh) và gửi cùng một bản rõ $m$ cho ba người nhận khác nhau, mỗi người có một môđun RSA riêng $n_1, n_2, n_3$ (đôi một nguyên tố cùng nhau, tức $\gcd(n_i, n_j) = 1$ với $i \ne j$), nhưng dùng chung $e = 3$:

$c_1 = m^3 \bmod n_1, \qquad c_2 = m^3 \bmod n_2, \qquad c_3 = m^3 \bmod n_3$

với $0 < m < \min(n_1, n_2, n_3)$.

Tấn công quảng bá Håstad: Kẻ nghe lén thu được cả ba $(n_i, c_i)$ nhưng không biết khoá riêng nào. Áp dụng Định lý phần dư Trung Hoa (CRT) cho hệ:

$x \equiv c_1 \pmod{n_1}, \qquad x \equiv c_2 \pmod{n_2}, \qquad x \equiv c_3 \pmod{n_3}$

ta tìm được nghiệm duy nhất $x$ với $0 \le x < N = n_1 n_2 n_3$. Vì $m < \min(n_i)$ nên $m^3 < \min(n_i)^3 \le N$, suy ra

$x = m^3 \pmod N \ \text{ và đồng thời } \ x = m^3 \text{ (đẳng thức trên số nguyên, không chỉ modulo)}$

Do đó chỉ cần khai căn bậc ba đúng (chính xác tuyệt đối trên số nguyên) của $x$ là ra $m$ — hoàn toàn không cần phá khoá riêng của bất kỳ ai. (Lưu ý: không dùng x ** (1/3) vì sai số dấu phẩy động với số lớn; cần cài đặt thuật toán khai căn bậc ba nguyên, ví dụ bằng tìm kiếm nhị phân.)

$m$, biểu diễn thành chuỗi byte lớn-đứng-trước với độ dài tối thiểu, là một chuỗi văn bản UTF-8.

Yêu cầu: Cho ba cặp $(n_1, c_1), (n_2, c_2), (n_3, c_3)$, hãy khôi phục và in ra bản rõ $m$ dạng văn bản.

Ví dụ: Với input mẫu, bản rõ khôi phục là "BROADCAST".