solution

Một hệ thống RSA cẩu thả dùng chung một môđun $n$ cho hai người dùng khác nhau, chỉ khác số mũ công khai: người A có khoá $(n, e_1)$, người B có khoá $(n, e_2)$, với $\gcd(e_1, e_2) = 1$.

Cùng một bản rõ $m$ ($0 < m < n$, $\gcd(m, n) = 1$) được mã hoá gửi cho cả hai:

$c_1 = m^{e_1} \bmod n, \qquad c_2 = m^{e_2} \bmod n$

Vì $\gcd(e_1, e_2) = 1$, dùng thuật toán Euclid mở rộng ta tìm được $u, v \in \mathbb{Z}$ sao cho

$u \cdot e_1 + v \cdot e_2 = 1$

Khi đó, không cần biết khoá riêng, kẻ tấn công vẫn khôi phục được $m$ nhờ:

$c_1^{u} \cdot c_2^{v} \equiv m^{u e_1 + v e_2} \equiv m^{1} \equiv m \pmod n$

(nếu $u$ hoặc $v$ âm, thay $c_i^{u}$ bằng $(c_i^{-1} \bmod n)^{-u}$, với $c_i^{-1}$ là nghịch đảo modulo $n$).

Bản rõ $m$, khi biểu diễn thành chuỗi byte lớn-đứng-trước (big-endian) với độ dài tối thiểu (tức số byte $= \lceil (\text{số bit của } m) / 8 \rceil$), chính là một chuỗi văn bản UTF-8 hợp lệ.

Yêu cầu: Cho $n, e_1, c_1, e_2, c_2$, hãy khôi phục lại bản rõ $m$ và in ra dưới dạng chuỗi văn bản gốc.

Ví dụ: với bộ số cho trước mô tả ở trên (xem input mẫu), bản rõ khôi phục được là văn bản "CTF{RSA}".