RSA算法实现
1 非对称加密算法
（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。
如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
三位数学家Rivest、Shamir 和 Adleman
2 发明者
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
3 如何生成公钥和密钥?
RSA算法密钥需要生成下面六个数字 (如何生成在👇 的6中解释)：
p = 质数 (最好大于1024位)
q = 质数 (最好大于1024位 , 两个不相等的质数p和q)
n = p和q的乘积 (公开的)
φ(n) = n的欧拉函数
e = 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质 (公开的)
d = e对于φ(n)的模反元素d
上面6个数字会保证一点 : 公钥加密的信息只有私钥解得开
-
所以:
把公开的n成功分解就能获得d,从而破解密钥. -
但是:
下文4会介绍,分解n只能暴力破解,目前声明破解最长的是768位的密钥,那么我们使用至少大于1024位的密钥,还是很安全的, 某种程度是越长越好.
只有这样, 在无法分解质数乘积n时,公钥加密的信息只有私钥解得开
4 破解RSA算法的核心 : 分解质数乘积n
根据已经披露的文献，目前被破解的最长RSA密钥是 768 个二进制位。
12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413
它等于这样两个质数的乘积：
33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917
事实上，这大概是人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。
也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
5 如何获得上面满足要求的6个数字?
1 : 随机选择质数p= 77 和 q = 91 (这里拿小数字测试) ,它们是互质关系
- 质数 : 只能被1和本身整除
- 互质关系 : 如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是
2 : 质数乘积 n = p x q = 77 x 91 = 7007
3 : 计算n的欧拉函数φ(n) = (p-1)(q-1) = 76 x 90 = 6840
4 : 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
这里假设选择 e = 777
5 : 计算e对于φ(n)的模反元素d
- 所谓“模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
这个式子等价于
ed – 1 = kφ(n)
于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。
ex + φ(n)y = 1
已知 e = 777 , φ(n) = 6840，
777 x + 6840 y = 1
这个方程可以用“扩展欧几里得算法”求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。
5 公钥如何加密? 私钥如何解密?
（1）加密要用公钥 (n,e)
假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
所谓”加密”，就是算出下式的c：
me ≡ c (mod n)
爱丽丝的公钥是 (3233, 17)，鲍勃的m假设是65，那么可以算出下面的等式：
6517 ≡ 2790 (mod 3233)
于是，c等于2790，鲍勃就把2790发给了爱丽丝。
（2）解密要用私钥(n,d)
爱丽丝拿到鲍勃发来的2790以后，就用自己的私钥(3233, 2753) 进行解密。可以证明，下面的等式一定成立：
cd ≡ m (mod n)
也就是说，c的d次方除以n的余数为m。现在，c等于2790，私钥是(3233, 2753)，那么，爱丽丝算出
27902753 ≡ 65 (mod 3233)
因此，爱丽丝知道了鲍勃加密前的原文就是65。”加密–解密”的整个过程全部完成。
