-
-
[原创]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: 解题流程
课程提供了：
1.获得GCD
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
