最后,我們來證明,為什么用私鑰解密,一定可以正確地得到m。也就是證明下面這個式子:
> cd?≡ m (mod n)
因為,根據加密規則
> me?≡ 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)
原式得到證明。
(完)