流密码代数攻击的研究现状及其展望

《流密码代数攻击的研究现状及其展望》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、流密码代数攻击的研究现状及其展望张龙基金项目：国家自然科学基金资助项目（60373059，60373047）；教育部博士点基金资助项目（20040013007）；国家“973”计划基金资助项目（2004CB318004）,3吴文玲2温巧燕1（1．北京邮电大学理学院，北京100876)（2．中科院软件所信息安全国家重点实验室，北京100080）（3．黑龙江大学数学科学学院，黑龙江哈尔滨150080）（zl_7768@tom.com）摘要介绍了流密码代数攻击方法的基本原理及其实现方法，详细描述了对具有LFSR结构的密钥流生成器的代数分析手段，概括了现有的降低已得方程系

2、统次数的有效方法，对整个代数攻击的计算复杂度的估计进行了全面的分析，最后对流密码的代数攻击方法进行了展望。关键词流密码代数攻击布尔函数线性反馈移位寄存器XL算法中图分类号TN918.1ReviewofalgebraicattacksonstreamciphersZHANGLong1,3,WUWen-ling2,WENQiao-yan1（1.SchoolofScience,BeijingUniversityofPostsandTelecommunications,Beijing100876,China）（2.StateKeyLaboratoryofInformati

3、onSecurity,InstituteofSoftware,ChineseAcademyofSciences,Beijing100080,China）（3.CollegeofMathematicsScience,HeilongjiangUniversity,Harbin150080,China）Abstract:Thebasictheoryandrealizingmethodsofalgebraicattacksonstreamciphersarepresentedinthispaper.Thenthealgebraicattacksonstreamcipher

4、swithlinearfeedbackshiftregisterandtheefficienttechniquestodecreasethedegreeofthenonlinearequationssystemaredescribedindetail.Afteranalyzingthecomplexityofwholeproceduresinalgebraicattacks,wesummarizethedirectionandfutureworksofthisresearchfiledintheend.Keywords:streamcipher；algebraic

5、attacks；booleanfunction；linearfeedbackshiftregister；XLalgorithm1引言近几年来，随着各国个人移动通信业务的蓬勃发展，特别是无线通信技术的不断成熟，人们开始逐步地重视无线移动通信中的安全保密问题。考虑到在个人手机上，实施加解密算法的硬件设备—SIM卡的计算能力较差且存储容量较小，而在此情况下，流密码与分组密码相比较，具有加解密速度更快、没有或只有有限的错误传播、实时性更好、更易于软硬件实现等优点，因此，流密码算法的设计与分析便再一次成为各国学者研究的热点。到2000年左右，对流密码的分析方法已经提出很多，

6、其中比较典型的有线性校验子攻击、线性一致性检验攻击、分别征服攻击、最佳仿射逼近攻击、快速相关攻击等等[1]。最近，一种被称为代数攻击（AlgebraicAttack）的分析手段成为了众多算法分析者的研究焦点，这一攻击的主要特点是它采用了基于代数思想的方法与技巧，将一个密码算法的安全性完全归约为求解一个超定的（Overdefined）多变元高次方程组系统（即该系统中的方程个数多于变量的个数）的问题上，这与以前的大都是基于概率思想的分析方法有着很大的不同。由于很多同步流密码算法，例如(Bluetooth)、Toyocryot、LILI-128等，在设计时并没有考虑到超

7、定的多变元高次方程组系统的可解性问题，因而，随着较为有效的求解超定的多变元高次方程组系统方法的出现，这些算法也就很难抵抗这种新的攻击方法了。本文以此为背景，全面地归纳和总结了近几年来流密码代数攻击方法的主要研究成果。122代数攻击方法的形成背景及基本思想2.1代数攻击的形成背景代数攻击方法主要是在以下三个方面的研究中逐步发展形成的。1、近些年来，许多公钥密码体制的安全性均建立在以下难题上：在上，求解一个随机生成的多变元二次（MultivariateQuadratic）多项式方程组是NP-hard问题。该问题与传统的大整数分解，离散对数问题完全不同。其中最典型的代表

8、就是199