RSA加密解密算法的证明

1.选择两个质数p,q

2.设n=p*q

3.求出n的欧拉函数f=(p-1)*(q-1)

4.在[2,f)的范围内随机找一个与f互质的数e作为公钥的指数

5.算出私钥指数d，d为公钥指数e对f的一个模反元素，即ed=kf+1(k为正整数)

6.将(n,e)封装成公钥，将(n,d)封装成私钥

1.设被加密的数为m,m为小于n的非负整数

2.算出c=(m^e)%n，则c即为密文

算出(c^d)%n,即为被加密的数m，证明如下。

因为 c=m^e-n*g，其中g为非负整数，

所以  (c^d)%n =[ (m^e-n*g)^d] %n

展开多项式后将n的整数倍的项去除，得到

[(m^e)^d]%n

=[m^(e*d)]%n

=[ m^(k*f+1)]%n

=[m*m^(k*f)]%n

={m*[(m^f)^k]}%n

接下来分三种情况讨论：

第一种情况：m=0或者m=1

则 {m*[(m^f)^k]}%n=m

第二种情况：m>1，且m与n互质

根据 欧拉定理 ，m^f=h*n+1，其中h为正整数

则{m*[(m^f)^k]}%n

={m*[(h*n+1)^k]}%n

={m*[i*n+1]}%n  (其中i为展开指数多项式后合并n的同类项得到的正整数)

=m%n 

=m (因为m<n)

第三种情况：m>1，且m与n不互质

因为n=p*q,且p,q均为质数，则m=j*p或者j*q,其中j为正整数

当m=j*p时,因为m<n,所以m与q互质

（证明：如果m,q不互质，则m含有质因数q，因为p与q互质,所以j含有质因数p,这与m<n矛盾）

根据欧拉定理m^(q-1)=x*q+1，其中x为正整数

则{m*[(m^f)^k]}%n

={m*[(m^[(p-1)*(q-1)])^k]}%n

={m*[m^(q-1)^(p-1)^k]}%n

={j*p*[( x*q+1)^(p-1)^k]}%n

={j*p*[y*q+1]}%n  (其中y为展开指数多项式后合并q的同类项得到的正整数)

=(j*p*y*q+m)%n

=(j*y*n+m)%n

=m

同理当m=j*q时也成立。

证明完毕。

RSA解密正确性证明_国科大网安二班的博客-CSDN博客

https://blog.csdn.net/weixin_46395886/article/details/114700012#:~:text=RSA%E8%A7%A3%E5%AF%86%E6%AD%A3%E7%A1%AE%E6%80%A7%E8%AF%81%E6%98%8E%20%E5%85%88%E6%8F%8F%E8%BF%B0%E4%B8%80%E4%B8%8BRSA%E5%AF%86%E7%A0%81%E4%BD%93%E5%88%B6%EF%BC%9A%20RSA%E5%AF%86%E7%A0%81%E4%BD%93%E5%88%B6%EF%BC%9A%20%E5%A4%A7%E7%B4%A0%E6%95%B0%20p%2Cq%20%EF%BC%8C%E6%A8%A1%E6%95%B0,n%20%3D%20pq%20%EF%BC%8C%E5%8A%A0%E5%AF%86%E6%8C%87%E6%95%B0%20b%20%EF%BC%8C%E8%A7%A3%E5%AF%86%E6%8C%87%E6%95%B0

RSA算法原理-知乎(zhihu.com)

https://zhuanlan.zhihu.com/p/48249182#:~:text=RSA%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86%201%20%EF%BC%881%EF%BC%89%E4%B9%99%E6%96%B9%E7%94%9F%E6%88%90%E4%B8%A4%E6%8A%8A%E5%AF%86%E9%92%A5%20%28%E5%85%AC%E9%92%A5%E5%92%8C%E7%A7%81%E9%92%A5%29%E3%80%82...,2%20%EF%BC%882%EF%BC%89%E7%94%B2%E6%96%B9%E8%8E%B7%E5%8F%96%E4%B9%99%E6%96%B9%E7%9A%84%E5%85%AC%E9%92%A5%EF%BC%8C%E7%84%B6%E5%90%8E%E7%94%A8%E5%AE%83%E5%AF%B9%E4%BF%A1%E6%81%AF%E5%8A%A0%E5%AF%86%E3%80%82%203%20%EF%BC%883%EF%BC%89%E4%B9%99%E6%96%B9%E5%BE%97%E5%88%B0%E5%8A%A0%E5%AF%86%E5%90%8E%E7%9A%84%E4%BF%A1%E6%81%AF%EF%BC%8C%E7%94%A8%E7%A7%81%E9%92%A5%E8%A7%A3%E5%AF%86%E3%80%82