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

序列密码中密钥流生成器的安全性研究与分析孙菁，傅德胜南京信息工程大学计算机与软件学院,南京210044摘要：序列密码设计的核心在于密钥流生成器的设计，本文分析了基于线性反馈移位寄存器的序列密码密钥流生成器的工作机制，在研究Geffe和收缩式非线性组合生成器模型的重构条件之基础上，给出了一般情况下非线性组合生成器整体的重构条件。本文的工作对构建安全序列密码体制有很好的指导意义。关键词：序列密码，LFSR，组合生成器中图分类号TN918ResearchandanalysisonthesecurityofkeygeneratorSUNJing,FUDe-shengSchoolofcomputerandsoftware,Nanjinguniversityofinformationscienceandtechnology,Nanjing210044Abstract:Designofkeygeneratoristhecoreprocessinstreamcipher.ThispaperbasedontheresearchofstreamcipherandthereconstructionconditionofGeffeandshrinkinggenerator,proposedthereconstructionconditionforgeneralnonlinearcombininggenerator,whichwouldgiveguidingsignificancetothedesignforthesecurestreamciphersystem.KeyWords:streamcipher;LFSR;combininggenerator0引言序列密码密钥流生成器有多种结构，多数是用一个或多个具有最大周期的线性反馈移位寄存器（Linear_feedback_shift,LFSR）作驱动器来产生一系列状态序列，使之周期最长、统计特性良好；然后这些状态序列经过一个非线性组合函数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的特征多项式必须是本原多项式，不同级数下本原多项式系数见下表1。N次本原多项式的个数nnn)12()(，其中为欧拉函数。已经证明，对于任意的正整数n，至少存在一个n次本原多项式，所以对于任意的n级LFSR，至少存在一种连接方式使其输出序列为m序列。m序列有密码学很多优良特性，如平衡性、移位可加性，它是最常采用的扩谱码序列，也是攻击者们致力于分析的序列。表1本原多项式系数表n本原多项式系数n本原多项式系数201C6873253FADF213074B5F95935892EDAC734015A02FC75874527D99F781D275073E876C9DCD9755BEC81BD6CE836B601FB7B391826A7E396521A762CC0F6015D57704E055031A9E62660FF75824EC073FB02B82A49F8016428CF31D321B4DB6B1B853189E29C9F12E75B82CDD51.2LFSR内部特性定理1：GF（p）上的n级LFSR产生的m序列z具有以下性质[5]：（1）z最小周期为pn-1，线性复杂度为n。（2）若LFSR的初始状态为全零，则输出z为全零序列。（3）若LFSR的初始状态为全1，则输出z与输出位的奇偶性相关。（4）对任意,0),(XpGFX在z的一个周期内X出现pn次，0出现pn-1次。（5）如果,),...()...(,111azaaazzzazrjrjjjj则称11...rjjjzzz是一个长为r的a的游程。在序列z的一个最小周期内：游程的总个数为pn-1；对于1≤r≤n-2，每个)(pGFa，长为r的a的游程有（p-1）2pn-k-2个，长为n-1的0游程有p-1个；对于每个0a，长为n-1的a游程有p-2个，长为n的a游程有1个。（6）对于1≤j≤pn-1，令x，y，…z为抽头序列，bjx，bjy，bjz为j轮抽头序列状态值，zj输出bjxbjy…bjz。（7）固定阶数和抽头的LFSR的输出序列中，输出序列的前一段是后一段的输入。LFSR安全分析推论1：对于单个阶长为n的LFSR，假定能够获得输出序列中任意一段长度为n的连续串，根据LFSR的特性（6）、（7），就能够在不知道初始状态的情况下重构出该LFSR的所有输出。如对于阶长为4的LFSR，如图2-1所示，选取本原多项式p(x)=x4+x+1即选取抽头（4，1）使其成为一个m序列，周期为24-1=15，设寄存器初始输入为1010，经过往复循环运算，一个周期内它的输出序列是：101011001000111。a4a3a2a1图1抽头为（4，1）的4级LFSR根据推论1，将任意一段长度为4的连续输出序列放入阶长和本原多项式或抽头均与原始LFSR相同的线性反馈移位寄存器中进行运算，产生的输出序列与原序列相同。该LSFR的输出的表示为：z5=z1z4，z1和z4分别表示当前轮1号、4号寄存器中的值。由此可得，任何单个LSFR的输出都可由上述等式表示，即每一轮的输出都是当前轮抽头异或。2非线性组合生成器安全分析真实设计的序列密码生成器往往采用多个LFSR级联相互反馈来获得更大周期序列和更好的伪随机性特征，加入了钟控或者复合控制器等等，分析起来十分困难。2.1Geffe生成器在Geffe发生器中，三个LFSR的长度分别为n1，n2，n3。若LFSRi的输出序列为{iks}，则输出序列{kz}可以表示为kz=1ks3ks+2ks3ks。如果将整个状态机看成一个特殊结构的LFSR，令其为LFSR4，根据输出模型，可以设定LFSR1、LFSR2、LFSR3的初始输入为未知量，未知量的数量为n1+n2+n3，那么只需获得长n1+n2+n3的输出序列就可以重构这三个LFSR的内部状态。LFSR1LFSR2LFSR3多路复合选择控制}{1kS}{2kS}{3kS图2Geffe发生器2.2收缩式反馈寄存器收缩式反馈寄存器[6]采用不同类型的时钟控制。发生器使用两个LFSR：LFSR1和LFSR2。它们分别按各自时钟运行，LFSR1在时间t-1的输出为1时，LFSR2在时间t输出为密钥流，否则舍去。这种钟控序列具有许多良好的性质，但它局部性质不理想，可测度高[7]。整个状态机可以看作一个特殊设计的LFSR，令其为LFSR3，可知LFSR3的输出与LFSR1和LFSR2相关。若LFSR2的输出属于集合N，LFSR3的输出属于集合S，则S∈N。相同的LFSR不同的初始条件输出的两个序列，其中一个必是另一个的位移。位置值等于初始条件在序列1和序列2中出现的位置差，正数则右移，负数左移。例如，一个n=5，抽头序列为(5,2)的LFSR，对于两种不同的初始输入，其中第二组是第一组左移1位，所得到的输出序列见表2-2。另第一组序列为参考序列，则第二组只需左移1位即可和第一组序列重叠。表2n=5，抽头序列为(5,2)的LFSR输入输出输入输出101011010111011000111110011010010000010100101011101100011111001101001000根据这一分析，可以任意取LFSR1和LFSR2的初始状态，获得三组输出，令LSFR1的输出为M1，LSFR2的输出为N1，LSFR1和LSFR2收缩反馈后最终输出为S1。检查S1是否属于S，如果不属于，让LFSR1时钟延迟一位再计算，得到的输出元素属于集合S2，检查集合S2是否属于集合S，如此循环最多需要x（x=2n-1，n为LFSR的阶数）次就可以重构收缩式反馈发生器。2.3一般情况下非线性组合生成器攻击分析设LFSRi长为li，初始状态为Ki=),...,,(21iliiiaaa，输出序列为),...,,(21iliiisss，非线性组合生成器f（x）的输出即密钥流为=),...,,(21iliiizzz，而且P(ikikzs)=Pi=0.5-εi(i=1，2，…m)。一般情况下，设0.5≥εi≥0，称εi为LFSR的相关系数．为了方便研究，假设LFSR的特征多项式是已知或者公开的，那么密码系统的密钥就是各个LFSR的初始状态。对LFSR的特征多项式是未知的情形，搜索所有可能的特征多项式。假定能获得足够长的明密文比特流，对明密文比特流的对应位置比特相异或，就得到了最终用来分析LFSR的初始状态的部分密钥流。攻击条件如下：（1）已知N长密钥流序列Z=(Nzzz,...,,21)，设LFSRi对应的输出序列是),...,,(21iniiisss。当N接近惟一解距离l／(1-H(pi))（其中H(·)是熵函数）时，攻击的计算复杂度趋于一般的相关攻击的计算复杂度，故假设N≥l／(1-H(pi))。（2）已知非线性组合函数f（x）的输出与LFSRi(i=l，2，⋯，p)输出的相关性：P(ikikzs)=Pi=0.5-εi。（3）已知LFSRi的特征多项式gi(x)及其长度li。攻击目的是从密钥流截断Z=(Nzzz,...,,21)恢复出对应的LFSRi的输出，再由LFSRi的递推式得到初始状态Ki=),...,,(21iliiiaaa。其实仅需要得到LFSRi输出的li个位置上的正确值就可以确定其初始状态，一般是直接恢复对应的LFSRi的输出),...,,(21iliiisss[8]。2.1节中已谈到，由LFSRi的线性递推式，容易得到)(iijljs可以由),...,,(21iliiisss线性表示，则对于),...,,(21iNiisss=),...,,(21iliiisssGi其中Gi=iNlililiNiiiNii那么),...,,(21iNiisss就可以看成一个[N,li]线性分组码，信息组是),...,,(21iNiisss，Z=(Nzzz,...,,21)可以看成),...,,(21iNiisss通过一个相关概率为Pi=0.5-εi的二进制对称信道(BinarySymmetricChannel,BSC)后的加噪声接收序列[9]，也就是Z=(Nzzz,...,,21)=),...,,(2211NiNiieseses其中e1，e2…，eN是独立同分布的随机变量，而且P(ek=1)=Pi=0.5一εi，P(ek=1)=1/2+εi这样就可使用纠错码的技术恢复[9]。3小结本文介绍了序列密码中密钥生成器工作原理——LFSR的工作机制，分析了密钥生成器两大组成部分LFSR和Geffe、钟控收缩生成器等非线性组合生成器的安全性，在此