RSA.jpg

没有公式推导，非常简单，只要小学数学水平就能看的懂的RSA加解密以及破译的过程讲解。真的很简单。

一、求取公钥以及私钥的过程

1.寻找两个大质数 p,q
2.计算 n = p * q
3.计算欧拉函数 f(n) = (p - 1) * (q - 1)
4.求公钥为 e,e 满足如下条件
(1)e 为 1 < e < f(n) 中的任意一个整数
(2)e 与 f(n) 互为质数
最后 (n , e) 共同组成公钥。
5.求私钥 d,d 满足如下条件
(e * d) mod f(n) = 1
最后 (n,d) 共同组成私钥

二、加解密过程，设 m 为原文，c 为密文

1.加密
m 的 e 次幂 mod n = c
2.解密
c 的 d 次幂 mod n = m

三、举个破例子

1.设 p = 3,q = 5
2.计算 n = 3 * 5 = 15
3.计算 f(n) = 2 * 4 = 8
4.根据第一点第4小点，e 可以取的值有3，5，7。这里取 3 好了
5.根据第一点第5小点，d = 11，因为 3 * 11 mod 8 = 1
6.加密：设 m = 2，则 c = 2 的 3 次幂 mod 15 = 8
7.解密：c 的 11 次幂 mod 15 = 2 (找个科学计算器算，不然很恼火)

四、破译的过程

破译的过程其实就是已知 (n,e) 根据求取公钥以及私钥的过程逆向求 (n,d)。
还是上面的破例子，已经 n = 15,那么就要分解质因子，15 的质因子为 3，5。然后根据第一点的前 4 个小步骤发现正好可以求得 e，再求 d 就简单了。
好简单，秒解，一眼就看出来。呃，但是交给计算机来算可没这么快了，而且这才 2 位，换成 1024 位再分解一下试试？