您好,欢迎来到360论文服务中心!设为首页 | 加入收藏

360论文服务中心

客服中心

全国咨询电话:18810141013

QQ :点击这里给我发消息 80017332

 点击这里给我发消息 634602927

手机:18810141013

邮箱:634602927@qq.com

短信:18810141013

本站介绍

360论文服务中心是最受欢迎的论文发表与论文编辑服务网站。

360论文服务中心于2000年创建,注册用户量已突破152万人,并帮助近380万人次顺利发表论文。14年来,360论文服务中心始终遵循热情快捷、安全可靠的服务宗旨,深受广大网民青睐。360论文服务中心主要设有论文发表部、论文创作部、期刊合作部、论文采编部、技术运营部和市场推广部等多个部门,是目前国内论文行业,规模最大、服务人员最多的正规网站。

创作发表说明

1. 如果您没有论文,还要评定职称,需要发表论文,请联系我们,客服人员会及时处理;

2. 教授、博士组成的论文指导团队,专业打造高品质论文;

3. 合作期刊,全国最全,与杂志社关系稳定,保证刊期。

360论文服务中心 > 论文资料 > 计算机论文 > 计算机网络论文 >

现实RSA算法的破解

2016-03-19 14:28 字体:   打印 收藏 

中文摘要:
    我们通过用两个程序生成RSA算法中的N和素数,发现有N能整除生成的素数.得出这是由随机函数是个有限固定的集合推出现实中RSA算法可以用彩虹表法破解.
 
Abstract: We by two programs generate N of RSA algorithm and a prime number, found that there are N aliquot generated prime. It is concluded that it is launched by the random function is a finite set of fixed reality cracking RSA algorithm can use the rainbow table method.
 
中文关键词:RSA算法;彩虹表攻击;随机函数
 
Key wordsRSA algorithm.;A rainbow table attack; Random function

正文:
一.什么是RSA算法

 
 RSA公钥加密算法是1977年由罗纳德•李维斯特(Ron Rivest)、阿迪•萨莫尔(Adi Shamir)和伦纳德•阿德曼(Leonard Adleman)一起提出的。
二.我们的破解思路
    以往的破解思路都在关注大数分解,理论证明这是极难的。在分解大数没有结果的情况下我们就得换思路进行破解。
    我们先看MD5的破解,MD5HASH值不可逆,但仍然可以破解,基于的是彩虹表破解法,就是先用MD5工具算大量的明文的MD5值,然后储存起来。破解时对比MD5值,相同时就被破解。
    那么,我们破解RSA算法也可以这样,先算大量素数,然后对比是不是在素数表中,这样就能找到了。当然计算需要强大的计算能力,用天河这样的超级计算机比较合适。
    那么有朋友可能要问了,最一般的RSA1024的素数也有2^512大小,穷举的时间也是天河计算机不可接受的。我们的理论来了:
    受到素数产生技术的限制,能产生的素数较少。
    也就是说我们用一般的素数生成工具不断产生素数,用超算算一定时间后就有一个很大的素数集合了。那些素数生成工具不会产生的素数,我们同样也不用计算。这样我们就可以用彩虹表进行破解了
 
三.按照这个思路我们进行实验
    用一个程序生成N,用另一个程序生成512位素数.两个程序用的算法相同. 产生随机素数源码如下:
 
/****************************************************************************************
产生¦随机素数
调用方法:N.GetPrime(bits)
返回值¦:N被赋值为一个bits位(0x100000000进制长度)的素数
****************************************************************************************/
void CBigInt::GetPrime(int bits)
{
    unsigned i;
    m_nLength=bits;
begin:
    for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand();
    m_ulValue[0]=m_ulValue[0]|1;
    for(i=m_nLength-1;i>0;i--)
    {
        m_ulValue[i]=m_ulValue[i]<<1;
        if(m_ulValue[i-1]&0x80000000)m_ulValue[i]++;
    }
    m_ulValue[0]=m_ulValue[0]<<1;
    m_ulValue[0]++;
    for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)goto begin;}
    CBigInt S,A,I,K;
    K.Mov(*this);
    K.m_ulValue[0]--;
    for(i=0;i<5;i++)
    {
        A.Mov(rand()*rand());
        S.Mov(K.Div(2));
        I.Mov(A.RsaTrans(S,*this));
        if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(I.Cmp(K)!=0))goto begin;
    }
}
 
我们在生成了23W个素数和1344个N 对比就有重复的结果了.比如:
N=3471DB828140D20BDC7257F181612CCA8E54727CEE3D7BEE4534433C
2C002D98AC4AAB357D1D0A3FB3111C5E4FDBFACD7E716172EC95564DE543C
C19860B382B0D89BD87930340DD3EC441C88CAD669FA2799301234A34467ABA
1137C1DCE71B0CFE76EC0EDFEBC1AE258680895D0A4365D63F435C5BB98892
3D8D424D063001 PRIME1=3AF43028DD9C86509C88A0F0629E7DC838AA707E756EBD78416AA17E5B10C022EE943F62A6FCDF507CB24178D044739EB676CE869D5C719A40BC38DADE461B1B
PRIME2=E3BC292A8670FAD222E43CCE0398387A5B88B23E80307EBAC582D9C2EA2074BC3C828230A82CF1144CC0B2BABEF26ACC3E3A694EA05A6B0816667564DD945713
 
接着产生的下一个
N=2A198CC45EDA697AA710272B31155044E8B7D7B328820772FC7F8F87731DFE
2B6D9236968EAAE2F471B0AED01A2C3CBFF923D971FFEE6C04D37350B6C5218
6D8449A743B62619949D0B59F8370AA2255AAC9DEAB2E814C982F444A222225E
744EF596C863C009C410CB8AF9DACB1DAAA43419C6AC62F583DB2732D1E8ED
CAB85
PRIME1=AB1C84FAF5F674D6140AA6B4690CA4A239EE7E9C2ED61F8E1C80B4600C8CFDD0CB247AB4BA78E866F35EC3F86CB25EF2A1C2DF429A50420AED785600FB24BA1B
PRIME2=3EFC4E86A5C436F2EE2A190435CE359C8D2AE1C0068CDC9462A874A64CDE661833F80B8AB264C82ECBDE9A04A474A7B05FC27DC22D90ABF6CB64AB6091648ADF
接着同样有N=PRIME1*PRIME2
 
    那么我们来看下素数产生的程序.
     rand()for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand();.:
    那么我们就推定rand()产生的数并不是真的随机数,而且生成的数不与时间有关,当前rand()确定,那么下一个rand()也确定. rand()是个确定顺序的有限集合,那么产生的素数也是有限集合的了,从而可以用彩虹表破解了.        
    Arjen K Lenstra,James P Hughes的论文Ron was wrong,whit is right中指出发现RSA密钥中有重复的弱密钥.大概700万中有27000个重复的弱密钥 我们根据概率算得整个大概有18亿的密钥空间.rand()产生的值在0~65535之间.那么素数产生程序起始rand()有64K的可能,即可能产生64K个数的素数 那么生成的N有64k*64k/2个,即18亿,与Arjen K Lenstra,James P Hughes的论文相符.
                                             
                                                  
参考文献:
[1]. Arjen K Lenstra,James P Hughes.Ron was wrong,Whit is right.[M]http://eprint.iacr.org/ 201
2/064.pdf. 2012
[2].杨波.网络安全理论与应用[M]电子工业出版社,2002
[3].谭浩强.C程序设计[M]清华大学出版社,1999
[4].Andrew S.Tanenbaum.计算机网络[M]清华大学出版社.1998


 

联系我们

全国免费热线:400-086-0807
咨询QQ:634602927
投稿邮箱:634602927@qq.com