solution

Cho khoá công khai RSA $(n, e)$ và bản mã $c = m^e \bmod n$ (với $\gcd(m, n) = 1$, $0 < m < n$). Ánh xạ mã hoá

$E(x) = x^{e} \bmod n$

là một song ánh (permutation) trên tập các số nguyên từ $1$ đến $n-1$ nguyên tố cùng nhau với $n$ (vì $e$ nguyên tố cùng nhau với $\lambda(n)$ — hàm Carmichael của $n$). Vì tập này hữu hạn, lặp lại $E$ nhiều lần từ bất kỳ điểm nào rồi cũng quay vòng trở lại điểm xuất phát.

Tấn công chu trình: không cần biết $p, q$ hay khoá riêng $d$, kẻ tấn công chỉ cần lặp:

$x_0 = c, \quad x_1 = E(x_0), \quad x_2 = E(x_1), \ \ldots$

cho đến khi gặp lại $x_t = x_0 = c$ lần đầu tiên (với $t \ge 1$ nhỏ nhất thoả điều kiện này). Khi đó giá trị ngay trước đó, $x_{t-1}$, chính là bản rõ:

$x_{t-1} = m$

Lý do: vì $E$ song ánh và $x_{t-1}^{e} \bmod n = x_t = c = m^e \bmod n$, nên $x_{t-1}$ phải bằng $m$ (nghiệm căn bậc $e$ duy nhất của $c$ trong tập song ánh).

Với các bộ khoá trong đề bài, chu trình luôn đủ ngắn (tối đa vài nghìn bước) để chạy được trong thời gian giới hạn.

Yêu cầu: Cho $(n, e, c)$, hãy tìm bản rõ $m$ bằng tấn công chu trình (không được phân tích thừa số $n$).

Ví dụ: Với $(n, e, c) = (915749,\ 5,\ 839994)$, kết quả là $m = 863390$.