RSA算法的破解

zuoyuanturing

一.什么是RSA算法
    RSA公钥加密算法是1977年由罗纳德•李维斯特（Ron Rivest）、阿迪•萨莫尔（Adi Shamir）和伦纳德•阿德曼（Leonard Adleman）一起提出的。
    RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
   正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。

二.我们的破解思路
    以往的破解思路都在关注大数分解，理论证明这是极难的。在分解大数没有结果的情况下我们就得换思路进行破解。
    我们先看MD5的破解，MD5HASH值不可逆，但仍然可以破解，基于的是彩虹表破解法，就是先用MD5工具算大量的明文的MD5值，然后储存起来。破解时对比MD5值，相同时就被破解。
    那么，我们破解RSA算法也可以这样，先算大量素数，然后对比是不是在素数表中，这样就能找到了。当然计算需要强大的计算能力，用天河这样的超级计算机比较合适。
    那么有朋友可能要问了，最一般的RSA1024的素数也有2^512大小，穷举的时间也是天河计算机不可接受的。我们的理论来了：
    受到素数产生技术的限制，能产生的素数较少。
    也就是说我们用一般的素数生成工具不断产生素数，用超算算一定时间后就有一个很大的素数集合了。那些素数生成工具不会产生的素数，我们同样也不用计算。这样我们就可以用彩虹表进行破解了

                                        湖南长沙 左远
                                                   2016/3/10

fender0107401

zuoyuanturing 发表于 2016-03-10 19:33
一.什么是RSA算法
    RSA公钥加密算法是1977年由罗纳德•李维斯特（Ron Rivest）、阿迪•萨莫尔 ...

> 我们先看MD5的破解，MD5HASH值不可逆，但仍然可以破解，基于的是彩虹表破解法，就是先用MD5工具算大量的明文的MD5值，然后储存起来。破解时对比MD5值，相同时就被破解。

cjaizss

精神病人思维广,
弱智儿童欢乐多.

lxyscls

回复 1# zuoyuanturing


    要确定一个数是不是素数，和找到那个确定的素数，难度能一样？

   

zuoyuanturing

现在的RSA的密钥在最普通的PC上一分钟能生成 是个速度很快的找素数的方法 只要找到的是素数 大小符合要求就行 大量的素数是用快速方法找不到的
也就是说 产生的素数是个小的集合 而且生成速度很快 2007年的一篇论文测试产生一个2^512的素数用两种方法在一台PC 上大约需要1秒和4秒的时间 天河是300万个计算核心 而且CPU更快 所以能产生大量的素数 剩下的就是估算下通用算法能产生的素数有多少 就能判断大约需要多少时间了
对于RSA 只要一个素数被算到 也就是破解了

zuoyuanturing

如果是对抗全世界的计算量 RSA1024 估计是不够的 估计任何找素数的方法估计都不行 要多少位 要看总计算量

zuoyuanturing

htt p://ww w.csdn.ne t/article/2012-02-15/311821
700万份密钥中有27000分重复 设总数为M 则M大约满足 (7000000-27000)/M=27000/(7000000-27000)
得M大约为18*10^8
假设天河一核心1秒可算1个密钥对 5分钟大约能算出来一半

windoze

lz又来了……上次和你说的遍历2^1024个数字要多久你忘了？哦，你还要把算出来的素数都存起来…………

I服了U

zuoyuanturing

上次没说对 这次没有错
受到素数产生技术的限制，能产生的素数较少。700万密钥有27000分重复的不是我的数据吧

这是原话:
摘要：一组研究人员发现，使用RSA算法对敏感在线交流与交易进行加密生成的公开密钥中存在一个漏洞。 通过对700万样本研究，研究人员发现其中27000份样本的公开密钥并非随机生成。也就是说，可能有人算出用于创建公开密钥的秘密素数。

MMMIX

RSA 的 vulnerable public keys 早就有人研究过，这是论文：
https://factorable.net/paper.html

Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

Abstract
RSA and DSA can fail catastrophically when used with malfunctioning random number generators, but the extent to which these problems arise in practice has never been comprehensively studied at Internet scale. We perform the largest ever network survey of TLS and SSH servers and present evidence that vulnerable keys are surprisingly widespread. We find that 0.75% of TLS certificates share keys due to insufficient entropy during key generation, and we suspect that another 1.70% come from the same faulty implementations and may be susceptible to compromise. Even more alarmingly, we are able to obtain RSA private keys for 0.50% of TLS hosts and 0.03% of SSH hosts, because their public keys shared nontrivial common factors due to entropy problems, and DSA private keys for 1.03% of SSH hosts, because of insufficient signature randomness. We cluster and investigate the vulnerable hosts, finding that the vast majority appear to be headless or embedded devices. In experiments with three software components commonly used by these devices, we are able to reproduce the vulnerabilities and identify specific software behaviors that induce them, including a boot-time entropy hole in the Linux random number generator. Finally, we suggest defenses and draw lessons for developers, users, and the security community.