序列密码中密钥流生成器的安全性研究与分析.pdf

序列密码中密钥流生成器的安全性研究与分析孙菁傅德胜南京信息工程大学计算机与软件学院南京210044摘要：序列密码设计的核心在于密钥流生成器的设计本文分析了基于线性反馈移位寄存器的序列密码密钥流生成器的工作机制在研究Geffe和收缩式非线性组合生成器模型的重构条件之基础上给出了一般情况下非线性组合生成器整体的重构条件。本文的工作对构建安全序列密码体制有很好的指导意义。关键词：序列密码LFSR组合生成器中图分类号TN918ResearchandanalysisonthesecurityofkeygeneratorSUNJingFUDe-shengSchoolofcomputerandsoftwareNanjinguniversityofinformationscienceandtechnologyNanjing210044Abstract:Designofkeygeneratoristhecoreprocessinstreamcipher.ThispaperbasedontheresearchofstreamcipherandthereconstructionconditionofGeffeandshrinkinggeneratorproposedthereconstructionconditionforgeneralnonlinearcombininggeneratorwhichwouldgiveguidingsignificancetothedesignforthesecurestreamciphersystem.KeyWords:streamcipher;LFSR;combininggenerator0引言序列密码密钥流生成器有多种结构多数是用一个或多个具有最大周期的线性反馈移位寄存器（Linear_feedback_shiftLFSR）作驱动器来产生一系列状态序列使之周期最长、统计特性良好；然后这些状态序列经过一个非线性组合函数f后得到高线性复杂度的密钥序列{ki}i≥0。自从线性移位寄存器的有效综合算法提出后[1]人们对单个LFSR的复杂度及相关攻击进行了大量研究包括序列的周期线性复杂度等代数特性和相关函数0-1分布及游程分布等统计特性[2][3][4]但是这些研究只反映了单个LFSR的安全状态并没有涉及整个组合生成器的安全策略。本文主要研究密钥流生成器在多个LFSR下的整体安全状态在研究Geffe和收缩钟控式非线性组合生成器模型的重构条件之基础上给出了一般情况下非线性组合生成器整体的重构条件。1线性反馈移位寄存器1.1LFSR的工作机制线性反馈移位寄存器由n个存储器与一个线性反馈函数组成移位寄存器每次向右移动一位新的最左边的位根据反馈函数计算得到移位寄存器输出的位是最低位[5]。反馈函数是寄存器中某些位的线性函数。每一存储器称为LFSR的一级（或抽头）这些级的内容构成该LFSR的状态每一状态对应于GF（2）上的一个n维向量共有2n种可能的状态。理论上n级LFSR在重复之前最多能产生2n-1位长的状态（除去全零状态）但只有具有一定抽头序列LFSR才能循环的通过所有2n-1位长的状态这种序列称为m序列。为了使LFSR有最大周期抽头必须符合一定规则或者LFSR的特征多项式必须是本原(2n1)多项式不同级数下本原多项式系数见下表1。N次本原多