一文搞懂 RSA 算法
地球上最重要的算法html
若是没有 RSA 算法，如今的网络世界毫无安全可言，也不可能有如今的网上交易。上一篇文章 ssh 协议为何安全 中的 ssh 协议也是基于 RSA 加密算法才能确保通信是加密的，可靠的。python
1976年之前，全部的加密方法都使用对称加密算法：加密和解密使用同一套规则。例如：甲使用密钥 A 加密，将密文传递给乙，乙仍使用密钥 A 解密。若是密钥 A 在甲传递给乙的过程当中泄露，或者根据已知的几回密文和明文推导出密钥 A，则甲乙之间的通信将毫无秘密。算法
1976年，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，能够在不传递密钥的状况下，完成解密。这被称为 Diffie-Hellman密钥交换算法
假如甲要和乙通信，甲使用公钥 A 加密，将密文传递给乙，乙使用私钥 B 解密获得明文。其中公钥在网络上传递，私钥只有乙本身拥有，不在网络上传递，这样即便知道了公钥 A 也没法解密。反过来通信也同样。只要私钥不泄漏，通讯就是安全的，这就是非对称加密算法。安全
1977年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，能够实现非对称加密。算法用他们三我的的名字命名，叫作 RSA 算法。直到如今，RSA 算法还是最普遍使用的"非对称加密算法"。绝不夸张地说，只要有计算机网络的地方，就有 RSA 算法。微信
下面我以一个简单的例子来描述 RSA 算法。网络
生成密钥对，即公钥和私钥。
第一步：随机找两个质数 P 和 Q ,P 与 Q 越大，越安全。
好比 P = 67 ，Q = 71。计算他们的乘积 n = P * Q = 4757 ，转化为二进为 1001010010101，该加密算法即为 13 位，实际算法是 1024 位 或 2048 位，位数越长，算法越难被破解。ssh
第二步：计算 n 的欧拉函数 φ(n)。
φ(n) 表示在小于等于 n 的正整数之中，与 n 构成互质关系的数的个数。例如：在 1 到 8 之中，与 8 造成互质关系的是一、三、五、7，因此 φ(n) = 4。
若是 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 = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 x 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
即（232个十进制位，768个二进制位），目前被破解的最长RSA密钥就是768位。实际应用中 RSA 的密钥长度为 1024 位，重要场合 2048 位，将来半个世纪不可能破解。
(完）
参考文档：
RSA算法原理（二）（阮一峰）（http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html）
数学之美：谈谈密码学的数学原理（吴军）
若是您对文章感兴趣，请关注微信公众号搜索 somenzz 关注，或扫下方二维码关注
