rsa加密破解（Rsa加解密）
rsa加密破解（Rsa加解密）
RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。两者之间有数学相关，该加密算法的原理就是对一极大整数做因数分解的困难性来保证安全性。通常个人保存私钥，公钥是公开的（可能同时多人持有）。
加密和签名都是为了安全性考虑，但略有不同。常有人问加密和签名是用私钥还是公钥？其实都是对加密和签名的作用有所混淆。简单的说，加密是为了防止信息被泄露，而签名是为了防止信息被篡改。这里举2个例子说明。
RSA的加密过程如下：
RSA签名的过程如下：
总结：公钥加密、私钥解密、私钥签名、公钥验签。
RSA加密对明文的长度有所限制，规定需加密的明文最大长度=密钥长度-11（单位是字节，即byte），所以在加密和解密的过程中需要分块进行。而密钥默认是1024位，即1024位/8位-11=128-11=117字节。所以默认加密前的明文最大长度117字节，解密密文最大长度为128字。那么为啥两者相差11字节呢？是因为RSA加密使用到了填充模式（padding），即内容不足117字节时会自动填满，用到填充模式自然会占用一定的字节，而且这部分字节也是参与加密的。
大家都知道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的公私钥生成好了！
假设我们加密一个字符"A"
再用数值表示，一般用Unicode或ASCII码表示
转ASCII码十进制为65，我们用m来代替明文，c来代替密文
m = 65
RSA加密公式：m e ≡ c (mod n)
RSA加密公式由欧拉函数公式与反模元素公式推导出来
代入：c = 65 17 % 2773 = 601
这样密文就出来了！
RSA解密公式：c d ≡ m (mod n)
RSA解密公式由欧拉函数公式与反模元素公式推导出来
代入：m = 601 157 % 2773 = 65
这样明文就出来了！
因为p、q、n、φ(n)、e、d这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏
由此可见推导出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
运行结果：
RSA加密的可靠性是基于因数分解的计算难度，但随着量子计算、云计算的发达，现在用的1024位RSA甚至2048位RSA都面临着挑战，据说40个量子比特位相当于一台超级计算机。
您的意见是我改善的东西，欢迎评论提建议，如果对您有帮助，请点个赞，谢谢~~
菲麦前端专题，汇聚前端好文，邀您关注！
如果需要理解RSA的加密原理，需要理解以下理论：
等同于求一元二次方程 23 * d + 192 * y = 1
可以求得其中一解为（d=167，y=-20）
至此就完成了所有的计算
对于上述例子的到公钥（221，23）和私钥（221，167）
在上述的计算过程中一共用到了
上面用到的数中只有公钥部分是公开的，即（221，23）。那么我们是否可以通过公钥来推到出私钥部分，即已知n和e，推到出d？
（1）ed 1(mod (n))，只有知道 (n)才能解出d
（2） (n)= (p) (q)= (p-1) (q-1)，只有知道p和q才能得到 (n)
（3）n=p q，就需要对n进行因式分解
那么如果可以对n因式分解就可以求出d，也就意味着私匙被破解
那么RSA加密的可靠性就在于对n因式分解的难度，而现在对一个整数n做因式分解并没有巧妙的算法，只有通过暴力破解计算。在实际应用中的n取值通常在1024位以上，而公开已知的可因式分解的最大数为768位。所以现阶段来说RSA加密是可靠的。
现在我们就可以进行加密和解密了
我们使用上面生成的公钥（221，23）来加密。如果我们需要加密的信息是m（ m必须为整数并且m要小于n ），m取56，可以用以下公式求出加密串c：
c (mod n)
10 (mod 221)
可以求出加密后的结果c为10
密钥为（221，167），加密结果c=10，可以使用以下公式求出被加密的信息
m (mod n) 即加密结果的d次方除以n的余数为m
56 (mod 221)
RSA加密属于块加密算法，总是在一个固定长度的块上进行操作。如果被加密的字符串过长，则需要对字符串进行切割，如果字符串过短则需要进行填充。
以下主介绍一下RSA_PKCS1_PADDING填充模式以及RSA_NO_PADDING模式
此填充模式是最常用的填充模式，在此填充模式下输入的长度受加密钥的长度限制，输入的最大长度为加密钥的位数k-11。如果公钥的长度为1024位即128字节，那么输入的长度最多为128-11=117字节。如果长度小于117就需要填充。如果输入T的长度为55字节，填充后的块为EM，则EM格式如下：
EM= 0x00 || BT || PS || 0x00 || T
在此填充模式下，输入的长度最多和RSA公钥长度一样长，如果小于公钥长度则会在前面填充0x00。如果公钥长度是128字节，输入T的长度为55字节，填充后的块为EM，则EM格式如下：
EM=P || T
参考：
rsa加密算法如下：
算法原理：
RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥
算法描述：
RSA算法的具体描述如下：
（1）任意选取两个不同的大素数p和q计算乘积
（2）任意选取一个大整数e，满足整数e用做加密钥（注意：e的选取是很容易的，例如，所有大于p和q的素数都可用）
（3）确定的解密钥d，满足 是一个任意的整数；所以，若知道e和，则很容易计算出d ；
（4）公开整数n和e，秘密保存d [5] ；
（5）将明文m（mn是一个整数）加密成密文c，加密算法
（6）将密文c解密为明文m，解密算法为
然而只根据n和e（注意：不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密
安全性
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，也并没有从理论上证明破译。RSA的难度与大数分解难度等价。因为没有证明破解RSA就一定需要做大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法，即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题
RSA 是一种非对称加密算法，很多表单的密码都采用 RSA 加密。
使用 RSA 一般需要先产生一对公钥和私钥，当采用公钥加密时，使用私钥解密；采用私钥加密时，使用公钥解密。
执行结果如下：
在实际应用中，我们可以先执行 genKeyPair 先生成一对密钥，将该对密钥保存在配置文件中，然后在加密时，调用 encrypt(str, publicKey) 方法使用公钥对文本进行加密，在解密时，调用 decrypt(strEn, privateKey) 方法使用私钥对文本进行解密，即可。
RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。在了解RSA算法之前，先熟悉下几个术语
根据密钥的使用方法，可以将密码分为对称密码和公钥密码
对称密码：加密和解密使用同一种密钥的方式
公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。
RSA的加密过程可以使用一个通式来表达
也就是说RSA加密是对明文的E次方后除以N后求余数的过程。就这么简单？对，就是这么简单。
从通式可知，只要知道E和N任何人都可以进行RSA加密了，所以说E、N是RSA加密的密钥，也就是说 E和N的组合就是公钥 ，我们用(E,N)来表示公钥
不过E和N不并不是随便什么数都可以的，它们都是经过严格的数学计算得出的，关于E和N拥有什么样的要求及其特性后面会讲到。顺便啰嗦一句E是加密（Encryption）的首字母，N是数字（Number）的首字母
RSA的解密同样可以使用一个通式来表达
也就是说对密文进行D次方后除以N的余数就是明文，这就是RSA解密过程。知道D和N就能进行解密密文了，所以D和N的组合就是私钥
从上述可以看出RSA的加密方式和解密方式是相同的，加密是求“E次方的mod N”;解密是求“D次方的mod N”
此处D是解密（Decryption）的首字母；N是数字（Number）的首字母。
小结下
既然公钥是（E，N），私钥是（D，N）所以密钥对即为（E，D，N）但密钥对是怎样生成的？步骤如下：
准备两个质数p，q。这两个数不能太小，太小则会容易破解，将p乘以q就是N
L 是 p－1 和 q－1的最小公倍数，可用如下表达式表示
E必须满足两个条件：E是一个比1大比L小的数，E和L的最大公约数为1
用gcd(X,Y)来表示X，Y的最大公约数则E条件如下(gcd释义：greatest common divisor)：
之所以需要E和L的最大公约数为1是为了保证一定存在解密时需要使用的数D。现在我们已经求出了E和N也就是说我们已经生成了密钥对中的公钥了。
数D是由数E计算出来的。D、E和L之间必须满足以下关系：
只要D满足上述2个条件，则通过E和N进行加密的密文就可以用D和N进行解密。
简单地说条件2是为了保证密文解密后的数据就是明文。
现在私钥自然也已经生成了，密钥对也就自然生成了。
小结下：
我们用具体的数字来实践下RSA的密钥对对生成，及其加解密对全过程。为方便我们使用较小数字来模拟。
我们准备两个很小对质数，
p ＝ 17
q ＝ 19
N ＝ p ＊ q ＝ 323
L ＝ lcm（p－1， q－1）＝ lcm(16，18） ＝ 144
144为16和18对最小公倍数
求E必须要满足2个条件：1 E L ，gcd（E，L）=1
即1 E 144，gcd（E，144） ＝ 1
E和144互为质数，5显然满足上述2个条件
故E ＝ 5
此时 公钥=(E，N）＝ （5，323）
求D也必须满足2个条件：1 D L，E＊D mod L ＝ 1
即1 D 144，5 ＊ D mod 144 ＝ 1
显然当D＝ 29 时满足上述两个条件
1 29 144
5＊29 mod 144 ＝ 145 mod 144 ＝ 1
此时 私钥＝（D，N）＝（29，323）
准备的明文必须时小于N的数，因为加密或者解密都要mod N其结果必须小于N
假设明文 ＝ 123
解密后的明文为123。
至此RSA的算法原理已经讲解完毕
