资源描述：
《对bivium流密码的变元猜测代数攻击》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第8期电子学报Vol.39No.82011年8月ACTAELECTRONICASINICAAug.2011对Bivium流密码的变元猜测代数攻击1,21李昕,林东岱(1.中国科学院软件研究所信息安全国家重点实验室,北京100190;2.中国科学院研究生院,北京100190)摘要:非线性方程组的求解是代数攻击的关键一环.对于一个具体的密码系统,在转化为方程组后,由于其计算上的复杂性,一般采用先猜测部分变元,再进行求解分析的方法.本文首先给出了对于猜测部分变元后子系统平均求解时间的估计模型,提出了基于动态权值以及静态权值的猜测变元选则方法和面向寄存器的猜测方法.在计算GrÊ
2、bner基的过程中,对变元序的定义采用了AB,S,S-rev,SM,DM等十种新的序.同时,提出了矛盾等式的概念,这对正确分析求解结果以及缩小猜测空间有重要作用.最后,我们对Bivium流密码算法的攻击时间进行了估计.结果表明,在最坏情况下,使用DM-rev序及Evy3的猜测位置,猜测60个变元有最优的攻击结果,约2exp(39.16)秒.关键词:方程组求解;GrÊbner基;Bivium流密码算法;猜测决策算法;矛盾等式中图分类号:TP301文献标识码:A文章编号:0372-2112(2011)08-1727-06GuessingSpecificVariablesin
3、AlgebraicAttacksonBivium1,21LIXin,LINDong-dai(1.StateKeyLaboratoryofInformationSecurity,InstituteofSoftware,ChineseAcademyofSciences,Beijing100190,China;2.GraduateSchooloftheChineseAcademyofSciences,Beijing100190,China)Abstract:Solvinganequationsystemisaveryimportantstepinalgebraicattack
4、.Foracryptosystem,afterbeingtransformedtoequations,weoftenneedtoemployguess-and-determinealgorithmtoestimatecomputationalcomplexityofthisattack.Inthispa-per,weintroduceamodeltoestimateaveragetimeinsolvingsubsystemsmoreaccurately,andproposesomecriteriaonselectingspecificguessedvariablesto
5、speedupthesolvingefficiency,whichbasedonstaticweightanddynamicweightetc.ForcomuptingGrÊbnerbases,weuseserveralvaribleorderwhichareAB,S,S-revetc.Meanwhile,weintroducetheconceptofconflictingequa-tions,andshowtheimportanceforcorrectanalysisandnarrowguessingspace.Intheend,weestimatethetimeof
6、attackingBivium.Experimentsshowedthat,intheworstcases,guessing60variblesintheEvy3positionandwithDM-revvaribleorderwillhavetheoptimalresult,thatisabout2exp(39.16)seconds.Keywords:equationssolving;GrÊbnerbases;Bivium;guess-and-determinealgorithm;conflictingequations程系统,上述算法均很难直接求解.1引言先猜测部分
7、变元,把原始的大的方程系统化为若干近年来,代数攻击逐渐成为密码分析中的热点,出小的方程系统,逐个进行求解分析是一种变通的做法.现了大量的对于分组密码,流密码,公钥密码的研究成如可以指定猜测n个变元,把整个方程系统化为2n个[1~4]果.代数攻击的发展也促进了解方程技术的进一步子系统,一旦求出某个子系统中其余变元的值,便可从[5][6]发展.如线性化算法,XL算法,吴方法,GrÊbnerBasis中恢复密钥.否则,若方程无解,说明猜测错误,继续进算法[7,8]等.其中,GrÊbnerBasis算法最令人瞩目,其实现n行下一组猜测.在最坏情况
