对称密码学及其应用 第7章 序列密码的设计与分析.ppt

对称密码学及其应用对称密码学及其应用1第七章第七章 序列密码的设计与分析序列密码的设计与分析n序列的随机性序列的随机性n线性反馈移位寄存器线性反馈移位寄存器n线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示nm m序列的伪随机性序列的伪随机性n线性反馈移位寄存器的分析方法线性反馈移位寄存器的分析方法nm m序列密码的破译序列密码的破译n序列的线性复杂度序列的线性复杂度nB-MB-M算法算法 n非线性反馈移位寄存器的序列密码非线性反馈移位寄存器的序列密码n非线性反馈移位寄存器序列非线性反馈移位寄存器序列 n利用进位寄存器反馈的移位寄存器利用进位寄存器反馈的移位寄存器n非线性前馈序列非线性前馈序列 n习题习题对称密码学及其应用对称密码学及其应用21.序列的随机性序列的随机性序列密码中必须解决的问题是：序列密码中必须解决的问题是：n密钥流的质量（随机性）如何刻画？密钥流的质量（随机性）如何刻画？如何保证？如何保证？n无限长密钥流如何产生？无限长密钥流如何产生？n合法用户如何很容易地获得或再生该合法用户如何很容易地获得或再生该密钥流？加密、解密如何同步？密钥流？加密、解密如何同步？对称密码学及其应用对称密码学及其应用3真正的随机序列真正的随机序列n看起来是随机的看起来是随机的n不可预测性不可预测性n不能重复产生不能重复产生n如果采用完全相同的输入对序列发生器操作两如果采用完全相同的输入对序列发生器操作两次，将得到两个不相关的随机序列次，将得到两个不相关的随机序列目的：目的：产生具有随机数统计特性，并且不可再现的数。产生具有随机数统计特性，并且不可再现的数。数学描述：数学描述：随机变量序列随机变量序列12i，其中，其中i（i=1，2，）是）是相互独立的、等概率取值相互独立的、等概率取值0，1的随机变量。的随机变量。对称密码学及其应用对称密码学及其应用4密码学意义上安全的伪随机序列密码学意义上安全的伪随机序列n看起来是随机的看起来是随机的n不可预测性不可预测性n即使给出产生序列的算法或硬件和所有即使给出产生序列的算法或硬件和所有以前产生的位序列的全部知识，也不可以前产生的位序列的全部知识，也不可能通过计算来预测下一个随机位是什么能通过计算来预测下一个随机位是什么对称密码学及其应用对称密码学及其应用5伪随机序列伪随机序列n看起来是随机的看起来是随机的n满足伪随机序列的满足伪随机序列的Golomb三条公设三条公设n0和和1的个数相等的个数相等nr游程基本上占游程总数的游程基本上占游程总数的1/2rn异相自相关函数是一个常数异相自相关函数是一个常数n能通过我们所能找到的所有随机性统计检验能通过我们所能找到的所有随机性统计检验对称密码学及其应用对称密码学及其应用6两个基本概念两个基本概念 定义定义 在序列在序列ki|i=1，2，的周期为的周期为p，在它，在它的一个周期的一个周期kl+1，kl+2，kl+p中，如果：中，如果：kmkm+1=km+2=km+rkm+r+1，l+1m+12，当当1in-2时，时，n长长m序列的一个周期内，序列的一个周期内，长为长为i的的0游程数目等于序列中如下形式的状态数目：游程数目等于序列中如下形式的状态数目：10001*，其中，其中n-i-2个个*可任取可任取0或或1。这种状。这种状态共有态共有2n-i-2个。同理可得长为个。同理可得长为i的的1游程数目也等于游程数目也等于 2n-i-2，所以长为所以长为i的游程总数为的游程总数为2n-i-1。m序列序列是伪随机序列的证明是伪随机序列的证明对称密码学及其应用对称密码学及其应用25 由于寄存器中不会出现全由于寄存器中不会出现全0状态，所以不会出状态，所以不会出现现0的的n游程，但必有一个游程，但必有一个1的的n游程，而且游程，而且1的游程的游程不会更大，因为若出现不会更大，因为若出现1的的n+1游程，就必然有两游程，就必然有两个相邻的全个相邻的全1状态，但这是不可能的。这就证明了状态，但这是不可能的。这就证明了1的的n游程必然出现在如下的串中：游程必然出现在如下的串中：当这当这n+2位通过移位寄存器时，便依次产生位通过移位寄存器时，便依次产生以下状态：以下状态：m序列序列是伪随机序列的证明是伪随机序列的证明对称密码学及其应用对称密码学及其应用26由于由于 ，这两个状态只这两个状态只能各出现一次，所以不会有能各出现一次，所以不会有1的的n-1游程。游程。于是在一个周期内，总游程数为于是在一个周期内，总游程数为m序列序列是伪随机序列的证明是伪随机序列的证明对称密码学及其应用对称密码学及其应用27 Golomb第三公设：第三公设：ai是周期为是周期为2n-1的的m序列，序列，对于任一正整数对于任一正整数(02n-1)，ai+ai+在一在一个周期内为个周期内为0的位的数目正好是序列的位的数目正好是序列ai和和ai+对应位相同的位的数目。对应位相同的位的数目。设序列设序列ai满足递推关系：满足递推关系：ah+n=c1ah+n-1c2ah+n-2cnah故故ah+n+=c1ah+n+-1c2ah+n+-2cnah+ah+nah+n+=c1(ah+n-1ah+n+-1)c2(ah+n-2ah+n+-2)cn(ahah+)m序列序列是伪随机序列的证明是伪随机序列的证明对称密码学及其应用对称密码学及其应用28 令令bj=ajaj+，由递推序列由递推序列ai可推得递可推得递推序列推序列bi，bi满足满足bh+n=c1bh+n-1c2bh+n-2cnbh bi也是也是m序列。为了计算序列。为了计算R()，只要只要用用bi在一个周期中在一个周期中0的个数减去的个数减去1的个数，的个数，再除以再除以2n-1，即即 （证毕）（证毕）m序列序列是伪随机序列的证明是伪随机序列的证明对称密码学及其应用对称密码学及其应用29设设LFSR的反馈系数为的反馈系数为c1,c2,.,cn，即：，即：an+k=c1 an+k-1 +c2 a n+k-2 +cn ak，i=0，1，2，。(1)可以用一个一元高次多项式来表示：可以用一个一元高次多项式来表示：称称这个多项式为这个多项式为LFSR的特征多项式的特征多项式。（*）在在(1)式中两边同时加上式中两边同时加上 得到：得到：令令据据其在输出序列其在输出序列中元素的左右位置，中元素的左右位置，左移一位相当于乘以左移一位相当于乘以2，则有：，则有：线性移位寄存器的特征多项式线性移位寄存器的特征多项式对称密码学及其应用对称密码学及其应用30 注意：注意：线性反馈移位寄存器与特征多项式是线性反馈移位寄存器与特征多项式是一一对应的，如果知道了线性反馈移位寄一一对应的，如果知道了线性反馈移位寄存器的结构，可以写出它的特征多项式，存器的结构，可以写出它的特征多项式，同样可以根据特征多项式画出移位寄存器同样可以根据特征多项式画出移位寄存器的结构。的结构。线性移位寄存器的特征多项式线性移位寄存器的特征多项式对称密码学及其应用对称密码学及其应用31n下面讨论特征多项式满足什么条件时，下面讨论特征多项式满足什么条件时，LFSR的输出序列为的输出序列为m序列。序列。n设设Pn(x)为为n次多项式，则次多项式，则l=mink:Pn(x)|(xk-1)称为称为多项式多项式Pn(x)的阶的阶。阶为。阶为2n-1的不可约的不可约多项式称为多项式称为本原多项式本原多项式。n不可约多项式不可约多项式是指那些不能表示成是指那些不能表示成f(x)g(x)的的形式的多项式。形式的多项式。n例：例：P4(x)=x4+x3+x2+x+1是不可约多项式。是不可约多项式。线性移位寄存器的特征多项式线性移位寄存器的特征多项式对称密码学及其应用对称密码学及其应用32例例5n证明证明P4(x)=x4+x+1是本原多项式，求以它为是本原多项式，求以它为特征多项式的线性移位寄存器的输出序列和周特征多项式的线性移位寄存器的输出序列和周期，该序列是期，该序列是m序列吗？序列吗？对称密码学及其应用对称密码学及其应用33例例5-解解n解：由解：由P4(x)|x15-1，但不存在，但不存在k 31)(ShiftRegister 6)(ShiftRegister 4)(ShiftRegister 2)(ShiftRegister 1)ShiftRegister)&000000001)1);return ShiftRegister&000000001;问题：如果问题：如果LFSRLFSR的级数较多，则效率低下的级数较多，则效率低下对称密码学及其应用对称密码学及其应用38n解决办法：解决办法：n使用汇编语言来实现使用汇编语言来实现n并行运行多个并行运行多个LFSR(16个或个或32个，视计算个，视计算机字长而定机字长而定)n采用字的数组，其长度是采用字的数组，其长度是LFSR的长度，字中的的长度，字中的每位表示不同的每位表示不同的LFSR的相应位的相应位n如果所有的反馈多项式相同，则运行速度非常快如果所有的反馈多项式相同，则运行速度非常快n改变改变LFSR的反馈形式的反馈形式2.4 LFSR的软件实现的软件实现对称密码学及其应用对称密码学及其应用39n也可以改变也可以改变LFSR的反馈形式，如图所示，采用抽头序的反馈形式，如图所示，采用抽头序列中的每一位和发生器的输出相异或，并用异或结果列中的每一位和发生器的输出相异或，并用异或结果取代抽头序列的那一位，同时发生器的输出作为新的取代抽头序列的那一位，同时发生器的输出作为新的最左端位。这种构造方式又称为最左端位。这种构造方式又称为Galois配置配置（Galois Configuration）。）。2.4 LFSR的软件实现的软件实现对称密码学及其应用对称密码学及其应用40Galois LFSR.#define mask 080000057 static unsigned long ShiftRegister=1;void seed_LFSR(unsigned long seed)if(seed=0)/*avoid calamity*/seed=1;ShiftRegister=seed;int modified_LFSR(void)if(ShiftRegister&000000001)ShiftRegister=(ShiftRegister mask 1)|08000000;Return 1;else ShiftRegister=1;return 0;2.4 LFSR的软件实现的软件实现对称密码学及其应用对称密码学及其应用412.4 LFSR的软件实现的软件实现n软件实现软件实现LFSR的一般原则：的一般原则：n如果具有利于移位的硬件，则采用如果具有利于移位的硬件，则采用Fibonacci配置配置n如果使用并行运算，那么采用如果使用并行运算，那么采用Galois配置。配置。对称密码学及其应用对称密码学及其应用423 线性反馈移位寄存器的分析方法线性反馈移位寄存器的分析方法 nm序列密码的破译序列密码的破译n序列的线性复杂度序列的线性复杂度 nB-M算法算法 对称密码学及其应用对称密码学及其应用433.1 m序列密码的破译序列密码的破译 上上面面说说过过，有有限限域域上上的的二二元元加加法法序序列列密密码码是是目目前前最最为为常常用用的的序序列列密密码码体体制制，设设滚滚动动密密钥钥生生成成器器是是线线性性反反馈馈移移位位寄寄存存器器，产产生生的的密密钥钥是是序序列列。又又设设和和是是序序列列中中两两个个连连续续的的长长向量，其中向量，其中对称密码学及其应用对称密码学及其应用443.1 m序列密码的破译序列密码的破译设序列设序列ai满足线性递推关系：满足线性递推关系：可表示为可表示为对称密码学及其应用对称密码学及其应用453.1 m序列密码的破译序列密码的破译或或Sh+1=MSh，其中其中又设敌手知道一段长为又设敌手知道一段长为2n的明密文对，即已的明密文对，即已知知对称密码学及其应用对称密码学及其应用463.1 m序列密码的破译序列密码的破译 于是可求出一段长为于是可求出一段长为2n的密钥序列的密钥序列 其中其中 ,由此可推由此可推出线性反馈移位寄存器连续的出线性反馈移位寄存器连续的n+1个状态：个状态：对称密码学及其应用对称密码学及其应用473.1 m序列密码的破译序列密码的破译做矩阵做矩阵而而若若X可逆，则可逆，则对称密码学及其应用对称密码学及其应用483.1 m序列密码的破译序列密码的破译下面证明下面证明X的确是可逆的。的确是可逆的。因为因为X是由是由S1,S2,Sn作为列向量，要作为列向量，要证证X可逆，只要证明这可逆，只要证明这n个向量线性无关。个向量线性无关。由序列递推关系：由序列递推关系：可推出向量的递推关系：可推出向量的递推关系：对称密码学及其应用对称密码学及其应用493.1 m序列密码的破译序列密码的破译 设设m(mn+1)是使是使S1,S2,Sm线性相关的线性相关的最小整数，即存在不全为最小整数，即存在不全为0的系数的系数l1,l2,lm，其中不妨设其中不妨设l1=1，使得使得即即对于任一整数对于任一整数i有有对称密码学及其应用对称密码学及其应用503.1 m序列密码的破译序列密码的破译 由此又推出密钥流的递推关系：由此又推出密钥流的递推关系：即密钥流的级数小于即密钥流的级数小于m。若。若mn，则得则得出密钥流的级数小于出密钥流的级数小于n，矛盾。所以矛盾。所以m=n+1，从而矩阵从而矩阵X必是可逆的。必是可逆的。对称密码学及其应用对称密码学及其应用513.1 m序列密码的破译序列密码的破译例例6 设敌手得到设敌手得到密文串：密文串：101101011110010和相应的和相应的明文串：明文串：011001111111001，还知道，还知道密钥流是使用密钥流是使用5级线性反馈移位寄存器产级线性反馈移位寄存器产生的。生的。问如何求得反馈寄存器的特征多项式？问如何求得反馈寄存器的特征多项式？对称密码学及其应用对称密码学及其应用523.1 m序列密码的破译序列密码的破译解：解：由由 密文串：密文串：101101011110010 明文串：明文串：011001111111001 得：密钥流：得：密钥流：110100100001011还知道密钥流是使用还知道密钥流是使用5级级LFSR产生的，那么敌手可产生的，那么敌手可用密钥流的前用密钥流的前10个比特建立如下方程：个比特建立如下方程：对称密码学及其应用对称密码学及其应用533.1 m序列密码的破译序列密码的破译即即而而对称密码学及其应用对称密码学及其应用543.1 m序列密码的破译序列密码的破译从而得到从而得到所以所以密钥流的递推关系为密钥流的递推关系为下面验证递推关系公式的正确性：下面验证递推关系公式的正确性：对称密码学及其应用对称密码学及其应用553.2 序列的线性复杂度序列的线性复杂度n定义定义8 一个序列一个序列s=i 0的的线性复杂度线性复杂度（linear complexity）是能产生该序列的）是能产生该序列的LFSR的最小级数，的最小级数，常用常用L(s)表示。表示。n序列的线性复杂度的基本性质；序列的线性复杂度的基本性质；n设设s和和t是是F2上的两个序列。上的两个序列。1.对任何，序列对任何，序列sn=线性复杂度线性复杂度L(sn)满足满足0L(sn)n；2.L(sn)=0，当且仅当，当且仅当sn是长为是长为n的零序列；的零序列；3.L(sn)=n，当且仅当当且仅当sn=0,0,0,1；4.如果如果s是周期为是周期为N的序列，则的序列，则L(sn)N；5.L(s t)=L(s)+L(t)，这里，这里s t表示表示s和和t的逐比特异或。的逐比特异或。对称密码学及其应用对称密码学及其应用56一个n-LFSR（给定结构常数）具有“由一个短的种子产生一个长的序列”的功能：以短的种子作为初态，产生的输出序列可以任意长！上述表明，任一n-LFSR都初步具有作为一个KG的资格；但从作为KG的效用来讲，自然更希望所使用的n-LFSR进一步是m-序列生成器。m序列的特性序列的特性对称密码学及其应用对称密码学及其应用57线性反馈移位寄存器（线性反馈移位寄存器（LFSR）的综合的综合n-FSR的结构常数+初态 n-FSR序列分析综合前面我们讲过，m-序列是满足Golomb三条随机性公设的PN序列，但其不可以作为一个序列密码的密钥序列。因为：对m-序列，知道其少量的比特以后是可以预测的！现在就讲怎么样仅凭已知的少量比特来找出整个序列所满足的线性递推关系。一般地，把有关反馈移位寄存器的求解问题，从正反两个方面分为分析与综合：对称密码学及其应用对称密码学及其应用58线性反馈移位寄存器（线性反馈移位寄存器（LFSR）的综合的综合线性反馈移位寄存器的综合问题就在于根据序列的少量比特求出整个序列所满根据序列的少量比特求出整个序列所满足的线性递推关系足的线性递推关系。一个自然的想法就是：先假定线性递推关系，然后由序列的各项应该适合之而导出线性方程组；但这样的方法有其不易行之处在于：不容易确定所适用的LFSR的级数n，从而就不能导致恰当规模的线性方程组；当上述的n很大时，求解相应规模的线性方程组也很困难。对称密码学及其应用对称密码学及其应用59事实上，对于线性反馈移位寄存器的综合问题已经出现了著名的解法：Berlekamp-Massey迭代算法，简称B-M算法。线性反馈移位寄存器（线性反馈移位寄存器（LFSR）的综合的综合对称密码学及其应用对称密码学及其应用60B-MB-M算法描述算法描述InputInput：S SN N=a=a0 0a a1 1a a2 2a aN-1N-1Step1Step1：置：置f f0 0(x)=1(x)=1，L L0 0=0=0（初值）初值）Step2Step2：设设 ，i=0,1,2,i=0,1,2,n,n（0 0 nNnN）均已求均已求出，且出，且L L0 0 L L1 1 L L2 2 L Ln n。设设 ,由此计算由此计算 。Step3Step3：当：当d dn n=0=0时，取时，取f fn+1n+1(x)=f(x)=fn n(x),L(x),Ln+1n+1=L Ln n。当当d dn n=1=1时，若时，若L Ln n=0,=0,则取则取f fn+1n+1(x)=x(x)=xn+1n+1+1,L+1,Ln+1n+1=n+1=n+1；否则否则,找出找出m(0m(0 mn)mn)使使L Lm m L Lm+1m+1=L Lm+2 m+2=L Ln n,取取f fn+1n+1(x)=f(x)=fn n(x)+x(x)+xn-mn-mf fm m(x),L(x),Ln+1n+1=maxL=maxLn n,n+1-,n+1-L Ln n。对于对于n=0,1,2,n=0,1,2,，重复重复Step2Step2与与Step3Step3，直至直至n=N-1n=N-1OutputOutput：对称密码学及其应用对称密码学及其应用61B-MB-M算法举例算法举例 输入：S8=10101111输出：对称密码学及其应用对称密码学及其应用62有关有关B-MB-M算法的结果算法的结果定理定理1.1.应用B-M算法，若以N长序列SN为输入，得到输出，则以fN(x)为联接多项式的LN-LFSR是产生SN的最短LFSR，且当 时，迭代至第2LN步就得到最终输出，即：。当 时，产生SN的最短LFSR只是上述一个；当 时，产生SN的最短LFSR一共有 个。由上述定理知，在前面的例子中，以f8(x)=1+x3+x4为联接多项式的4-LFSR是唯一的产生S8=10101111的最短LFSR。对称密码学及其应用对称密码学及其应用63有关有关B-MB-M算法的结果算法的结果考虑问题：S6=101011f6(x)=1+x2+x3如何解释？其实，对，由于L6=4，故4-LFSR 0,1,1,0生成S6；对，由于L1+N=1，故1-LFSR0生成S2（规定：f(x)=1产生全零序列）。对称密码学及其应用对称密码学及其应用64有关有关B-MB-M算法的结果算法的结果对于周期序列，也可应用B-M算法求出产生它的最短LFSR的联接多项式，不过须注意：一定得是针对两个周期段去求才正确！定理2.对周期为p的序列a=a0a1a2，应用B-M算法于S2p=a0a1ap-1a0a1ap-1求出时，必f2p(x)的次数必为L2p，且以f2p(x)为联接多项式的L2p-LFSR是唯一的产生a的最短LFSR。对称密码学及其应用对称密码学及其应用65应用应用B-MB-M算法举例算法举例 求产生序列a的最低次多项式，这里 a=111001，a=(111001)解：可见答案为：1+x2+x3；1+x2+x4。对称密码学及其应用对称密码学及其应用66一般的非线性反馈移位寄存器序列一般的非线性反馈移位寄存器序列n例：例：f（x1,x2,x3）=x1+(x2/x3)n小项表示式：小项表示式：f(x1,x2,x3)=x1 x2x3+x1 x2x3+x1 x2x3+x1 x2x3n输出序列：输出序列：0001011100010111n周期：周期：8对称密码学及其应用对称密码学及其应用67利用进位的反馈移位寄存器 FCSRn基本原理图基本原理图 对称密码学及其应用对称密码学及其应用68FCSR的例子的例子Shift Register Carry Register0 0 1 01 0 0 00 1 0 01 0 1 01 1 0 01 1 1 00 1 1 11 0 1 10 1 0 10 0 1 10 0 0 11 0 0 0例：例：n=3级的级的FCSR，抽头在，抽头在第第1位和第位和第2位。初值为位。初值为001，进位寄存器的初值为进位寄存器的初值为0。对称密码学及其应用对称密码学及其应用69FCSR的讨论的讨论n进位寄存器的级数至少为进位寄存器的级数至少为lb t。t为反馈为反馈抽头数抽头数nFCSR的暂态过程的暂态过程nn级级FCSR的最大周期为的最大周期为q-1；其中；其中q是链是链接整数，由抽头决定。即：接整数，由抽头决定。即：q=2q1+22q2+23q3+2nqn-1n不是每个初始状态不是每个初始状态 都能给出最大周期。都能给出最大周期。Shift Register Carry Register 1 0 1 4 1 1 0 2 1 1 1 1 1 1 1 1对称密码学及其应用对称密码学及其应用70FCSR的讨论（续）的讨论（续）nFCSR的可能输出的可能输出n最大周期的一部分最大周期的一部分n在初始暂态之后进入最大周期的循环在初始暂态之后进入最大周期的循环n在初始暂态之后进入全在初始暂态之后进入全0状态状态n在初始暂态之后进入全在初始暂态之后进入全1状态状态nFCSR理论研究内容理论研究内容n给定一个整数给定一个整数q，如何得到抽头位置，可以，如何得到抽头位置，可以构造出最大周期的构造出最大周期的FCSRnFCSR的复杂度的复杂度对称密码学及其应用对称密码学及其应用71内容提要内容提要n利用进位的反馈移位寄存器 FCSR(feedback with carry shift register)n非线性前馈序列非线性前馈序列 n Geffe 发生器发生器n推广的推广的 Geffe发生器发生器nJennings发生器发生器n自采样发生器自采样发生器nBeth-Piper 停走式发生器停走式发生器nAlternating停走式发生器停走式发生器n门限发生器门限发生器对称密码学及其应用对称密码学及其应用72基本概念基本概念n n周期序列线性复杂度周期序列线性复杂度定义：定义：周期序列周期序列kii=0的线性复杂度是能产生的线性复杂度是能产生kii=0的的LFSR的最小级数的最小级数n。显然，显然，n级级m序列的线性复杂度为序列的线性复杂度为n。对称密码学及其应用对称密码学及其应用73基本概念（续）基本概念（续）n相关攻击相关攻击n定义：一个或更多的内部输出序列常常正好定义：一个或更多的内部输出序列常常正好是独立的是独立的LFSR输出输出-与组合密码序列相与组合密码序列相关，并且易受到线性代数的攻击。这一般被关，并且易受到线性代数的攻击。这一般被称为相关攻击（称为相关攻击（correlation attack）。）。n基本思想：识别发生器的输出和它的内部某基本思想：识别发生器的输出和它的内部某一块之间的相关性。然后，通过观察输出序一块之间的相关性。然后，通过观察输出序列，获得关于其内部输出的一些信息。用这列，获得关于其内部输出的一些信息。用这些信息和其他的相关性，搜集其他内部输出些信息和其他的相关性，搜集其他内部输出的相关性，直到整个发生器被破译。的相关性，直到整个发生器被破译。对称密码学及其应用对称密码学及其应用74密钥流生成器的结构密钥流生成器的结构驱驱 动动 器器非非 线线 性性 组组组组 合合 器器 FS1S2SN.ki存储器存储器存储器存储器密钥流生成器组成密钥流生成器组成对称密码学及其应用对称密码学及其应用75问题问题n用一个用一个LFSR是否可以实现生成器的功是否可以实现生成器的功能？能？n用多个用多个LFSR如何来实现生成器的功能如何来实现生成器的功能？对称密码学及其应用对称密码学及其应用76使用一个使用一个LFSR的情况的情况n由由E.J.Groth在在1971年提出年提出n以一个以一个LFSR的多个不同相输出作为驱动序列去控制一个的多个不同相输出作为驱动序列去控制一个非线性组合函数非线性组合函数F，得到非线性输出序列，得到非线性输出序列ki，称这一序，称这一序列产生器为非线性前馈序列产生器，列产生器为非线性前馈序列产生器，F为前馈函数，为前馈函数，ki为前馈序列。为前馈序列。对称密码学及其应用对称密码学及其应用77多个多个LFSR的非线性前馈序列生成器的非线性前馈序列生成器n由多个彼此独立的由多个彼此独立的LFSR的输出作为前馈的输出作为前馈的驱动序列如下：的驱动序列如下：n令令LFSRj(j=1,2,J)的周期为的周期为Pj,则输则输出序列出序列ki的周期：的周期：对称密码学及其应用对称密码学及其应用78Geffe 发生器发生器nb=(a1 a2)(a1)a3)(a1,a2,a3是三个是三个LFSR的输出的输出)nLFSR的长度为的长度为n1,n2,n3 线性复杂度为：线性复杂度为：(n1+1)n2+n1n3n周期是三个周期是三个LFSR的周期的的周期的 最小公倍数最小公倍数n安全性：较弱安全性：较弱n无法抵抗相关攻击无法抵抗相关攻击对称密码学及其应用对称密码学及其应用79推广的推广的 Geffe发生器发生器n共有共有n+1个个LFSR，在，在n个个LFSR中进行选择中进行选择nLFSR1必须比其他必须比其他n个个LFSR运行快运行快log2n倍倍n可能受到相关攻击可能受到相关攻击对称密码学及其应用对称密码学及其应用80Jennings发生器发生器n用一个复合器来组合两个用一个复合器来组合两个LFSRn优点：良好的统计特性优点：良好的统计特性n缺点：无法抵御中间相遇一致性攻击和线性一致性攻击缺点：无法抵御中间相遇一致性攻击和线性一致性攻击对称密码学及其应用对称密码学及其应用81自采样发生器自采样发生器n是由是由LFSR的输出来控制自己时钟的发生器的输出来控制自己时钟的发生器n已提出两种类型已提出两种类型nRueppel自采样发生器自采样发生器nLFSR的输出为的输出为0，LFSR被时钟驱动被时钟驱动d次；次；nLFSR的输出为的输出为1，LFSR被时钟驱动被时钟驱动k次；次；对称密码学及其应用对称密码学及其应用82自采样发生器（续）自采样发生器（续）nChambers和和Gollmann自采样发生器自采样发生器n由由LFSR的几位来控制自己的时钟的几位来控制自己的时钟n思想与思想与Rueppel自采样发生器相同自采样发生器相同n 自采样发生器已被证明是不安全的。自采样发生器已被证明是不安全的。对称密码学及其应用对称密码学及其应用83Beth-Piper 停走式发生器停走式发生器n易于用硬件来实现易于用硬件来实现n抗相关攻击能力差抗相关攻击能力差对称密码学及其应用对称密码学及其应用84Alternating停走式发生器停走式发生器n易于用硬件来实现易于用硬件来实现n具有长周期和大的线性复杂性具有长周期和大的线性复杂性对称密码学及其应用对称密码学及其应用85门限发生器门限发生器n大数目的大数目的LFSR(奇数个奇数个)，LFSR的长度互素，且反馈多项的长度互素，且反馈多项式是本原的，这样可以达到最大周期。式是本原的，这样可以达到最大周期。n过半函数的含义：输出过半函数的含义：输出=半数以上的输入值半数以上的输入值n理论根据：使用多个理论根据：使用多个LFSR，来增加破译这种密码的难度，来增加破译这种密码的难度n无法抵抗相关攻击无法抵抗相关攻击