# RSA的人生故事
RSA加密算法是一种非对称加密算法。RSA广泛应用于公钥加密和电子商务。RSA由罗纳德李韦斯特(罗恩
瑞文斯特)、阿迪萨莫尔和伦纳德阿德曼
阿德曼)一起提出的。当时，他们三人都在麻省理工学院工作。RSA是他们三个姓氏首字母的组合。
RSA算法是第一个既能用于加密又能用于数字签名的算法，而且易于理解和操作。RSA是研究最广泛的公钥算法。经过30多年各种攻击的考验，逐渐被人们所接受。截至2017年，RSA被广泛认为是最好的公钥方案之一，一度被称为地球上最重要的加密算法。
作为一种非对称加密算法，RSA的特点是当数据在网络中传输时，用于加密数据的密钥不需要与数据一起传输。因此，这降低了密钥泄露的可能性。当不允许加密方解密数据时，RSA也很有用。加密方使用一个密钥，称为公钥，解密方使用另一个密钥，称为私钥，需要保密。
RSA被认为非常安全，但计算速度比DES慢很多。和DES一样，它的安全性从来没有被证明过，但是要突破RSA算法中涉及的大数(至少200位大数)的因式分解是极其困难的。因此，由于缺乏解决大数因式分解的有效方法，可以推断目前还没有破解RSA的有效方法。
#在解释RSA之前，让我们先了解几个概念。
互质关系：
如果两个正整数除了1没有公因数，我们称这两个数互质。比如15和32没有公因数，所以是质数关系。这说明素数也可以构成素数关系。
关于质数关系，不难得出以下结论：
1.任何两个质数形成质数关系，如13和61。
2.一个数是质数，只要另一个数不是前者的倍数，它们就形成质数关系，比如3和10。
3.如果两个数中较大的一个是质数，那么它们就形成了质数关系，比如97和57。
4\.1和任何自然数都是质数关系，比如1和99。
If 5\。p是大于1的整数，那么p和p-1形成素数关系，比如57和56。
6\.p是大于1的奇数，那么p和p-2形成素数关系，比如17和15。
欧拉函数：
用来解决_给定任意正整数n，有多少小于或等于n的正整数与n形成素关系？(比如1到8之间，有多少个数字与8形成质数关系？)_
这个问题。
具体的推导过程，本文就不多说了。如果我感兴趣，我会自己去看一看。欧拉函数的一般公式是：
欧拉函数的普适公式
欧拉定理：
欧拉函数的效用在于欧拉定理。“欧拉定理”指的是
如果n，a是正整数，n，a是素数，则满足以下公式
欧拉定理可以大大简化一些运算。
费马小定理：
a是不能被素数P整除的正整数，那么就有了(p-1) 1 (mod p)
让我们从一个基本的例子开始。A=3，n=
这两个数字是质数。小于5的正整数中有1、2、3、4个5的素数，所以(5)=4(详见【欧拉函数】)。计算： a {(n)}=3 ^ 4
=81，81=80 1 1 (mod 5)。与定理的结果一致。
这个定理可以用来简化功率的模运算。例如，计算7 {222}的个位数实际上就是求7 {222}的余数除以10。7和10[[质数]]，(10)=4。欧拉定理知道7 4 1 (mod
10)。所以7 { 222 }=(7 4)55 *(7 2)1 { 55 } * 7 2499(mod 10)。
懂欧拉定理，就能懂RSA。
模反元素：
如果两个正整数A和N都是素数，那么我们就可以求出整数B，这样ab-1被N等分，或者ab除以N的余数是1。此时，B被称为a的“反模元素”。
例如，如果3和11是素数，那么3的模逆元素是4，因为(3 4)-1可以被11整除。显然，反模元素不止一个，4的整数倍加上减11就是3的反模元素。
{.-18,-7,4,15,26,}，也就是说，如果B是A的模逆元素，那么b kn
都是a的模反元素。欧拉定理可以用来证明模反元素必然存在。
# RSA密钥的生成
生成密钥对，即公钥和私钥
第一步：随机找两个质数 P 和 Q ,P 与 Q 越大，越安全。
比如 P = 67 ，Q = 71。计算他们的乘积 n = P * Q = 4757 ，转化为二进为 1001010010101，该加密算法即为 13
位，实际算法是 1024 位 或 2048 位，位数越长，算法越难被破解。
第二步：计算 n 的欧拉函数 φ(n)。
如果 n = P * Q，P 与 Q 均为质数，则 φ(n) = φ(P * Q)= φ(P - 1)φ(Q - 1) = (P - 1)(Q - 1) 。
本例中 φ(n) = 66 * 70 = 4620，这里记为 m， m = φ(n) = 4620
第三步：随机选择一个整数 e，条件是1 < e < m，且 e 与 m 互质。
公约数只有 1 的两个整数，叫做互质整数，这里我们随机选择 e = 101
请注意不要选择 4619，如果选这个，则公钥和私钥将变得相同。
第四步：有一个整数 d，可以使得 e*d 除以 m 的余数为 1。
即找一个整数 d，使得 (e * d ) % m = 1。
等价于 e * d - 1 = y * m ( y 为整数）
找到 d ，实质就是对下面二元一次方程求解。
e * x - m * y =1 ，其中 e = 101，m = 4620
101x - 4620y =1
这个方程可以用"扩展欧几里得算法"求解，此处省略具体过程。 总之算出一组整数解（x，y ）= （ 1601，35），即 d = 1601。
到此密钥对生成完毕。不同的 e 生成不同的 d，因此可以生成多个密钥对。
本例中公钥为 （n，e) = (4757 , 101)，私钥为 （n，d) = (4757 ，1601) ，仅（n，e) = (4757 , 101)
是公开的，其余数字均不公开。可以想像如果只有 n 和 e，如何推导出 d，目前只能靠暴力破解，位数越长，暴力破解的时间越长。
加密生成密文
比如甲向乙发送汉字“中”，就要使用乙的公钥加密汉字 "中"， 以 utf-8 方式编码为 [e4 b8 ad]，转为 10 进制为
[228,184,173]。要想使用公钥（n，e) = (4757 , 101)加密，要求 被加密的数字必须小于
n，被加密的数字必须是整数，字符串可以取 ascii 值或unicode值 ，因此将“中”字折为三个字节
[228,184,173]，分别对三个字节加密。
假设 a 为明文，b 为密文，则按下列公式计算出 b
a^e % n = b
计算 [228,184,173]的密文：
228^101 % 4757 = 4296
184^101 % 4757 = 2458
173^101 % 4757 = 3263
即 [228,184,173]加密后得到密文 [4296，2458，3263] ，如果没有私钥 d ,神仙也无法从 [4296，2458，3263]中恢复
[228,184,173]。
解密生成明文
乙收到密文 [4296，2458，3263]，并用自己的私钥（n，d) = (4757 ，1601) 解密。解密公式如下：
假设 a 为明文，b 为密文，则按下列公式计算出 a
a^d % n = b
密文 [4296，2458，3263]的明文如下：
4296^1601% 4757 = 228
2458^1601% 4757 = 184
3263^1601% 4757 = 173
即密文 [4296，2458，3263] 解密后得到 [228,184,173]
将[228,184,173] 再按 utf-8 解码为汉字 "中"，至此解密完毕。
加密和解密的过程使用了费尔马小定理的两种等价的描述
最后，问题来了，有没有可能在已知 （n，e) 的情况下，推导出 d。
根据以上密钥生成过程：
如果想知道 d 需要知道欧拉函数 φ(n)
如果想知道欧拉函数 φ(n) 需要知道 P 和 Q
要知道 P 和 Q 需要对 n 进行因数分解。
对于本例中的 4757
你可以轻松进行因数分解，但对于大整数的因数分解，是一件很困难的事情，目前除了暴力破解，还没有更好的办法，如果以目前的计算速度，破解需要50年以上，则这个算法就是安全的。
维基百科这样描述：
> "对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
> 假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
> 只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。"
目前已经破解的最大整数：
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413=33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489x36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
即（232个十进制位，768个二进制位），目前被破解的最长RSA密钥就是768位。实际应用中 RSA 的密钥长度为 1024 位，重要场合 2048
位，未来半个世纪不可能破解。
# Java中开源工具
RSA到这里就介绍完了，喜欢就点个关注哦，谢谢你们！
