流密码代数攻击的研究现状及其展望张龙⑴吴文玲2温巧燕】(1.北京邮电大学理学院，北京100876)(2中科院软件所信息安全国家重点实验室，北京100080)(3.黑龙江大学数学科学学院，黑龙江哈尔滨150080)(zl_7768@tom.com)摘要介绍了流密码代数攻击方法的基本原理及其实现方法，详细描述了对具有LFSR结构的密钥流生成器的代数分析手段，概括了现有的降低已得方程系统次数的有效方法，对整个代数攻击的计算复杂度的估计进行了全面的分析，最后对流密码的代数攻击方法进行了展望。关键词流密码代数攻击布尔函数线性反馈移位寄存器XL算法中图分类号TN9I8.IReviewofalgebraicattacksonstreamciphersZHANGLong13,WUWen-ling2,WENQiao-yan1(I.SchoolofScience,BeijingUniversityofPostsandlelecommunications,Beijing100876,China)(2.StateKeyLaboratotyofInformationSecurity,InstituteofSoftware,ChineseAcademyofSciences,Beijing100080.China)(3.CollegeofMathematicsScience,HeilongjiangUniversity,Haibin150080,China)Abstract:Thebasictheoiyandrealizingmethodsofalgebraicattacksonstreamciphersarepresentedintliispape匚Thenthealgebraicattacksonstreamcipherswithlinearfeedbackshiftregisterandtheefficienttechniquestodecreasethedegreeofthenonlinearequationssystemaredescribedindetail.Afteranalyzingthecomplexityofwholeproceduresinalgebraicattacks,wesummarizethedirectionandfutureworksofthisreseairhfiledintheend.Keywords:streamcipher;algebraicattacks;booleanfunction;linearfeedbackshiftregister;XLalgorithm1引言近儿年来，随着各国个人移动通信业务的蓬勃发展，特别是无线通信技术的不断成熟，人们开始逐步地匝视无线移动通信中的女全保密问题。考虑到在个人手机上，实施加解密算法的硬件设备一SIM卡的计算能力较差且存储容量较小，而在此情况下，流密码与分纽密码相比较，具有加解密速度更快、没有或只有有限的错谋传播、实时性更好、更易于软硬件实现等优点，因此流密码算法的设计与分析便再一次成为各国学者研究的热点。到2000年左右，对流密码的分析方法己经提出很多，其中比较典型的有线性校验子攻击、线性一致性检验攻击、分别征服攻击、最佳仿射逼近攻击、快速相关攻击等等⑴。最近，一种被称为代数攻击(AlgebraicAttack)的分析手段成为了众多算法分析者的研究焦点，这一攻击的主要特点是它采用了基于代数思想的方法与技巧，将一个密码算法的安全性完全归约为求解一个超定的(Overdefined)多变元高次方程纟I［系统(即该系统中的方程个数多于变量的个数)的问题上，这与以前的大都是基于概率思想的分析方法有着很人的不同。由丁•很多同步流密码算法，例如Ej/Blucloolh)、ToyocryotLILI-128等，在设计时并没有考虑到超定的多变元高次方程组系统的可解性问题，因而，随着较为有效的求解超定的多变元高次方程组系统方法的出现，这些算法也就很难抵抗这种新的攻击方法了。本文以此为背景，全而地归纳和总结了近儿年来流密码代数攻击方法的主要研究成果。基金项目：国家自然科学基金资助项H(60373059,60373047)；教冇部博士点基金资助项H(20040013007)；国家“973”计划基金资助项H(2004CB318004)2代数攻击方法的形成背景及基本思想2.1代数攻击的形成背景代数攻击方法主要是在以下三个方面的研究中逐步发展形成的。1、近些年來，许多公钥密码体制的安全性均建立在以下难题上：在GF(p)上,求解-个随机生成的多变元二次(MultivariateQuadratic)多项式方程组是NP・hard问题。该问题与传统的大整数分解，离散对数问题完全不同。其中最典型的代表就是1996年由Patarin捉出的HFE密码系统叫及:其变种HFE、HFE、HFEV、HFEF等⑶。2、对分组密码的研究，特别是2002年Courtois等人对AES的代数结构研究⑷表明，AES中字节变换步骤所使川的非线性S-盒可用一个有限域GF(256)上的超定的多变元2次方程组表出(以接近于1的概率)。而AES候选算法Serpent也满足这一假设。3、文献［5,6,7份别对Toyociypl、E。等儿个具有线性反馈结构的流密码(密钥流牛成器)的女全性进行了详细地分...