RSA号称地球上最安全的加密算法，https、ssl、网银密码等大多都是基于RSA加密的。那么RSA的基本原理是什么？我们都很好奇，在云计算发达与量子计算崭露头角的今天，RSA加密还是地球最安全的吗？本文为大家以12位演算RSA的加密解密，与暴力破解12位RSA之法。

一、RSA12位加密解密演算

(1) 生成公钥密钥

大家都知道RSA是非对称加密，解密方生成公钥和密钥，公钥公开给加密方加密，密钥留给自己解密是不公开的。

1.随机选两个质数，我们用p、q来代替 （质数的数值越大位数就越多可靠性就越高）
假设我们取了47与59
p = 47
q = 59

2.计算这两个质数的乘积，用n代替
n = 47 x 59 = 2773

n的长度就是密钥长度。2773写成二进制是101011010101，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

3.计算n的欧拉函数φ(n)
欧拉函数公式：φ(n) = (p-1)(q-1)
代入：φ(2773) = (47 - 1) x (59 - 1) = 46 x 58 = 2668

4.随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质
那么我们就在1到2668之间，随机选择了17
e = 17

5.计算e对于φ(n)的模反元素d
模反元素公式: ax ≡ 1 (mod b)
这是欧拉定理推导出来的，若a、b互质则a乘以一个整数除以b的余数是1。这个整数就是a与b的模反元素。
该公式可以写成：ax - b = 1 则 x = (1 + b) / a

代入： d = (1 + φ(n)) / e = (1 + 2668) / 17 = 157
是一个整数，但很多情况下结果不一定是整数，我们为了计算的方便，在公式里追加一个整数k: x = (1 + kb) / a，加上k来乘以b并不影响余数1的结果。

重新代入： d = (1 + kφ(n)) / e = (1 + k x 2668) / 23
即得到一个线性方程
求解的坐标点(k,d)有很多 (1,157)、(18,2825)、(35,5493) ....
我们随机出一个坐标点： (1,157)
即：d = 157

6.将n和e封装成公钥，n和d封装成私钥
即公开的公钥为：n = 2773，e = 17
保密的私钥为：n = 2773，d = 157
就是这样子12位RSA的公私钥生成好了！

(2) 用公钥加密字符串

假设我们加密一个字符"A"
再用数值表示，一般用Unicode或ASCII码表示
转ASCII码十进制为65，我们用m来代替明文，c来代替密文
m = 65
RSA加密公式：m^e ≡ c (mod n)
RSA加密公式由欧拉函数公式与反模元素公式推导出来

代入：c = 65¹⁷ % 2773 = 601
这样密文就出来了！

(3) 用私钥解密密文

RSA解密公式：c^d ≡ m (mod n)
RSA解密公式由欧拉函数公式与反模元素公式推导出来

代入：m = 601¹⁵⁷ % 2773 = 65
这样明文就出来了！

公式的推导过程请参考阮老师的博客：
RSA算法原理（一）
RSA算法原理（二）

二、RSA12位暴力破解

(1) RSA的可靠性在于因数分解的难度

因为p、q、n、φ(n)、e、d这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏

（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。

由此可见推导出d就必须因数分解出p和q
公钥里面有n = 2773
那么暴力破解的方法就是把2773因数分解出两个相乘的质数。

最简单的方法就是遍历穷举质数的乘积：
<pre>
var distNum = 2773;
var numList = [];
var p = 1;
var q = 1;
for(var i = 1; i < 100; i++) {
var isGetResult = false; // 是否找到结果
var isUseful = true; // 是否质数
var isHave = false; // 是否在质数列表中存在
for(var j = 0; j < numList.length; j++) {
if(numList[j] == i) {
isHave = true;
break;
}
}
for(var k = 2; k < i; k++ ) {
if(i % k == 0) {
isUseful = false;
break;
}
}
if(!isHave && isUseful) {
numList.push(i); // 加入质数列表
// 匹配乘积
for(var n = 0; n < numList.length; n++) {
if(i != numList[n] && i * numList[n] == distNum) {
p = i;
q = numList[n];
isGetResult = true;
break;
}
}
}
console.log(JSON.stringify(numList));
if(isGetResult) {
console.log('p = ' + p);
console.log('q = ' + q);
break;
}
}
</pre>

运行结果：

12位的RSA加密瞬间破解出来了！

三、结语

RSA加密的可靠性是基于因数分解的计算难度，但随着量子计算、云计算的发达，现在用的1024位RSA甚至2048位RSA都面临着挑战，据说40个量子比特位相当于一台超级计算机。

参考资料：
RSA算法原理（一）
RSA算法原理（二）

您的意见是我改善的东西，欢迎评论提建议，如果对您有帮助，请点个赞，谢谢~~
菲麦前端专题，汇聚前端好文，邀您关注！