序列密码发展报告(X年中国密码学学术会议)

序列密码发展报告戚文峰胡予濮2报告内容一、引言二、国外序列密码研究态势三、我国序列密码研究现状四、国内外序列密码研究进展比较五、序列密码发展趋势3早期国际序列密码研究的重点为基于LFSR序列的非线性序列生成器。如前馈、组合、钟控等一、引言钟控LFSR2LFSR1非线性过滤……f(x1,…,xn)线性42000年启动的欧洲NESSIE计划和2004年启动的欧洲eSTREAM计划极大地推动了国际序列密码算法设计和分析的发展。以eSTREAM计划中胜出算法为代表的新一代序列密码算法，标志着非线性驱动和非线性迭代已成为国际序列密码设计的主流方向，它们将成为未来序列密码分析的主要焦点。5我国学者自上世纪八十年代开始，就融入了国际序列密码设计和分析研究领域。近几年，更是在序列密码的多个前沿方向做出了重要的研究成果，为我国序列密码的发展、应用、标准化起到了积极的推动作用。6（1）序列密码设计态势2000年1月，欧洲开始了一项新的欧洲数字签名、数据完整性和加密标准的计划,即NESSIE计划。NESSIE计划共征集到6个序列密码候选算法:LEVIATHAN,LILI-128,BMGL,SNOW,SOBER-t16,SOBER-t32二、国外序列密码研究态势NESSIE密码计划7由于所有候选算法在安全性等指标上都未达到NESSIE的要求，所以最终全部落选。一方面，反映出2000年前后国际上序列密码设计思想的局限性；另一方面，暴露了从线性序列变换到非线性序列的传统设计模式的安全隐患，促进了相关攻击和代数攻击的发展。8有了NESSIE计划的基础，在2004年启动的欧洲eSTREAM序列密码计划中，不论是面向软件还是面向硬件，其算法设计都有了新的突破。9eSTREAM序列密码计划2004年11月，ECRYPT启动了欧洲序列密码计划（eSTREAM）的研究项目。最终胜出的7个算法：软件硬件RabbitTriviumSalsa20Grainv1SosemanukMICKEYv2HC-12810从以上七个算法可以看出，非线性驱动和非线性迭代已成为国际序列密码设计的主流方向。由于目前主要的密码分析技术都是针对线性驱动的体制，所以，新的设计观念为序列密码分析技术提出了严峻挑战。11（2）序列密码分析态势相关攻击相关攻击源于1985年瑞士学者T.Siegenthaler针对组合生成器提出的“分别征服”攻击。相关攻击是最重要的密钥恢复攻击之一，它利用密码体制中LFSR序列与密钥流序列之间的统计相关性实施攻击。1988年，W.Meier和O.Staffelbach给出的两个快速相关攻击算法从思想上和技术上对T.Siegenthaler的相关攻击进行了很大改进，为此后十余年相关攻击的繁荣奠定了基础。122000年前后，涌现出许多新的快速相关攻击改进算法。法国学者A.Canteaut和M.Trabbia通过寻找反馈多项式的低重倍式(4重或5重)改进了W.Meier和O.Staffelbach的迭代解码算法B。瑞典学者T.Johansson和F.Jönsson通过构造低率的卷积码以及采用高效译码算法改进快速相关攻击。沿着T.Johansson和F.Jönsson的思路，挪威学者H.Molland等通过进一步降低T.Johansson和F.Jönsson卷积码码率来获得更多校验方程，提高快速相关攻击的效果。13代数攻击代数攻击是2003年由N.T.Courtois和W.Meier提出，他们通过布尔函数的低次“零化子”，建立LFSR初态和密钥流之间的超定的低次多变元方程组。随后，N.T.Courtois进一步提出快速代数攻击方法。快速代数攻击在代数攻击的基础上增加对方程的预处理步骤，达到降低方程次数的目的。14代数攻击不仅适用于序列密码，早在1995年，代数攻击就成功用于分析多变元的公钥密码体制。代数攻击的出现使得求解超定方程组的算法成为密码分析者关注的焦点问题之一，促进了有限域上解多变元方程组理论的发展。代数攻击用于序列密码分析约六年时间，但已成为序列密码分析领域极受关注的分析方法。和相关攻击一样，代数攻击能否应用于非线性驱动的序列密码体制是未来序列密码分析的重点研究问题之一。15其它攻击区分攻击是指在统计意义上可以将密钥流序列与随机序列区分。Cube攻击是A.Shamir等提出的一种新型攻击方法，已经被用于攻击MD4的替代算法MD6、eSTREAM最终胜出的算法Trivium等。旁道攻击是利用密码设备在执行密码算法时泄露的物理信息，如电源消耗、运行时间、电磁辐射等，并结合数学统计工具来获取和部分获取密码系统中的秘密参数的一种攻击手段。16三、我国序列密码研究现状我国学者早在二十世纪七十年代就开始了序列密码的研究工作，在序列密码的许多研究领域取得了重要的研究成果，研究论文频频发表在国际密码年会和著名国际刊物上。目前，不仅在某些研究领域保持了先进优势，并且不断开拓新的国际前沿研究方向。17（1）整数剩余类环上线性递归序列二十世纪八十年代，我国学者和俄罗斯学者几乎同时独立提出将整数剩余类环上线性递归序列用于序列密码非线性源，并各自独立证明了整数剩余类环上线性递归序列的一系列重要密码性质。从二十世纪八十年代至今，我国在环上序列的研究方面一直处于国际先进水平。由此可以看出，我国在非线性序列源研究方面的前瞻性。18近五年，该领域的研究得到进一步的发展Z/(pe)上本原序列最高权位序列0元素的局部保熵性质，即两条不同的本原序列，其最高权位序列的0元素分布必不同。X.Y.ZhuandW.F.Qi,UniquenessofthedistributionofzerosofprimitivelevelsequencesoverZ/(pe),FiniteFieldsandTheirApplications,Jan.2005,11(1):30-44.X.Y.ZhuandW.F.Qi.UniquenessofthedistributionofzeroesofprimitivelevelsequencesoverZ/(pe)(II),FiniteFieldsandTheirApplications,2007,13(2):230-248.19Z/(pe)上本原序列在压缩函数g(xe1)(x0,x1,…,xe2)作用下是保熵的X.Y.ZhuandW.F.Qi,ComprssionmappingsonprimitivesequencesoverZ/(pe),IEEETrans.Inform.Theory,Oct.2004,50(10):2442-2448.X.Y.ZhuandW.F.Qi,Furtherresultofcompressingmapsonprimitivesequencesmodulooddprimepowers,IEEETrans.Inform.Theory,August,2007,53(8):2985-2990.T.Tian,W.F.Qi,InjectivityofcompressingmapsonprimitivesequencesoverZ/(pe),IEEETrans.Inform.Theory,August,2007,53(8):2960-2965.20Z/(pe)本原序列在模M压缩后是保熵的，其中M是至少包含一个异于p的素因子的正整数。X.Y.ZhuandW.F.Qi,Onthedistinctnessofmodularreductionsofmaximallengthsequencesmodulooddprimepowers,MathematicsofComputation,2008,77:1623-1637.21对Z/(pq)(p和q是奇素数)上本原序列，模2压缩后是保熵的。H.J.ChenandW.F.Qi,OnthedistinctnessofmaximallengthsequencesoverZ/(pq)modulo2,FiniteFieldsandTheirApplications,2009,1:23-39.22（2）带进位反馈移位寄存器序列研究了FCSR的记忆序列。证明了l-序列的记忆序列的周期达到l-序列自身的周期,并且其元素分布具有半周期互补性质T.TianandW.F.Qi,PeriodandcomplementaritypropertiesofFCSRmemorysequences,IEEETrans.Inform.Theory,2007,53(8):2966-2970.23证明了l-序列的局部分布也是平衡的W.F.QiandH.Xu.PartialperioddistributionofFCSRsequences,IEEETrans.Inform.Theory,2003,49(3):761-765.24进一步完善了l-序列的采样的不平移等价性的结果H.XuandW.F.Qi.AutocorrelationsofmaximumperiodFCSRsequences,SIAMJ.Discr.Math.,2006,20(3):568-577.T.TianandW.F.Qi,Autocorrelationanddistinctionnessofdecimationsofl-sequencesbasedonprimes,SIAMJ.Discr.Math,2009,23(2):805-821.25发现了l-序列的一些统计优势明显的线性关系T.TianandW.F.Qi,LinearitypropertiesofbinaryFCSRsequences,Designs,CodesandCryptography,2009,52:249-262.26给出多条l-序列的模2加的周期T.TianandW.F.Qi,PeriodsoftermwiseexclusiveorsofmaximallengthFCSRsequences,FiniteFieldsandTheirApplications,16(2),2009,214-235.27（3）代数免疫继代数攻击提出后，布尔函数代数免疫的研究倍受关注。我国学者在该研究方面取得以下重要研究成果:28证明了Majority函数是唯一的代数免疫最优的奇数变元对称函数。N.LiandW.F.Qi,SymmetricBooleanfunctionwithmaximumalgebraicimmunitydependingonanoddnumberofvariables,IEEETrans.Inform.Theory,2006,52(5):2271-2273.L.J.Qu,C.LiandK.Q.Feng,AnoteonsymmetricBooleanfunctionswithmaximumalgebraicimmunityonoddnumberofvariables,IEEETrans.Inform.Theory,2007,53(8):2908-2910.29研究了偶数变元代数免疫达到最大的对称布尔函数的一些基本密码性质，如值向量、代数正规型、代数次数等。并且还进一步研究了偶数变元代数免疫达到最大的布尔函数的构造问题。L.J.QuandC.Li,Onthe2m-variablesymmetricBooleanfunctionswithmaximumalgebraicimmunity,ScienceinChinaSeriesF–InformationSciences,2008,51(2):120-127.L.J.Qu,K.Q.Feng,F.Liu,andL.Wang,ConstructingsymmetricBooleanfunctionswithmaximumalgebraicimmunity,IEEETrans.Inform.Theory,2009,55(5):2406-2412.30通过对一个给定的代数免疫最优的布尔函数进行真值表改造,构造出新的仍具有代数免疫最优的函数。N.Li,L.J.Qu,W.F.Qi,G