-
-
[原创]RSA弱公钥公因数漏洞介绍与解题
-
2017-9-22 07:24
-
这篇文章记录的是关于RSA的弱公钥漏洞，并利用漏洞解题。
这篇文章我还发在C博客上，博主名字还是samohyes。如有雷同，并非抄袭。。。哈哈哈
英文论文的原文是《Mining your Ps and Qs: Detection of Widespread Weak Keys in Network Devices》。
接触这个的原因是课程中第一个关于密码学的大作业中有3个hard级别的题目。我解决了两个，还有一个是我的队友做出来的，我没细看。我解决的一个是padding oracle，这个内容网上有不少，我当时也是看了中文文献才懂的。看英文的有点吃不消，看了几篇没懂后来就去看中文的了。而这个Ps and Qs 我查了后发现没有什么中文资料，硬啃英文文献加上理解才了解并解出来。所以这里就做一个简单的介绍和做题过程，一方面自己加以记录，一方面给别人以参考。这里的介绍会比较简单，因为还有个课程项目等我做。
Part1: 原理介绍
首先RSA原理具体不介绍了，阮一峰的博客上有这样一段，直接搬过来吧。
这里我们知道公钥是（n,e）私钥是（n,d）要想知道d那么就是要分解n。但是n很大，人类目前分解不了1024位的大数。那怎么办呢？虽然我们分解不了一个大数，但是如果我们要找两个大数的最大公约数（GCD）却相对比较简单。所以，如果我们拿到一大堆的n，也就是moduli我们是不是可以两两找他们的最大公约数，如果找到了，我们就可以分解了。不过这个漏洞并不是RSA自身算法的漏洞，只是我们没有产生足够随机的n罢了。不过，这还是可以被我们利用起来，找到私钥！
Part2: 解题流程
课程提供了：
一个.hex文件，里面全部是moduli；一个pbp.py文件，里面提供一个decrypt函数，找到key后传进去就可以找到明文了；一个密文，需要和key一起传进函数1.获得GCD
代码如下，效率很低，需要3小时左右获得所有公约数。最终我获得了51对moduli，和他们的GCD。这里应该有更好的算法，有想法的朋友希望能够说出来分享下。
2. 利用GCD获得private key
过程就是我上面的阮一峰博客截图。利用公因数就可以分解n，分解掉后就好办了。麻烦一点的就是后面那个扩展欧几里得函数了，不过维基百科上有python代码，拿来就用了，这一步解出了私钥中的d。
3.利用得到的私钥破解出明文。
这里有一个注意点，那就是我们需要用到pycrypto中的RSA去构造一个key。而RSA.construct中的参数必须是long。这个点最后困扰了我们很久。具体代码如下。
大体结果就在这里了。后面附上github的代码链接。
https://github.com/samohyes/UIUC-CS461.git
mp1里面的1.2.4.py就是了。题目还有相关的东西都在里面了。有兴趣的朋友可以下下来做一做。
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
