rsa：大整数相乘的问题

zuoyuanturing

RSA算法的破解
一.什么是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