md5选择前缀碰撞算法的改进及复杂度分析

《md5选择前缀碰撞算法的改进及复杂度分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、选择前缀碰撞算法的改进及复杂度分析MD5*宽1，韩文报2程(1．信息工程大学，郑州450001;2．数学工程与先进计算国家重点实验室，郑州450001)(*通信作者电子邮箱chengkuan0116@163．com)摘要:针对MD5选择前缀碰撞算法在实际应用时复杂度分布的失衡问题，提出了改进的MD5选择前缀碰撞算法。结合非相邻表示型(NAF)，给出了生日搜索复杂度中概率值在特定条件下的推导方式，建立了平衡参数与生日搜索复杂度之间的关系;并基于上述理论结果，通过引入新的消息差分，改进了选择前缀碰撞所需的生日碰撞形式，得到改进算法。在实际应用所需的参数条件下，改进算法相对MD5算法平均可

2、降低1比特的复杂度。分析结果表明:相对于原MD5算法，改进算法缓和了复杂度分布的失衡现象，降低了算法复杂度，更适用于实际应用。关键词:MD5;非相邻表示型;选择前缀碰撞;生日搜索;消息差分中图分类号:TP309文献标志码:AImprovementonchosen-prefixcollisionsforMD5andcomplexityanalysisCHENGKuan1*，HANWenbao2(1．InformationEngineeringUniversity，ZhengzhouHenan450001，China;2．StateKeyLaboratoryofMathematicalE

3、ngineeringandAdvancedComputing，ZhengzhouHenan450001，China)Abstract:Accordingtotheunbalanceddistributionofthecomplexityofchosen-prefixcollisionsunderthepracticalrequirement，animprovedalgorithmofchosen-prefixcollisionsforMD5wasdesigned．CombinedwithNon-AdjacentForm(NAF)，theprobabilityrelatedtothec

4、omplexityofbirthdaysearchwasdeducedundercertainconditions，andtherelationbetweenthebalanceparameterandthecomplexityofbirthdaysearchwasestablished．Thenbasedontheaboveresults，theimprovedalgorithmwasdesignedthroughimprovingtheformofbirthdaycollisionbyintroducingnewmessageblockdifferences．Underthepr

5、acticalrequirementforparameters，thecomplexityoftheimprovedalgorithmcanreduceonebitonaverage．Theresultsshowthat，comparedwiththeoriginalMD5，theimprovedalgorithmdefusesimbalanceofcomplexitydistribution，reducesthecomplexity，andismoresuitableforpracticalapplications．Keywords:MD5;Non-AdjacentForm(NAF

6、);chosen-prefixcollision;birthdaysearch;messagedifferenceShamir-Adleman)模数部分为8192比特，大大超出一般证书授权中心(CertificateAuthority，CA)所要求的1048比特的标准上界［4］。随后在2009年，Stevens等［5］通过选取更加灵活的差分路径，进一步完善了MD5选择前缀碰撞算法，并给出了理论上最优的攻击复杂度239;同时，利用X．509协议中标准的2048比特的ＲSA大数字段，运用选择前缀碰撞，成功通过3次近似碰撞伪造了CA证书，复杂度为249．9;两个复杂度的差异主要由实际应用时

7、对近似碰撞块数的限制引起。2012年，Stevens等［6］给出了最终完善后的MD5选择前缀碰撞流程及伪造证书等应用的细节。除Stevens等所做的相关工作外，周林［7］对选择前缀碰撞的部分组件进行了多平台实现。尽管在过去十年来学术界意识到了现有Hash函数的一些隐患，并致力于推广更安全的Hash函数，但实际情况是MD5仍被大量使用，基于MD5的签名体制也仍将存在很长一段时间［8］，因此，针对MD5选择前缀碰撞攻击及其实际应用的研究是十分必要的。引言Has