你想要的RSA解题技巧(二)

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

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

00.png


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

一、CTF题目实战

1.1 利用n的公约数

题目链接 : http://pan.baidu.com/s/1bo7maR1  密码:kd7o

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

1.1 1.png

解题思路:求解n1,n2的最大公约数,用python脚本实现,脚本参考下篇文章

http://www.cnblogs.com/reborn-blog/p/7553528.html

1.1 2.png

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

1.2 共模攻击

我们知道RSA加密算法:

1.2 1.png

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

题目链接:http://pan.baidu.com/s/1bSmJHO 密码:0mzz

题目:

1.2 2.png

这道题给出两个加密文件,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

用.png

用2.png

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,如果ckn能开三次根式,那么可以直接得到明文。

题目链接:http://pan.baidu.com/s/1nuIxdQ5  密码:avvw

avw.png

通过公钥pubkey.pem获取e和n的值:

用 3.png

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

p q.png

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

大于  N.png

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

m.png

将m转换字符串的形式。

形式.png

二、总结

大致介绍了3种情形,RSA题目解密方法远不止这些,本文算是上一篇的延伸,所有脚本和题目,以及脑图和密码学相关的几本书籍都放在网盘:链接:http://pan.baidu.com/s/1i55UoQh 密码:5l4s,小伙伴们根据需要进行下载吧。

640.webp.jpg

4

更多精彩
发表评论

已有 1 条评论

取消
Loading...

填写个人信息

姓名
电话
邮箱
公司
行业
职位
css.php