solution

Một hệ thống sinh khóa RSA yếu chọn $p, q$ đều không vượt quá $10^6$, khiến mô-đun $n = pq$ có thể bị phân tích thừa số nhanh bằng phương pháp chia thử. Giả sử kẻ tấn công chỉ biết khóa công khai $(n, e)$ và một bản mã $c$ (không biết $p, q$ hay $d$). Hãy khôi phục bản rõ $m$ bằng cách:

1. Phân tích $n = p \times q$ với $p \le q \le 10^6$ (đảm bảo $n$ luôn có đúng một cách phân tích thành hai thừa số nguyên tố phân biệt hoặc bằng nhau thỏa điều kiện trên).
2. Tính $\varphi(n) = (p-1)(q-1)$ rồi số mũ bí mật $d = e^{-1} \bmod \varphi(n)$.
3. Giải mã $m = c^d \bmod n$.

Ví dụ: $n = 3233$ ($= 61 \times 53$), $e = 17$, $c = 2790$ $\Rightarrow$ phân tích được $p=53, q=61$, $\varphi(n)=3120$, $d=2753$, và $m = 2790^{2753} \bmod 3233 = 65$.