Tính đúng đắn của giải mã RSA

Vì $ed \equiv 1 \pmod{\phi(n)}$, theo định nghĩa đồng dư modulo tồn tại một số nguyên không âm $k$ với $ed = 1 + k\phi(n)$.

Trường hợp 1: $\gcd(m,n)=1$. Định lý Euler cho $m^{\phi(n)} \equiv 1 \pmod n$, nên nâng cả hai vế lên luỹ thừa $k$ rồi nhân với $m$ cho $m^{ed} = m \cdot (m^{\phi(n)})^{k} \equiv m \cdot 1^{k} \equiv m \pmod n$.

Trường hợp 2: $\gcd(m,n) \ne 1$. Vì $n = pq$, điều này nghĩa là $p$ chia hết $m$ hoặc $q$ chia hết $m$ (không thể cả hai, vì $m$ nhỏ hơn $n$). Xét theo modulo $p$: nếu $p$ chia hết $m$ thì cả $m$ và $m^{ed}$ đều đồng dư $0$ theo modulo $p$; nếu không thì $\gcd(m,p)=1$ và định lý nhỏ Fermat cho $m^{p-1} \equiv 1 \pmod p$, và vì $(p-1)$ chia hết $\phi(n)$ nên cùng tính toán như Trường hợp 1 cho $m^{ed} \equiv m \pmod p$. Lập luận giống hệt theo modulo $q$ cho $m^{ed} \equiv m \pmod q$.

Theo định lý số dư Trung Hoa, một đồng dư đúng theo modulo $p$ và theo modulo $q$ riêng biệt thì cũng đúng theo modulo tích của chúng $n=pq$, nên $(m^e)^d \equiv m \pmod n$ đúng với mọi thông điệp $m$, không chỉ những thông điệp nguyên tố cùng nhau với $n$.