solution

Khi sinh khoá RSA, nếu hai số nguyên tố $p, q$ được chọn quá gần nhau ($|p - q|$ nhỏ so với $\sqrt{n}$), môđun $n = p \cdot q$ có thể bị phân tích rất nhanh bằng phương pháp Fermat, bất kể $n$ lớn cỡ nào.

Ý tưởng: vì $p, q$ gần nhau nên $a = \dfrac{p+q}{2}$ và $b = \dfrac{p-q}{2}$ đều là số nguyên, và

$n = p \cdot q = a^2 - b^2$

Thuật toán Fermat: bắt đầu với $a = \lceil \sqrt{n} \rceil$, kiểm tra $a^2 - n$ có phải là số chính phương không; nếu chưa, tăng $a$ lên $1$ và thử lại, cho đến khi tìm được $b = \sqrt{a^2 - n}$ nguyên. Khi đó:

$p = a - b, \qquad q = a + b$

Vì $p, q$ gần nhau nên thuật toán hội tụ chỉ sau rất ít vòng lặp, dù $p, q$ có hàng trăm chữ số.

Sau khi phân tích được $n = p \cdot q$, ta tính $\varphi(n) = (p-1)(q-1)$, khoá riêng $d = e^{-1} \bmod \varphi(n)$, rồi giải mã bản mã $c$:

$m = c^{d} \bmod 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 khoá công khai $(n, e)$ (với $n$ được sinh từ hai số nguyên tố $p, q$ gần nhau) và bản mã $c$, hãy phân tích $n$, khôi phục khoá riêng và giải mã, in ra bản rõ dạng văn bản.

Ví dụ: Với bộ $(n, e, c)$ ở input mẫu, bản rõ khôi phục là "RSAFERMAT".