solution

Cùng một bản rõ $m$ được mã hóa gửi cho ba người nhận khác nhau, dùng chung số mũ công khai nhỏ $e = 3$ nhưng ba môđun khác nhau và đôi một nguyên tố cùng nhau $n_1, n_2, n_3$:

$c_i = m^3 \bmod n_i, \quad i = 1,2,3.$

Nếu $m^3 < n_1 n_2 n_3$ (đúng khi $m$ đủ nhỏ so với các $n_i$), kẻ tấn công không cần biết bất kỳ khóa bí mật nào vẫn khôi phục được $m$ theo tấn công quảng bá Håstad:

1. Dùng Định lý số dư Trung Hoa (CRT) với hệ phương trình $x \equiv c_i \pmod{n_i}$ để tìm nghiệm duy nhất $C$ với $0 \le C < n_1 n_2 n_3$. Vì $\gcd(m^3, n_1n_2n_3)$ không ảnh hưởng tính duy nhất nghiệm CRT và $m^3 < n_1n_2n_3$, ta có chính xác $C = m^3$ (không chỉ đồng dư).
2. Lấy căn bậc ba nguyên của $C$ để thu được $m$.

Cho $n_1, c_1, n_2, c_2, n_3, c_3$ (đảm bảo $n_1, n_2, n_3$ đôi một nguyên tố cùng nhau và tồn tại $m$ nguyên không âm thỏa $c_i = m^3 \bmod n_i$ với mọi $i$, đồng thời $m^3 < n_1 n_2 n_3$), hãy khôi phục $m$.

Ví dụ: $n_1=1760553551, c_1=74088, n_2=3267902051, c_2=74088, n_3=3659333159, c_3=74088$ thì $m = 42$ (vì $42^3 = 74088$ nhỏ hơn cả ba môđun nên không bị rút gọn).