- A+
所属分类：网络安全
https://blog.csdn.net/doujinlong1/article/details/82051986
主要是欧拉函数，欧拉定理和模反元素，上面这篇文章讲的比较清楚。
我这里要说的是对上面这篇文章的补充，因为里面只讲了如何通过公钥加密和通过私钥解密，但为什么可以用私钥去解密没有讲清楚。
其实RSA的核心就是对于等式 c = m^e mod n 可以找到一个d的值使得c^d mod n = m成立，这样就得到了原文m。d的值为φ(n)的模反元素。即 ed mod φ(n) = 1。
现在d的值也知道了，那么问题就变成证明c^d mod n = m了。
首先，因为c = m^e mod n，把c代入c^d mod n中，得到
c^d mod n = （m^e mod n）^d mod n = m^ed mod n
上面这个变换，用到了二个结论，
- a与b的乘积除以c的余数，等于a，b分别除以c的余数之积（或这个积除以c的余数）。例如，23，16除以5的余数分别是3和1，所以（23×16）除以5的余数等于3×1=3。注意：当余数之积大于除数时，所求余数等于余数之积再除以c的余数。例如，23，19除以5的余数分别是3和4，所以（23×19）除以5的余数等于（3×4）除以5的余数。
- 对n mod多次结果是一样的，这个应该很好理解，比如我用5 mod 3 = 2，再用2 mod 3结果还是2。
根据 ed mod φ(n) = 1 可得 ed= kφ(n) + 1，代入上式中得到，
m^ed nod n = m^(kφ(n) + 1) mod n = (m^kφ(n) mod n) * (m mod n)
这里m mod n的结果就是m，最主要的是计算m^kφ(n) mod n。根据欧拉定理，m^φ(n) mod n =1，而m^kφ(n)其实就是k个m^φ(n)相乘，也就是k个1相乘，也就等于1,所以得出
(m^kφ(n) mod n) * (m mod n) = 1 * m = m
证明完毕。可能有点不好理解，如果有任何疑问，欢迎留言交流。
