代数攻击流密码之研究

《代数攻击流密码之研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机光盘软件与应用工程技术ComputerCDSoftwareandApplications2010年第8期代数攻击流密码之研究汤永龙（吉首大学信息管理与工程学院，湖南张家界427000）摘要：说明了对具有LFSR结构的密钥流生成器的代数分析手段，阐述了代数攻击流密码基本原理及实现方法，概括了现有的降低已得方程系统次数的有效方法，对整个代数攻击的计算复杂度的估计进行了全面的分析研究和改进，最后对流密码的代数攻击方法进行了展望。关键词：流密码；代数攻击；布尔函数；XL算法中图分类号：NO151文献标识码：A文章编号：1007-9599（2010）08-0050-03T

2、heStudyofAlgebraicAttacksonStreamCiphersTangYonglong(JishouUniversity,InformationManagement&EngineeringInstitute,Zhangjiajie427000,China)Abstract:Realizingmethodsofalgebraicattacksonstreamciphersarepresentedinthispaper.Thenthealgebraicattacksonstreamcipherswithlinearfeedbackshiftregiste

3、randtheefficienttechniquestodecreasethedegreeofthenonlinearequationssystemaredescribedindetail.Afteranalyzingthecomplexityofwholeproceduresinalgebraicattacks,finallywesummarizethedirectionandfutureworksofthisresearchfiled.Keywords:Streamcipher;Algebraicattacks;Booleanfunction;XLalgorith

4、m一、代数攻击流密码的方法和基本思想特，完全可以建立一个仅仅以LFSR的初始状态来作为基变量的4[4]（一）“代数攻击（AlgebraicAttack）”流密码的基本方法次方程，其中也不用不包含相应的记忆比特，再然用在求解一个随机生成的多变元二次（MultivariateLinearization方法，就可以给出了破解。改进后的算法的复杂Quadratic）多项式方程组是NP-hard问题。该问题与传统的大整度为7⋅Tlog27≈270.341，远远优于其它已知的结果。数分解，离散对数问题完全不同。最典型的代表就是由Patarin（二）代数攻击简化后的具有线性反馈结构

5、性质的滤波生成---[4]在1996年提出的HFE密码，及其相应的变种HFE、HFE、HFEV、器[1]HFEF等。Courtois等人在2002年对AES的研究得出代数攻击常用的基于LFSR的简化后的具有线性反馈结构滤波生成器流密码结构形式，AES中在字节变换步骤中AES所使用的非线性如图2-1所示：S-盒可以由一个有限域GF（256）上超定的多变元的2次方程组来表示。并且AES候选算法中的Serpent同样也满足假设条件，再由Toyocrypt、E0等几个具有线性的反馈结构形式的流密码的[3，4]安全性进行了比较系统的研究，从而得出这些公开密码系统的安全完全可以归

6、约为求解一个超定的多变元高次方程组。并且Linearization、Relinearization、XL、GrobnerBases等人也图2-1基于LFSR简化后的滤波生成器系统给出了求解超定的高次多变元方程组的一此比较好的算法。其中，K=(k0,L,kn−1)是初始密钥，L是线性反馈移位寄存器，（二）代数攻击流密码的基本步骤f是非线性滤波函数，bt+1为t+1时刻输出的密钥流比特。研究表（1）通过某些方法将要研究分析的密码系统的安全性（设为明这种流密码的结构，下面的方程组是成立：安全参数p）规约（Reduce）到求解一个超定（overdefined）的⎧bfkk=(

7、,,)L001n−多变元高次方程组的问题上⎪⎪bfL=((,,))kkL10n−1（2）然后再用一些比较好的方法，比如Linearization、⎨bfLkk=((,,))2L⎪20n−1Relinearization、XL等，对（1）中所产生的超定（overdefined）⎪⎩M的多变元高次方程组系统求解。现在要研究的问题是：知道m个(t,bt)，由上述方程组知道只（3）再把（2）中求出的（1）中的解反馈到具体的密码系统有K=(k0,L,kn−1)未知，这样通过求解一个m个高次方程，n个未的所设定的安全参数p上来。最后达到代数攻击流密码的目的。知量