第4章-序列密码变换理论课件

4.1序列密码的基础理论

4.2密钥序列的产生方法

4.3序列密码的安全性

4.4序列密码的应用第4章序列密码变换理论4.1序列密码的基础理论序列密码又称流密码(StreamCipher)，其加密方式是用密钥序列z=z1z2…的第i个符号加密明文序列m=m1m2…的第i个符号，即

在序列密码中，第i个密钥zi由第i时刻密钥生成器的内部状态和初始密钥K决定。密码的安全性主要取决于所用密钥的随机性，所以设计序列密码的核心问题在于设计随机性较好的密钥序列生成器。密钥序列生成器可看做是一个有限状态自动机，由输出符号集Γ、状态集Δ、状态转移函数f、输出函数g和初始状态σ0所组成，如图4-1所示。图4-1密钥序列生成器序列密码可分为两类：同步流密码(SynchronousStreamCipher)和自同步流密码(Self-SynchronousStreamCipher)，前者的密钥序列独立于明文和密文，后者的密钥序列与已产生的一定数量的密文有关。同步流密码的加密过程可描述为这里，σ0是初始状态，可以由密钥K确定；f是状态转移函数;g是产生密钥序列的函数;E是由密钥序列和明文序列产生密文的函数。在同步序列密码中，只要发送端和接收端有相同的初始密钥和初始状态，就能产生出相同的密钥序列，因此说收、发双方的密钥生成器是同步的。其优点是无错误传播，一个传输错误只能影响一个符号，不会影响后继的解密结果。自同步序列密码的加密过程可描述为其中，σ0=(c－t，c－t+1，…，c－1)是非秘密的初始状态，是初始密钥;其余符号与同步序列密码中的含义相同。4.1.1周期序列的极小多项式及m序列通常，密钥流生成器中的驱动部分是一个反馈移位寄存器。线性反馈移位寄存器LFSR(LinearFeedbackShiftRegister)的理论非常成熟，它的实现简单、速度快、便于分析，因而成为构造密钥流生成器最重要的部件之一。移位寄存器是一种有限状态自动机，它由一系列的存储单元、若干个乘法器和加法器通过电路连接而成。假设共有n个存储单元(此时称该移位寄存器为n级)，每个存储单元可存储一比特信息，在第i时刻各个存储单元中的比特序列(aiai+1…ai+n－1)称为移位寄存器的状态，(a0a1…an－1)为初始状态。在第j个时钟脉冲到来时，存储单元中的数据向前移动一位，状态由(ajaj+1…aj+n－1)变为(aj+1aj+2…aj+n)，同时，按照固定规则产生输入比特和输出比特。图4-2描述了GF(2)上的n级LFSR。图4-2GF(2)上的n级LFSR产生输入数据的变换规则称为反馈函数。给定了当前状态和反馈函数，可以唯一确定输出和下一时刻的状态。通常，反馈函数是一个n元布尔函数。

定义4-1

设LFSR的输出序列为a=a0a1a2…，则称满足对任意i∈Z+，ai=ai+p的最小正整数p为序列的周期。具有有限周期的序列称为周期序列。更一般地，如果存在一个下标i0，满足ai+p=ai(对所有i≥i0成立)则称序列a是周期为p的终归周期序列。非终归周期序列的周期定义为无穷大。通常我们将形如a0a1…的序列称为半无限序列，记作a∞，而将形如a0a1…an－1a0a1…an－1…的序列称为周期为n的周期半无限序列，记作(an)∞。一个n级LFSR的输出序列的最长周期由以下定理确定。定理4-1

n级LFSR的周期≤2n－1。周期是衡量序列伪随机性的一个重要标准，要产生性能较好的密钥序列，要求作为密钥发生器的驱动部分的移位寄存器有较长的周期。除此之外，序列的随机性还用游程分布和周期自相关函数来度量。

定义4-2

在序列a∞中,若有at－1≠at=at+1=…=at+l－1≠at+l，则称(xt，xt+1，…，xt+l－1)为一个长为l的游程。

定义4-3

设序列(an)∞的周期为p，定义周期自相关函数为其中，A=|{0≤i＜p;ai=ai+j}|;D=|{0≤i＜p;ai≠ai+j}|。若p|j，则R(j)为同相自相关函数，此时A=p，D=0，故R(j)=1;若p

j，则R(j)为异相自相关函数。

Golomb对于二进制序列的随机性提出了三条假设［4］，满足这些假设的序列就被视为具有较强的随机性，或称其为伪随机序列(Pseudo-RandomSequence)。这三条假设是：

(1)若序列的周期为偶数，则在一个周期内，0、1的个数相等；若序列的周期为奇数，则在一个周期内，0、1的个数相差1。

(2)在一个周期内，长度为l的游程数占游程总数的，且对于任意长度，0游程与1游程个数相等。

(3)所有的异相自相关函数值相等。这三条假设也可以推广到GF(q)上的序列。

LFSR可以用线性函数递归地定义，末端存储器的输入引入多项式f(x)=c0+c1x+c2x2+…+cn－1xn－1其中，未定元x(xak=ak－1)称为延迟算子。f(x)称为LFSR的联结多项式。f(x)的互反多项式称为LFSR的特征多项式。已知二元周期序列a=a0a1a2…，其周期p(a)=L，显然，由联结多项式为1+xL－1的L级LFSR(称为纯轮换移位寄存器)可以产生序列a，联结多项式为1+x2L－1，1+x3L－1，…的LFSR也可以产生a。我们将能产生a的LFSR的联结多项式组成的集合记作J(a)：J(a)={g(x)|g(x)∈F2［x］，g(x)a=0}

设ma(x)是J(a)中次数最低的首一多项式，则J(a)={h(x)ma(x)|h(x)∈F2［x］}即J(a)中的多项式都是ma(x)的倍式。事实上，可以证明J(a)是多项式环GF(2)［x］的一个理想，其生成元为ma(x)。通常称ma(x)为周期序列a的极小多项式，也称极小联结式。显然，用ma(x)作为联结多项式产生序列a是效率最高的一种方案。由于序列的周期与其联结多项式密切相关，下面我们介绍多项式的周期，并用多项式的周期来研究序列的周期。

定义4-4

设g(x)为GF(2)上的多项式，deg(g(x))≥1，g(0)≠0，使g(x)|(1－xL)成立的最小正整数L称为g(x)的周期(又称阶或指数)，记作p(g)。注：

如果g(0)=0，则可将g表示为如下形式：g(x)=xlh(x)h(0)≠0此时，g(x)的周期定义为h(x)的周期。如果LFSR的联结多项式中的cn－1≠0，则称该LFSR是非退化的。

定理4-2

设ma(x)是非退化LFSR产生的序列a的极小多项式，则p(a)=p(ma)，即a的周期等于多项式ma(x)的周期。由定理4-2知，n级LFSR的极小多项式周期的上界与其输出序列的周期上界相同，均为2n－1。设f(x)∈F2［x］，deg(f(x))≥1，如果f(x)不能分解为GF(2)中两个非平凡多项式的乘积，则称f(x)是GF(2)上的不可约多项式(或既约多项式)。如果f(x)是GF(2)上的n次不可约多项式，并且其周期达到上界2n－1，则称f(x)是GF(2)上的一个n次本原多项式。

定理4-3

设LFSR的联结多项式f(x)是GF(2)上常数项为1的既约多项式，则对于LFSR的任一非0输出序列a，有ma(x)=f(x)，并且p(a)=p(f)。定义4-5

周期为2n－1的n级LFSR的输出序列称为m序列。

m序列是由n级线性移位寄存器所能产生的最长周期序列，同时，它也是研究最为成熟的序列。除了具有最长周期之外，它还有许多良好的伪随机性质，因而在密码学和扩频通信等领域中得到了广泛应用。m序列的基本特性由以下定理给出[2]。定理4-4

GF(q)上的n级m序列a∞具有以下性质：

(1)a∞的周期为qn－1，线性复杂度为n。

(2)对任意x∈GF(q)，x≠0，x在a∞的一个周期内出现qn－1次，0出现qn－1－1次，特别地，GF(2)上的m序列在一个周期内0的个数为2n－1，1的个数为2n－1－1。

(3)a∞的极小多项式生成的所有非0序列均为m序列，它们是a∞的平移序列。

(4)设(a(j))∞(j=1，2，…，k)为a∞的k个平移序列，任取k个常数xj∈GF(q)，则序列

或为全0序列，或为a∞的一个平移序列。

(5)对任意k(1≤k≤n)，称为序列a∞的一个k维状态向量。在连续qn－1个k维状态向量中，GF(q)k中的每个非0向量出现qn－k次，0向量出现qn－k－1次。

(6)如果aj=aj+1=…=aj+k－1=x∈GF(q)，且aj－1≠x，aj+k≠x，则称(ajaj+1…aj+k－1)是一个长为k的x游程。将序列a∞的一个周期首尾相连，则游程分布如下：①游程的总数为qn－1；②1≤k≤n－2时，对x∈GF(q)，长为k的x游程有(q－1)2qn－k－2个；③长为n－1的0游程有q－1个；④对x≠0，长为n－1的x游程有q－2个，长为n的x游程有1个。

(7)设序列a∞的h间隔采样序列为a(h，d)∞，即a(h，d)∞=adad+had+2h…，则a(h，d)∞是m序列当且仅当h与qn－1互素。当gcd(h，qn－1)=1时，m序列a(h，d)∞的极小多项式与起始采样位置d无关，仅仅与采样间隔h有关；不同的采样间隔对应着不同的极小多项式。

(8)对任意h=1，2，…，qn－2，d=0，1，…，qn－2且gcd(h，qn－1)=1，h间隔采样序列a(h，d)∞遍历了所有的n级m序列。下述定理给出了产生m序列的充要条件。

定理4-5

设GF(2)上n级LFSR的联结多项式为f(x)，用G(f)表示可以由此LFSR产生的全部序列集合，则G(f)中的非零序列均为n级m序列的充要条件是f(x)为GF(2)上的n次本原多项式。根据定理4-5，可将产生n级m序列的问题归结为求GF(2)上n次本原多项式这个纯代数问题，这属于近世代数的内容，在此不加详述。

LFSR的综合问题是指根据序列中的少量比特求出整个序列所满足的线性递推关系，这个问题可以用Berlelcamp-Massey算法(简称B-M算法)解决[6-7]。根据B-M算法，对于任意n级LFSR,连续抽取序列的2n项之后，都可以求出产生该序列的联结多项式。该算法以长为N的二元序列a0，a2，…，aN－1为输入，输出产生该序列的最短LFSR的特征多项式fN(x)及其阶数lN。

B-M算法输入：N，序列a0，a1，…，aN－1。第一步：n←0，〈f0(x)，l0〉←〈1，0〉。第二步：计算dn=fn(D)an，其中，D为延迟算子(Dak=ak－1)。

(1)当dn=0时，〈fn+1(x)，ln+1〉←〈fn(x)，ln〉转第三步；

(2)当dn=1，且l0=l1=…=ln=0时，〈fn+1(x)，ln+1〉←〈1+xn+1，n+1〉转第三步；

(3)当dn=1，且lm<lm+1=lm+2=…=ln(m<n)时，

第三步：若n<N－1，n←n+1，转第二步。输出：〈fN(x)，lN〉。

B-M算法的时间复杂性为O(N2)，空间复杂性为O(N)。

B-M算法广泛应用于BCH码的译码中。一个二元随机序列a0a1a2…可视作一个二元对称信源的输出，当前输出位an与以前输出段a0a1…an－1之间是完全独立的，因此，即使已知a0，a1，…，an－1，an仍是不可预测的。而对于n级m序列，由B-M算法，只要得知其前2n位，就能以较快的速度求出序列的任一位。4.1.2序列的线性复杂度

度量有限长或周期序列的随机性的方法有很多，但最常用的方法是由Lempel和Ziv建议的“线性复杂度”方法［8］，用产生该序列的最短LFSR的长度来度量，这种方法本质上衡量了序列的线性不可预测性。

定义4-6

一个有限序列a=a0a1…at的线性复杂度，是指对于选定的初始状态，生成序列a所需要的线性反馈移位寄存器的最小阶数，记作C(a)。对于全0序列，约定其复杂度为0。

定理4-6

设a=a0a1a2…是二元周期序列，且序列a的线性复杂度C(a)=L≥1，则只要知道a中任意相继的2L位就可确定整个序列及产生a的极小多项式。事实上，B-M算法给出了确定序列线性复杂度的有效方法，由于B-M算法可以求得任一给定序列的线性复杂度，从而使序列的线性复杂度成为同步序列密码的一个重要强度指标。在序列密码中，线性复杂度小的序列不能用作密钥序列，但也不是说，线性复杂度大的序列就一定能作为密钥序列。比如周期为p的序列：000…0100…10如果p很大，则产生该序列的LFSR长度也很大，然而该序列显然不能作为密钥序列。任何周期序列的线性复杂度显然不超过它的周期。此外还可以利用矩阵的秩来研究序列的线性复杂度。

定理4-7

设域GF(q)上的序列a=a0a1…an－1，则a的线性复杂度等于矩阵Ga当Δ1，Δ2，…，Δn－1取遍GF(q)中所有值时的最小秩。

证明:设Ga的最小秩为r(Ga)，将矩阵Ga的第一行至第n行分别标记为0至n－1。若a的线性复杂度C(a)=l，则存在线性递推关系:

(4-1)从而对于l≤i≤n－1，只要适当地选择Δ1，Δ2，…，Δn－1，便可将Ga的第i行表示为前面l行的线性组合，因此r(Ga)≤1。但由线性复杂度的定义，l是使式(4-1)成立的最小整数，因而也是第l行的前n－l个分量能够表示成前面各行的对应分量线性组合的最小整数。故前l行线性独立，从而r(Ga)≥l，故r(Ga)=l。定理4-7描述了有限长序列的线性复杂度的秩表示，下面讨论无限序列的线性复杂度的秩表示。

定理4-8

一个周期半无限序列(an)∞的线性复杂度等于矩阵的秩，即C((an)∞)=rank［M(an)］这里，Si(a)表示序列a循环左移i位得到的序列，称矩阵M(an)为循环矩阵。

证明:

在周期半无限序列(an)∞=a0a1…an－1a0a1…an－1…中，ai=ai+n(i≥0)。显然，(an)∞的线性复杂度至多为n，如果C((an)∞)=l，则对1≤i<∞，式(4-1)必成立。而该周期序列的线性复杂度是l当且仅当对序列中n个连续位，式(4-1)成立。为了使i≥l时，式(4-1)也成立，则(an)∞必须满足以下的矢量方程:(4-2)因此，C((an)∞)是使式(4-2)成立的最小l。如果C((an)∞)=l，则l是使M(an)的第Sl(a)行为前l行的线性组合的最小整数，也是式(4-2)成立的最小整数，因此rank［M(an)］≥l。另一方面，对式(4-2)两边同时乘以Sj，得上式表明，M(an)的每一行与以前各行线性相关，因此rank［M(an)］≤l。由此得到rank［M(an)］=l，从而C((an)∞)=rank［M(an)］。线性复杂度是衡量序列密码安全性的重要指标，但是要衡量一个密钥序列的安全性，仅用线性复杂度是远远不够的，原因在于线性复杂度严格局限于线性方式。20世纪80年代末至今，随着频谱理论在密码学中的应用，人们又提出了线性复杂度轮廓、跃复杂度、重量复杂度、球体复杂度、k错复杂度、变复杂度距离、定复杂度距离、球周期、非线性复杂度等多种度量序列随机性和稳定性的指标，使序列密码的研究日趋完善。4.1.3和序列与乘积序列序列密码中的密钥流序列通常由多个序列经过一些简单运算得到，因而研究序列间的运算规律有着重要的密码学价值。本节简要介绍序列的加法、Hadamard乘法及卷积运算的概念及这些运算对于序列的随机性，特别是周期和线性复杂度的影响。为了进一步分析序列的性质，此处引入生成函数的概念。

定义4-7

设(an)∞=a0a1…an－1a0a1…an－1…为GF(q)上的周期序列，(an)∞的生成函数定义为如下的形式幂级数:这里x为未定元。生成函数与序列是一一对应的。设B(x)、C(x)为GF(q)上的多项式，如果B(x)C(x)=1，则称B(x)和C(x)互为乘法逆元素。

定理4-9

形式幂级数:有乘法逆元素当且仅当b0≠0。证明:如果存在使得B(x)C(x)=1，则下述方程成立：由第一个方程知b0≠0，且c0由第一个方程唯一确定；再由第二个方程和c0唯一确定出c1。一般而言，利用第一个方程和递归关系式：可以确定出所有的cn，所得到的形式幂级数C(x)即为B(x)的乘法逆元。若B(x)的乘法逆元存在，则其必是唯一的，在这里用符号表示B(x)的乘法逆元。对A(x)∈GF(q)［x］，我们用表示A(x)与的乘积。

定理4-10

设GF(q)上的周期序列(an)∞满足齐次线性递归关系式:

(4-3)则ga(x)可以表示为有理分式的形式，即(4-4)其中，

(4-5)

反之，若r(x)是GF(q)上的一个次数小于n的多项式，且f(x)由式(4-5)给出，则由式(4-4)所定义的形式幂级数是一个满足递归关系式(4-3)的齐次递归序列的生成函数。证明:由于

(4-6)如果(an)∞满足式(4-3)，则当j≥n时，式(4-6)右端xi项的系数为零，因而f(x)ga(x)=r(x)。由定理4-9知，f(x)在GF(q)［x］中有乘法逆元，故式(4-4)成立。反之，由式(4-6)知，只有当对所有j≥L都成立时，f(x)ga(x)的次数才小于L，从而ga(x)的系数序列满足递归关系式(4-3)。上述定理表明，以f(x)为特征多项式的L阶齐次线性递归序列和以f(x)为分母的有理分式之间存在着一一对应关系。当f(x)与r(x)互素时，称分式为既约有理分式。序列的相加是指序列中的对应分量分别相加，它是最简单的一种序列运算。

定理4-11

设为GF(q)上的k个周期序列，其周期分别为n1,n2,…,nk，生成函数分别为f1(x)，f2(x)，…，fk(x)，再设分别为其生成函数的既约有理分式表示，定义k个序列的和序列为，即令则有:

(1)序列s的极小多项式

；

(2)序列s的周期p(s)≤lcm{n1，n2，…，nk}，当f1(x)，…，fk(x)两两互素时等号成立；

(3)序列s的线性复杂度，当且仅当f1(x)，…，fk(x)两两互素时等号成立。上述定理表明，在序列密码体制中，如果利用多个序列的和作为密钥序列，则一般情况下其周期和线性复杂度会比单个序列有所增加，所以相加是一种有效的序列运算方法。更有意义的序列运算是序列的Hadamard乘积和序列的运算。

定义4-8

GF(q)上的两个周期序列(an)∞和(bm)∞的Hadamard乘积定义为t=(an)∞×(bm)∞

ti=aibi;i=0，1，…两个序列集合A和B的Hadamard乘积定义为T=A×B={(an)∞×(bm)∞：(an)∞∈A，(bm)∞∈B}

定理4-12

设(an)∞与(bm)∞为GF(q)上的两个周期序列，则其乘积序列t的线性复杂度满足C(t)≤C((an)∞)·C((bm)∞)

定义4-9GF(q)上的两个周期序列(an)∞和(bm)∞的卷积序列定义为

关于卷积序列的周期和线性复杂度有以下结论。

定理4-13

设(an)∞与(bm)∞为GF(q)上的两个周期序列，其生成函数的既约有理分式分别为，令g(x)=gcd(fa(x)fb(x)，ra(x)rb(x))，再设ω为(an)∞与(bm)∞的卷积序列，则有:

(1)ω的周期p(ω)≤nm，当gcd(fa(x)，rb(x))=1，gcd(fb(x)，ra(x))=1且gcd(n，m)=1时等号成立；

(2)ω的线性复杂度C(ω)≤C((an)∞)+C((bm)∞)，当且仅当gcd(fa(x)，rb(x))=1且gcd(fb(x)，ra(x))=1时等号成立。从上述定理可以看出，序列间进行相加、相乘和卷积运算都能使周期和线性复杂度提高。这些运算各有优缺点。在实际应用中，常常利用各种运算的复合使最终得到的密钥序列具有良好的随机性。本节并未给出定理4-11、4-12及4-13的证明，有兴趣的读者可以参阅参考文献［1-2］。4.1.4密钥序列的稳定性周期序列的稳定性主要考虑当改变每个周期段相应的一些元素后，序列的各个随机性指标(如周期、线性复杂度等)的变化情况。为了衡量序列线性复杂度的稳定性，丁存生等提出了重量复杂度和球体复杂度两个稳定性度量指标［9］，随后为了进一步分析序列密码的稳定性，又提出了定复杂度距离和变复杂度距离等指标。本节对此作简要介绍。

定义4-10

设(an)∞为GF(q)上的周期序列，对于非负整数u，(an)∞的重量复杂度和球体复杂度分别定义为其中，WH((tn)∞)表示周期序列(tn)∞的Hamming重量。

引理4-1

设(an)∞为GF(2)上的周期序列，(tn)∞为(an)∞的补序列，则C((an)∞)－1≤C((tn)∞)≤C((an)∞)+1

证明:

设序列(an)∞的极小多项式为f(x)，则易知(1+x)f(x)必为(tn)∞的一个特征多项式，因此C((tn)∞)≤C((an)∞)+1，由对称性知C((an)∞)≤C((tn)∞)+1。

定理4-14

设(an)∞、(tn)∞为GF(2)上的周期序列，an=a0a1…an－1，u为非负整数，则有:

(1)WC0((an)∞)≤C((an)∞)；

(2)；

(3)C((an)∞)－1≤WCn((an)∞)≤C((an)∞)+1；

(4)WCu((an)∞+(tn)∞)≤WCu((an)∞)+WCu((tn)∞)

证明:(1)是显然的。若取(tn)∞为(an)∞的补序列，则(an)∞+(tn)∞为全1序列，由重量复杂度的定义，(2)显然成立。取(tn)∞为全1序列,则(an)∞+(tn)∞是(an)∞的补序列,(3)得证。取(ωn)∞为GF(2)上的周期序列，ωn=ω0ω1…ωn－1，且WH(ωn)=u，则由于C((an)∞+(tn)∞)≤C((an)∞)+C((tn)∞)因此从而(4)成立。

定理4-15

设(an)∞和(bn)∞是GF(q)上的周期序列，分别为其生成函数的既约有理分式表示，则对任意非负整数u，有特别地，当u=1时，有其中，。定理4-15给出了重量复杂度和球体复杂度的确切表达。其详细证明见参考文献［1］。4.2密钥序列的产生方法序列密码主要有四种设计方法：系统论方法、复杂性理论方法、信息论方法和随机化方法。在序列密码设计中，最关键的问题是设计良好的伪随机序列作为密钥。4.1.1节中指出，n级m序列是以n次不可约多项式作为联结多项式所能生成的最长周期序列。m序列具有许多优良的密码学性质，但在所有相同周期的序列中线性复杂度最低,因此一般不直接用作密钥序列。为了构造线性复杂度较高的序列，传统的方法主要有两类。第一类是将m序列作为驱动序列，进行适当的变换或组合，在提高线性复杂度的同时，保留m序列的其它较好的伪随机性。第二类是以计算上困难问题(如分解大整数、离散对数问题等)为基础构造的伪随机序列，如Shamir利用大数分解问题构造了一种伪随机数生成器［10］。通常第二类方法的计算量较大，不适合直接用作密码体制中的密钥序列，但可用于消息认证等领域。第一类伪随机数生成方法主要包括以下三种：

(1)非线性组合。设为GF(q)上的k个m序列，f(x)为GF(q)上的k元非线性函数，令，则称(tn)∞为非线性组合序列，称为驱动序列。特别地，当k个m序列互为平移序列时，f(x)的输出序列(tn)∞称为非线性前馈序列。

(2)多路复合序列。用一个LFSR的输出控制其它LFSR的输出，产生的序列称为多路复合序列。

(3)钟控序列。用某些m序列的输出控制另一些m序列生成器的行为，所产生的与时钟脉冲有关的输出序列称为钟控序列。4.2.1前馈序列本节介绍由LFSR的输出序列经过非线性变换而得到的前馈序列，后两节介绍多路复合序列和钟控序列。基于m序列的前馈序列可以分为两大类：第一类由一个m序列经过非线性组合电路生成；第二类由若干个不同的m序列经过非线性化生成。设序列a∞为n级m序列，g(x)为非线性组合函数，其输出序列为t∞，则第一类前馈序列生成器如图4-3所示。图4-3第一类前馈序列生成器图4-3中，输出序列t∞即为前馈序列。关于第一类前馈序列的密码学特性有以下结论：

定理4-16

基于GF(2)上的n级m序列的二元前馈序列(tn)∞的线性复杂度满足:其中，k是非线性组合函数g(x)的次数。

定理4-17

若前馈序列生成器中的非线性函数次数为k，且具有如下形式：其中，ci∈GF(2)，i=0，1，…，n－k，且ci不全为零;g1(x0，…，xn－1)是次数小于k的布尔函数。则由g(x0，…，xn－1)产生的前馈序列t∞的线性复杂度满足:

定理4-18

设布尔函数g(x0,…,xn－1)=xr+g1(x0,x1,…,xr－1,xr+1,…,xn－1)，r=0，1，…，n－1，则以g为前馈函数所产生的输出序列在一个周期内，0、1个数相差不会超过1。第二类前馈序列生成器的构成如图4-4所示。图4-4第二类前馈序列生成器关于第二类前馈序列有以下相关结论：

定理4-19

若g(x)的输入序列均为m序列，各个m序列的周期分别为n1，n2，…，nk，且对i≠j，i，j∈{1，2，…，k}，有(ni，nj)=1，则输出序列t∞的周期为

一种典型的前馈序列是由Olsen和Scholtz等于1982年为减少通信系统中的干扰而构造的Bent序列［12］，Kumar等人分析了这类序列的线性复杂度［13］，由于Bent序列在生成过程中利用Bent函数滤波并具有可控的线性复杂度，因而在实际中得到了较广泛的应用。

设n>8，n=4k，m=2k，2<d≤k，再设c∈GF(2)m，定义d次函数f(x)：GF(2)m→GF(2)，

(4-7)其中，x=(x(1)，x(2))∈GF(2)m，x(1)，x(2)∈GF(2)k，x(1)=(x1，x2，…，xk)，xT为x的转置，则显然f(x)是GF(2)m上的Bent函数。

定义4-11

设a∞={a(t)|t=0，1，2，…}为GF(2)上的n级m序列，为a∞的平移序列，令其中，函数f(x)如式(4-7)中所定义，则序列s∞={s(t)|t=0，1，2，…}称为一个Bent序列。参考文献［13］及［1］中给出了Bent序列线性复杂度的下界值。

定理4-20Bent序列的线性复杂度

。此外，典型的前馈序列还有几何序列、No序列等，详细构造可见参考文献［2］。4.2.2多路复合序列多路复合序列生成器涉及到多个LFSR，其中一个LFSR用于控制其它LFSR的输出。常见的多路复合序列有Geffe序列、J-K触发器及Pless序列等。

1.Geffe序列

Geffe序列生成器由三个LFSR组成，其中LFSR2作为控制生成器使用，如图4-5所示。图4-5Geffe序列生成器(一)当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。若设LFSRi(i=1，2，3)的输入序列为a(i)，输出序列为b，则有

Geffe序列生成器也可以表示为如图4-6所示的形式。图4-6Geffe序列生成器(二)图中，LFSR1和LFSR3作为多路复合器的输入；LFSR2控制多路复合器的输出。

定理4-21

在如图4-6所示的Geffe序列生成器中，设LFSRi(i=1，2，3)的特征多项式分别为di次本原多项式，且di两两互素，则所生成的Geffe序列的周期为，线性复杂度为(d1+d3)d2+d3。

Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的，因而不失为一种理想的伪随机序列。

2.J-K触发器

J-K触发器如图4-7所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck－1。图4-7J-K触发器设J、K端的输入分别为x1和x2，则由此可得J-K触发器的真值表如表4-1所示。利用J-K触发器可以构造非线性序列生成器，如图4-8所示。图4-8利用J-K触发器构造的非线性序列生成器图中，a∞、b∞为驱动序列，且

(4-8)

设驱动序列a∞和b∞分别为n1级和n2级m序列，如果n1、n2互素且a0+b0=1，则序列c∞的周期为

。由式(4-8)易知:因此，如果知道序列c∞中两个相邻位的值ck－1和ck，就可以推断出ak或bk。进而可以由足够多的这类信息分析得到序列a∞和b∞。为了克服这个缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器［14］。

3.Pless生成器

Pless生成器由八个LFSR、四个J-K触发器和一个循环计数器构成，由循环计数器进行选通控制，如图4-9所示。图4-9Pless生成器4.2.3钟控序列钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图4-10所示。

图4-10钟控序列当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2，因此LFSR2重复输出前一位。输出序列c∞称为钟控序列。设LFSR1和LFSR2的输出序列分别为，周期分别为p1和p2，钟控序列c∞的周期为p3，则有如下关系：其中，。再设的极小多项式分别为GF(2)上的本原多项式f1(x)和f2(x)，deg(f1)=d1，deg(f2)=d2，且d1|d2，则

，由m序列的性质知，从而gcd(w，p2)=1，所以

此外，也可推导出c∞的线性复杂度为

，极小多项式为

。在实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型。典型的钟控序列有Jennings复合序列［15］、停—走生成器(stop-and-gogenerator)［16］、Gunther生成器［17］及缩减序列［18］。以下仅对停—走生成器做一简要介绍，其它序列的具体构造请参考有关文献。

定义4-12

设GF(2)上的两个n级m序列为a∞和b∞，它们的极小多项式分别为f(x)和g(x)，定义整数函数G(t)为(4-9)令

，则序列u∞=u0u1u2…称为停—走序列。所谓停—走序列是指由序列a∞控制b∞的停或走而生成的序列，实际上是由a∞控制的对b∞的不等距采样序列。其周期和线性复杂度由下述定理给出。

定理4-22

停—走序列u∞的极小多项式为，周期为(2n－1)2，线性复杂度为n(2n－1)。停—走序列的概念可以进一步推广到两个级数不同m序列或者多个同级m序列的情形。定理4-23设a∞为GF(2)上的n级m序列，b∞为GF(2)上的r级m序列，函数G(t)如式(4-9)中定义，序列u∞=u0u1u2…定义为ut=bG(t)

t=0，1，2，…则u∞的线性复杂度为n(2r－1)。

定理4-24

设

为GF(2)上的k个n级m序列，如果将这k个序列用停—走生成器进行级联，即用

控制得到序列控制

得到序列控制

得到序列，则的线性复杂度不小于n(2n－1)k－1。停—走序列的线性复杂度有着良好的稳定性，这由以下定理给出。

定理4-25［1］设停—走序列u∞如定义4-12所述，则其重量复杂度满足以下关系：

(1)WC1(u∞)≥(2n－1)(2n－n－1)；

(2)WC2(u∞)≥(2n－1)(2n－N－n－1)，其中N是2n－1的最大真因子。钟控序列是对线性序列进行改造，提高序列线性复杂度的一种有效方法。与多路复合序列及前馈序列相比，通常认为钟控序列有以下两个优越性［2］：

(1)钟控序列的线性复杂度“指数地依赖于”驱动LFSR的级数，而不像前馈序列和多路复合序列那样，“线性地依赖于”驱动LFSR的级数，从而稳定性较强；

(2)钟控序列生成器易于控制其线性复杂度。但钟控序列也有不足之处，除线性复杂度之外，有些钟控序列其它方面的伪随机性能常常不理想，比如有过多的长游程。4.3序列密码的安全性为了使密钥序列有较强的随机性，从而使密码体制足够安全，人们对序列密码中的密钥生成器提出了如下一些基本要求：

(1)初始密钥K的变化量足够大，一般应在2128种以上；

(2)密钥序列k∞的周期一般不小于255；

(3)k∞具有均匀的游程分布；

(4)k∞不能由一个低级(比如，小于106级)的LFSR产生，也不能与由低级LFSR产生的序列具有较高相似度；

(5)利用统计方法由k∞提取关于密钥生成器的结构或初始密钥K的信息在计算上是不可行的；

(6)具有混乱性，即k∞的每一位与K的大多数比特有关；

(7)具有扩散性，即改变K中任何一位，均会引起k∞的较大改变。目前对序列密码的攻击方法主要有分别征服攻击、线性攻击、最佳仿射攻击、线性伴随式攻击、线性一致性攻击、快速相关攻击、线性时序逻辑逼近、熵漏分析等多种有效的分析方法。

线性攻击是一种已知明文攻击，主要针对线性复杂度较低的序列，用B-M算法破解密钥序列。分别征服攻击(DivideandConquer，DC攻击)［19］利用非线性组合序列对驱动序列的依赖性进行攻击。最佳仿射攻击(BestAffineAttack，BAA攻击)［1］利用序列线性复杂度的不稳定性，当一个高线性复杂度的序列与一个低线性复杂度的序列“距离很近”时，BAA攻击有效。以下主要讨论BAA攻击和DC攻击。在进行BAA攻击或DC攻击时，序列密码体制的模型如图4-11所示。图4-11序列密码体制模型有限域GF(q)上的s元非线性布尔函数f(x)具有如下的一般形式：

(4-10)其中，a0，ai，aij，…∈GF(q)。当函数f(x)的输入序列均为m序列时，关于输出密钥序列的复杂度有如下结论。

定理4-26

设GF(q)上s个最大长度序列由式(4-10)中的函数f(x)进行组合，如果产生这s个最大长度序列的LFSR的极小多项式次数Li(i=1，…，s)互不相同且均大于2，则由f(x)产生的序列有最大线性复杂度f*(L1，L2，…，Ls)。其中，这里的计算在实数域中进行。4.3.1布尔函数的最佳仿射逼近与BAA攻击

定义4-13

设f(x)：GF(2)n→GF(2)，如果存在仿射函数wx+l(w∈GF(2)n，l∈GF(2))，使得取最大值，则称wx+l是f(x)的一个最佳仿射逼近。布尔函数的最佳仿射逼近可以用Walsh谱值来研究，以下的结论与实例来自参考文献［1］。用第二种Walsh谱值描述的最佳逼近定理如下。

引理4-2

令Pf(wx+l)为函数f(x)与仿射函数wx+l相等的概率，则有

(4-11)(4-12)证明:由第二种Walsh谱的定义，有由此即得式(4-11)，再由定理3-2可得式(4-12)。由引理4-2易证得如下的最佳逼近定理。

定理4-27

设f(x)：GF(2)n→GF(2)，a=max{|S〈f〉(w)|：w∈GF(2)n}=|S〈f〉(w0)|则有：

(1)如果S〈f〉(w0)≥0，则w0x为f(x)的最佳仿射逼近，且与f(x)相等的概率为；

(2)如果S〈f〉(w0)<0，则1+w0x为f(x)的最佳仿射逼近，且与f(x)相等的概率为。

Rueppel首先给出了DES中S盒的最佳仿射逼近分析，但未对该方法在密码学中的应用给予进一步的分析。丁存生与单炜娟于1987年将线性逼近与代数方法结合起来设计了针对两类流密码的BAA攻击方法，并由此提出了序列密码的稳定性问题。

BAA攻击是一种已知明文攻击方法，其目的不是恢复密钥生成器的初始密钥，而是利用已知信息构造一个新的密钥生成器来近似替代原密钥序列生成器，从而完成对任意密文的解密。假定攻击者所掌握的信息为：

(1)非线性组合函数f(x)；

(2)所有LFSR的级数ri(i=1，…，s)；

(3)明文编码及语言的统计特性；

(4)M比特密钥序列k1k2…kM，其中M>2(r1+…+rs)。

BAA攻击的主要思想是利用已知信息构造一个新的级数不超过的LFSR，以它来近似地替代原密钥序列生成器；构造方法则是用一个低复杂度的线性序列去逼近高复杂度的非线性序列。由定理4-27知，如果求出w=(w1，w2，…，wn)∈GF(2)n,使谱值的绝对值|S〈f〉(w)|达到最大，且(1≤t≤n)，而其它wj=0，则f(x)的最佳仿射逼近为这里当S〈f〉(w)≥0时，l=0，否则l=1。从而得到序列:在LFSR的输出序列的所有线性组合序列中，(k′)∞与密钥序列k∞的相关性最好，且两者相等的概率为，这里a为最大谱值|S〈f〉(w)|。

例4-1

设图4-11中的s=5，r1=3，r2=4，r3=5，r4=6，r5=7，非线性组合函数f(x)的真值表为f=(00110011110011000011001111001100)，再设已知如下51bit的密钥序列段：k51=1001100001101000100001000100

11010101011011001011001如果每个LFSR的联结多项式均为本原多项式，则由定理4-26，有L(k∞)=6677，计算出最大谱值a=15/16，最大谱值点为(01010)，最佳仿射逼近函数为x2+x4，这样，就有r=4+6=10。从而用B-M算法可以求出第10个2r截段后的每个截段的(g(x)，L)为(1+x2+x4+x5+x6+x7+x10，10)因而基本上可以认为这个LFSR即为产生密钥序列的LFSR。如果进一步的检验正确的话，就构造出了一个级数为10的LFSR，使得它与原密钥生成器的符合率为31/32。这时虽然原密钥流序列的线性复杂度为6677，但可以用一个复杂度为10的序列去逼近它，并且这种逼近与原序列的符合率是相当高(31/32)的。4.3.2DC攻击“DivideandConquer”是一种图论算法，意为将一个待求解问题分解成许多子问题，然后对每个子问题求解，最后再综合。Siegenthler于1985年将这种方法用于分析二元加法非线性组合序列密码［20］，针对图4-11中所示的密码体制设计了一种分别征服攻击方法，该方法大大地降低了寻找密钥所需的试验次数。

DC攻击是一种惟密文攻击，其基本思路是：根据非线性组合器的输出序列k∞与组合函数f(x)的每个输入序列(a(i))∞之间的相关性，用统计方法恢复各个LFSR的初始状态和反馈函数。在图4-11的密码体制中，如果令GF(2)上所有次数为ri的本原多项式数量为Ri，则第i个LFSR的未知参数有个，因此，总的密钥量为。而Siegenthler提出的DC攻击方法将实施穷尽攻击时所需的次减少到了次。

假设攻击者掌握了以下信息：

(1)足够长的密文序列；

(2)非线性组合函数f(x)；

(3)所有LFSR的级数ri(i=1，…，s)；

(4)语言编码及语言统计特性。在进行DC攻击时，首先为密码体制建立如下的统计模型。假设函数f(x)的输入是由一些相互独立同分布的随机变量所产生的，这些随机变量的分布函数为pA，且对所有i和n，有，即为均匀分布。函数f(x)生成一些独立同分布的随机变量

,其概率分布为pK，这里P(Kn=0)=P(Kn=1)且P(Kn=)=qj。再假定明文序列x∞由二元无记忆信源产生，且P(Xn=0)=P0。由于密文Yn与Kn和Xn有关，而Kn又与有关，因而Yn间接地与有关，所以Yn中必定含有LFSRi的信息。DC攻击通过计算LFSRi的输出序列与密文序列之间的相关度α或符合率pe来提取子密钥的信息。

定义4-14

两个长度为N的序列Y1Y2…YN与之间的相关度定义为这里，与各个统计独立且同分布，其概率分布为pA，其中。序列Y1Y2…YN与之间的符合率pe定义为于是。由定义知，pe越大说明序列Y1Y2…YN与之间的符合率越大，从而密文序列中含有关于LFSRi的子密钥的信息量就越大。

DC攻击中还包括假设检验、错误决策分析等过程，这里不一一详述，具体可参考参考文献［1］及［20］。Siegenthler指出，当LFSR的级数足够大时，DC攻击由于计算量太大而无法实现［20］。同时由于目前没有有效的方法来确定所有n次本原多项式，因而DC攻击只能应用于驱动LFSR的级数较小的序列密码。4.4序列密码的应用序列密码是一种方便快捷的加密方法，许多序列密码在现实中得到了广泛应用，如RC4、A5和SNOW。本节将对这些密码体制进行介绍。4.4.1RC4密码

RC4加密算法是RonRivest于1987年设计的密钥长度可变的序列密码算法。该算法在最初的7年中为专利，算法的细节必须在签署保密协议后才能得到。后来RC4通过互联网流传到全世界并得到了关注和研究，随后被广泛地应用于商业加密中。与前面介绍的基于LFSR的随机数产生器不同，RC4的密钥序列使用了称为Table-shuffling的方法产生，即利用一张很大的表生成随机密钥，而这张表可以在自身的控制下变化。RC4主要有以下特征：

(1)可变的密钥长度；

(2)以字节