九、私鑰解密的證明

最后，我們來證明，為什么用私鑰解密，一定可以正確地得到m。也就是證明下面這個式子：

　　cd?≡ m (mod n)

因為，根據(jù)加密規(guī)則

　?。韊?≡ c (mod n)

于是，c可以寫成下面的形式：

　　c = me?- kn

將c代入要我們要證明的那個解密規(guī)則：

　　(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互質(zhì)。

根據(jù)歐拉定理，此時

　　mφ(n)?≡ 1 (mod n)

得到

　　(mφ(n))h?× m ≡ m (mod n)

原式得到證明。

（2）m與n不是互質(zhì)關系。

此時，由于n等于質(zhì)數(shù)p和q的乘積，所以m必然等于kp或kq。

以 m = kp為例，考慮到這時k與q必然互質(zhì)，則根據(jù)歐拉定理，下面的式子成立：

　　(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)

原式得到證明。

（完）