CTF| 你想要的RSA解题技巧（二）

上一期已经给大家分享了RSA的基本解题思路，总结如下，本期带来几种复杂的RSA题目解法。

以上都是基本解法，基于n能够分解的前提下进行的解法，但是当题目n的长度达到2048、4096bit以上的级别的时候，上述的方法就不适用了。

一、CTF题目实战

1.1 利用n的公约数

题目链接 ： http://pan.baidu.com/s/1bo7maR1

密码：kd7o

题目：在一道CTF题中，已知n1和n2且长度很大，e都为65537。

解题思路：

求解n1，n2的最大公约数，用python脚本实现，脚本参考下篇文章。http://www.cnblogs.com/reborn-blog/p/7553528.html

此时求解出一个公约数，此即为n1，n2共有的共因素p，在借助公式n=p*q解出q。

1.2 共模攻击

我们知道RSA加密算法：

如果收到两份密文c1,c2，是一个明文m由相同的n和不同的2个e（e1，e2）进行加密的，此时无需求解出d即可破解出明文，具体的证明过程就不给出了，可自行查阅资料。

题目链接：http://pan.baidu.com/s/1bSmJHO

密码：0mzz

题目：

解题思路：这道题给出两个加密文件，flag.enc1和flag.enc2，verhardRSA.py给出了N的值和e1,e1。

打开加密文件会乱码，你可以使用winhex来提取十六进制。也可以使用python的libnum模块来进行进制和字符串的转换。

libnum模块的安装方法：

git clone https://github.com/hellman/libnum

cd libnum

python setup.py install

下面直接给出这种题型的解密脚本，脚本作者是ByStudent，非斗哥原创。

gmpy2模块可以参考pcat的文章安装，http://www.cnblogs.com/pcat/p/5746821.html

1.3 低加密指数攻击

加密指数指的是e，因为e是可以随机选取的，当e很小时就会被直接破解掉。

当e=3，而且明文也很小，导致明文的三次方仍然小于n，那么通过直接对密文3次开放，即可得到明文。

C=me mod n

如果e=3，且me<n，那么

me mod n= me ，即C=me

m=3√c

如果e=3，且me>n，那么设k，有：

c= me +kn

爆破k，如果c−kn能开三次根式，那么可以直接得到明文。

题目链接：http://pan.baidu.com/s/1nuIxdQ5

密码：avvw

解题思路：通过公钥pubkey.pem获取e和n的值：

发现n的长度为4098，难以直接分解得到p和q。

e=3,尝试使用低加密指数攻击，通过计算可知密文的3次方大于n。

利用脚本爆破n的值求出m。

将m转换字符串的形式。

二、总结

大致介绍了3种情形，RSA题目解密方法远不止这些，本文算是上一篇的延伸，所有脚本和题目，以及脑图和密码学相关的几本书籍都放在网盘。

链接：http://pan.baidu.com/s/1i55UoQh

密码：5l4s

小伙伴们根据需要进行下载吧。