RSA的身世

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的三十多年里，经历了各种攻击的考验，逐渐为人们接受，截止2017年被普遍认为是最优秀的公钥方案之一，曾被人誉为地球上最重要的加密算法。

RSA作为一种非对称的加密算法，其中很重要的一特点是当数据在网络中传输时，用来加密数据的密钥并不需要也和数据一起传送。因此，这就减少了密钥泄露的可能性。RSA在不允许加密方解密数据时也很有用，加密的一方使用一个密钥，称为公钥，解密的一方使用另一个密钥，称为私钥，私钥需要保持其私有性。

RSA被认为是非常安全的，不过计算速度要比DES慢很多。同DES一样，其安全性也从未被证明过，但想攻破RSA算法涉及的大数（至少200位的大数）的因子分解是一个极其困难的问题。所以，由于缺乏解决大数的因子分解的有效方法，因此，可以推测出目前没有有效的办法可以破解RSA。

在讲解RSA之前，我们先了解几个概念

互质关系：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

关于互质关系，不难得到以下结论：

　 1. 任意两个质数构成互质关系，比如13和61。

　　2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

　　3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

　　4. 1和任意一个自然数是都是互质关系，比如1和99。

　　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整除的正整数，则有a^(p-1) ≡ 1 (mod p)

首先看一个基本的例子。令a = 3，n = 5，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以φ(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^2Ξ49Ξ9 (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到这里就介绍完了，喜欢就点个关注哦，谢谢你们！