转载请注明出处:https://www.jzgwind.com/?p=617 by joey

 

已知两个质数p和q,n = p * q,m, e是整数,且m < n,1 < e < φ(n)。φ(n)是n的欧拉函数,d是e对于φ(n)的模反元素。

加密公式为me = c (mod n),证明如下解密公式成立:

cd = m (mod n)。

解:

根据条件,∵ me = c (mod n)

∴ me = c + kn,即c = me – kn。

所以解密公式的证明等同于证明(me – kn)d = m (mod n)。再根据二项式展开定理可知,它等同于证明:

med  =m (mod n)

分两种情况:

(1) 假设m与n互质

∵ d是e对于φ(n)的模反元素

ed = 1 (mod φ(n)),即ed = 1 + h*φ(n)。

因此证明med  =m (mod n)就等同于证明 m1+h*φ(n) = m (mod d),即证明:

mh*φ(n) * m = m (mod n)

根据欧拉定理,如果m与n互质,则 mφ(n) = 1 (mod n)   ,所以 mh*φ(n) * m= m (mod n),证毕。

(2) 假设m与n非互质

因为n = p * q,所以如果m和n不是互质关系,则m要么为kp,要么为kq。

现在以m = kp为例,∵ m < n,n = p * q

k < q(否则 m = kp > pq = n)

∵ q是质数, k与q必然互质,进而又可知kp与q也必然是互质(k与p分别与q互质,kp与q必然是互质),根据欧拉定理:

(kp)φ(q) = 1 mod (q)。

∵ q是质数, φ(q) = q – 1, (kp)q-1 = 1 (mod q)。

因此可以得到[(kp)h(p-1)(q-1) * kp = kp (mod q) ,即 kph*φ(n)+1 = kp (mod q)。

而h*φ(n) + 1 = ed,因此(kp)ed = kp (mod q),将其改写成:

(kp)ed = tq + kp,根据等式可知t必然能被p整除,即 t = t’pq。即等式可以进一步改写成:

(kp)ed = t’pq + kp。 又因为m = kp, n = pq,所以:

med = t’n + m,即 med  = m (mod n),证毕。

参考文献:

阮一峰个人博客——RSA算法原理(二)