RSA的解密方法 | JucanaYu’s Blog

type

status

date

slug

summary

一、前记

在进行RSA解密之前。先介绍python的两个有用的库

1、libnum

用处1：一般使用在cmd命令里面，使用在编辑器下面可能会导致部分错误。可以使用字符串与数字相互转换以及分解。

主要是以下几个几个：

n2s：数字（不论是十六进制还是十进制）与字符串之间的转换

b2s：二进制转换成字符串

s2n：字符串转换成整数

s2n：字符串转化成整数

像这样

用处2：用来分解得到质数

直接就是factorize(数字)

例如：

代表着3个11相乘

2、gmpy2

gmpy2是一个强大的数论库，能有效的解决一些大数问题。可以使用在编辑器里面，也可以使用在cmd里面

用法一：查看一个数字是不是质数

格式：is_prime(数字)

用法二：初始化一个大整数

格式：mpz(数字)

对于一个大数来说，是要先将其初始化。

用法三：幂取模，一个数先次方，再取模

格式：powmod(M,e,n) C=M^e mod n

例如：

用法四：求逆元

(a*b)%c==1

格式：invert(a,b)

（参考链接：https://xz.aliyun.com/t/2446）

例如这样的：

验证一下：（a*结果）%b==1

结果正确

用法五：欧几里得算法（辗转相除法）用来求最大公约数的

格式：gcd(a,b)

类似于：

（参考链接：https://cloud.tencent.com/developer/article/1175131）

例如下面的例子：

用法六：计算拓展欧几里得算法

计算已知整数a、b，在求得a,b最大公约数的同时，找到整数x，y (有一个可能为负数)，使之满足：ax+by=gcd(a,b)

格式：gcdext(a,b)

如下例子：

第一个结果是最大的公约数，第二个结果是x，第三个结果是y

用法七：一个数开n次根

格式：iroot(a,n)

如以下例子：

当完整的开出来之后，会显示为true，否则为false

用法八：求最小公倍数

格式：lcm(a,b)

如下例：

二、RSA简介

它是一种公钥加密算法。在RSA里面有几个比较重要的参数：

M（明文）：一般是十进制，但是也不排除其他进制的可能性

C（密文）：一般为十进制，不排除有其他进制的可能性

大质数p和q：一般是为N做准备。N=p*q

L（p-1）和（q-1）的最小公倍数

E，N一般为一组公钥

D，N一般为一组私钥

明文经过公钥加密，密文私钥解密

三、RSA加密的步骤

生成密钥对

求N：首先准备两个很大的质数p和q（太小容易被破译，太大的话计算时间容易变长） N=p*q

求L： L=lcm(p-1,q-1) 即(p-1)和(q-1)的最小公倍数

求E：E要满足两个条件，即E和L的最大公约数必须为1，gcd(E,L)=1;1<E<L

求D：要满足两个条件，即1<D<L;D*E mod L=1;D=invert(E,L)

密文=明文^E mod N

四、RSA密文解密

除了正常解法之外，另外还会有几种比较特殊的解法，下面我就用已知参数来分别讲述解法和脚本。

情一：已知c，d，n，e（是RSA最简单的一种情况）

将n分解成p和q（yafu，在线factor都可以）

再一步步去算

具体脚本：

情二：当e非常大（肉眼不可见的时候）主要是快速求d

使用wiener_Attack，低解密指数攻击

情三：有一个n，多组c，e

使用共模攻击

情四：一个e，多组n，c

广播攻击

情五：只有一组且e比较小

低加密指数攻击

当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。如果明文的三次方虽然比n大，但是大不了多少，则可以爆破

情六：已知n,c,e和明文的高位

明文高位已知：参考https://github.com/mimoo/RSA-and-LLL-attacks

情七：已知dp，dq求解

dp=d%(p-1) dq=d%(q-1)

解密代码如下：

情八：已知n,e,dp,c时，可求d

dp泄露攻击

情九：n可以被分解成多个素数

修改欧拉函数即可

非常特殊的情况：

情十：已知n,c,e和m的高位

如果已知明文三分之二的比特就可以求出明文（Coppersmith定理攻击）

借鉴的sage文件代码

sage代码可以在在线网站运行：https://sagecell.sagemath.org/

情十一：已知n，p的大部分比特，还原p

sage文件

五、参考

参考链接：

https://github.com/kur0mi/CTF-RSA/tree/master/%E5%8A%A0%E5%AF%86%E6%8C%87%E6%95%B0/copperSmith%E9%83%A8%E5%88%86%E4%BF%A1%E6%81%AF%E6%94%BB%E5%87%BB

https://kirin-say.top/2018/04/09/CTF-RSA%E5%9F%BA%E6%9C%AC%E7%A0%B4%E8%A7%A3%E5%A7%BF%E5%8A%BF/#0x06-%E6%98%8E%E6%96%87%E9%AB%98%E4%BD%8D%E5%B7%B2%E7%9F%A5