solution

Hai người dùng dùng chung một môđun RSA $n$ nhưng có số mũ công khai khác nhau $e_1, e_2$ với $\gcd(e_1, e_2) = 1$. Cùng một bản rõ $m$ được gửi mã hóa tới cả hai: $c_1 = m^{e_1} \bmod n$, $c_2 = m^{e_2} \bmod n$.

Kẻ tấn công biết $n, e_1, c_1, e_2, c_2$ (không biết khóa bí mật) có thể khôi phục $m$: dùng thuật toán Euclid mở rộng tìm cặp số nguyên $a, b$ sao cho

$a \cdot e_1 + b \cdot e_2 = 1,$

khi đó $m = c_1^{a} \cdot c_2^{b} \bmod n$. Vì $\gcd(e_1,e_2)=1$ nên chắc chắn tìm được đúng một cặp $(a,b)$ như vậy (theo thuật toán Euclid mở rộng chuẩn); nếu $a$ hoặc $b$ âm, dùng nghịch đảo modulo của $c_1$ hoặc $c_2$ theo $n$ để tính lũy thừa âm.

Cho $n, e_1, c_1, e_2, c_2$ (đảm bảo $\gcd(e_1, e_2) = 1$ và $\gcd(m, n) = 1$), hãy khôi phục $m$.

Ví dụ: $n=3233, e_1=17, c_1=2790, e_2=23, c_2=1320$ thì $m = 65$.