RSA解密的正确性

由于 $ed \equiv 1 \pmod{\phi(n)}$,根据模同余的定义,存在非负整数 $k$ 使得 $ed = 1 + k\phi(n)$ 成立。

情形一:$\gcd(m,n)=1$。由欧拉定理有 $m^{\phi(n)} \equiv 1 \pmod n$,将两边同时 $k$ 次幂再乘以 $m$,得到 $m^{ed} = m \cdot (m^{\phi(n)})^{k} \equiv m \cdot 1^{k} \equiv m \pmod n$。

情形二:$\gcd(m,n) \ne 1$。由于 $n = pq$,这意味着 $p$ 整除 $m$ 或者 $q$ 整除 $m$(不会同时成立,因为 $m$ 小于 $n$)。在模 $p$ 下考虑:若 $p$ 整除 $m$,则 $m$ 与 $m^{ed}$ 在模 $p$ 下都同余于 $0$;否则 $\gcd(m,p)=1$,由费马小定理有 $m^{p-1} \equiv 1 \pmod p$,又因为 $(p-1)$ 整除 $\phi(n)$,与情形一相同的计算给出 $m^{ed} \equiv m \pmod p$。在模 $q$ 下的论证完全相同,给出 $m^{ed} \equiv m \pmod q$。

由中国剩余定理,分别在模 $p$ 和模 $q$ 下成立的同余式,在其乘积 $n=pq$ 下也成立,因此 $(m^e)^d \equiv m \pmod n$ 对每一个消息 $m$ 都成立,而不仅仅是那些与 $n$ 互素的消息。