九、私钥解密的证明

最后更新于:2022-04-01 21:43:03

最后,我们来证明,为什么用私钥解密,一定可以正确地得到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) 原式得到证明。 (完)
';