RSA加解密演算与暴力破解12位

大家都知道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个量子比特位相当于一台超级计算机。

您的意见是我改善的东西，欢迎评论提建议，如果对您有帮助，请点个赞，谢谢~~

菲麦前端专题，汇聚前端好文，邀您关注！

急求！！“1024位的RSA 公开密钥加密算法 ”数据结构课程设计！高手解答啊！！

[我是不是复制粘贴的，我认真写的，你也认真看下就懂了]

我写的这个浅显易懂，看看你就明白了。举得有例子。

RSA算法举例说明

空间里面好像还有算法

知道里面刚才回答了另个朋友的问题帖出来给你看看

题目：用RSA算法加密时，已经公钥是（e=7,n=20）,私钥是（e=3,n=20），用公钥对消息M=3加密，得到的密文是_____？

给出详细过程。 谢谢！

答：

你所说的：

n=20

d=7 公钥

e=3 私钥

对M=3 进行加密

M'=M^d%n (M的d次方，然后除以n取余数)

M'=3^7%20=2187%20=7 加密后等於7

对M'=7进行解密

M=M'^e%n=7^3%20=343%20=3 解密后又变成3了

你取的两个素数太小了，所以n太小根本起不了作用。至少要取1024位的数字

RSA密码体制抗破解的原理是什么?

RSA密码体制抗破解的原理是：利用Euclid 算法计算解密密钥d, 满足de≡1(mod φ(n))。其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。

现在常规的密码破解方式有两种，分别是暴力破解和字典破解。通常的破解软件你还可以设置字符集（比如选择是否算上符号，大小写字母和数字等）。用这种方式只要密码不超过能破译的长度范围，在一定时间下是一定能破解出来的，唯一缺点就是速度太慢。

为提高保密强度

RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。

rsa高位攻击 恢复p

核心考点在于拿到rsa中p的前568位，但是知道 e n 要利用算法破解1024位的p，至少需要576位，所以要爆破8位的二进制，达到576位了再用算法恢复完整的p

密码题目在最下方的whctf2017.py

144.py截图

142+2.py截图

so easy，脚本为最下面的 rsa.py

git clone

运行结果

运行结果

1024位RSA加解密怎么用

[我是不是复制粘贴的，我认真写的，你也认真看下就懂了]

我写的这个浅显易懂，看看你就明白了。举得有例子。

RSA算法举例说明

空间里面好像还有算法

知道里面刚才回答了另个朋友的问题帖出来给你看看

题目：用RSA算法加密时，已经公钥是（e=7,n=20）,私钥是（e=3,n=20），用公钥对消息M=3加密，得到的密文是_____？

给出详细过程。 谢谢！

答：

你所说的：

n=20

d=7 公钥

e=3 私钥

对M=3 进行加密

M'=M^d%n (M的d次方，然后除以n取余数)

M'=3^7%20=2187%20=7 加密后等於7

对M'=7进行解密

M=M'^e%n=7^3%20=343%20=3 解密后又变成3了

你取的两个素数太小了，所以n太小根本起不了作用。至少要取1024位的数字

RSA加密、解密、签名、验签的原理及方法

RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。两者之间有数学相关，该加密算法的原理就是对一极大整数做因数分解的困难性来保证安全性。通常个人保存私钥，公钥是公开的（可能同时多人持有）。

加密和签名都是为了安全性考虑，但略有不同。常有人问加密和签名是用私钥还是公钥？其实都是对加密和签名的作用有所混淆。简单的说，加密是为了防止信息被泄露，而签名是为了防止信息被篡改。这里举2个例子说明。

RSA的加密过程如下：

RSA签名的过程如下：

总结：公钥加密、私钥解密、私钥签名、公钥验签。

RSA加密对明文的长度有所限制，规定需加密的明文最大长度=密钥长度-11（单位是字节，即byte），所以在加密和解密的过程中需要分块进行。而密钥默认是1024位，即1024位/8位-11=128-11=117字节。所以默认加密前的明文最大长度117字节，解密密文最大长度为128字。那么为啥两者相差11字节呢？是因为RSA加密使用到了填充模式（padding），即内容不足117字节时会自动填满，用到填充模式自然会占用一定的字节，而且这部分字节也是参与加密的。