九、私钥解密的证明
最后更新于：2022-04-01 21:43:03
最后，我们来证明，为什么用私钥解密，一定可以正确地得到m。也就是证明下面这个式子：
> cd ≡ m (mod n)
因为，根据加密规则
> ｍe ≡ c (mod n)
于是，c可以写成下面的形式：
> c = me - kn
将c代入要我们要证明的那个解密规则：
> (me - kn)d ≡ m (mod n)
它等同于求证
> med ≡ m (mod n)
由于
> ed ≡ 1 (mod φ(n))
所以
> ed = hφ(n)+1
将ed代入：
> mhφ(n)+1 ≡ m (mod n)
接下来，分成两种情况证明上面这个式子。
（1）m与n互质。
根据欧拉定理，此时
> mφ(n) ≡ 1 (mod n)
得到
> (mφ(n))h × m ≡ m (mod n)
原式得到证明。
（2）m与n不是互质关系。
此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。
以 m = kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立：
> (kp)q-1 ≡ 1 (mod q)
进一步得到
> [(kp)q-1]h(p-1) × kp ≡ kp (mod q)
即
> (kp)ed ≡ kp (mod q)
将它改写成下面的等式
> (kp)ed = tq + kp
这时t必然能被p整除，即 t=t'p
> (kp)ed = t'pq + kp
因为 m=kp，n=pq，所以
> med ≡ m (mod n)
原式得到证明。
（完）
';