一、前记

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

1、libnum

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

主要是以下几个几个:

n2s:数字(不论是十六进制还是十进制)与字符串之间的转换

b2s:二进制转换成字符串

s2n:字符串转换成整数

s2n:字符串转化成整数

像这样

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

直接就是factorize(数字)

例如:

代表着三个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里面有几个比较重要的参数:

1、M(明文):一般是十进制,但是也不排除其他进制的可能性

2、C(密文):一般为十进制,不排除有其他进制的可能性

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

4、L(p-1)和(q-1)的最小公倍数

5、E,N一般为一组公钥

6、D,N一般为一组私钥

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

三、RSA加密的步骤

1、首先生成密钥对

(1)求N

首先准备两个很大的质数p和q(太小容易被破译,太大计算时间容易变长)

N=p*q

(2)求L

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

(3)求E

E要满足两个条件:E和L的最大公约数必须为1;1<E<L

(4)求D

要满足两个条件:1<D<L;D*EmodL=1

D=invert(E,L)

密文=明文^E mod N

四、RSA密文解密

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

情一:已知c,d,n,e(是RSA最简单的一种情况)

将n分解成p和q(yafu,在线factor都可以)

再一步步去算

具体脚本:

五、后记

有很多特殊的解法大家都可以在搜索引擎里面搜到。推荐几个链接:

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