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

1、第4章 序列密码变换理论4.1 序列密码的基础理论 4.2 密钥序列的产生方法 4.3 序列密码的安全性 4.4 序列密码的应用 第第4章章 序列密码变换理论序列密码变换理论第4章 序列密码变换理论4.1 序列密码的基础理论序列密码的基础理论序列密码又称流密码(Stream Cipher)，其加密方式是用密钥序列z=z1z2的第i个符号加密明文序列m=m1m2的第i个符号，即 在序列密码中，第i个密钥zi由第i时刻密钥生成器的内部状态和初始密钥K决定。密码的安全性主要取决于所用密钥的随机性，所以设计序列密码的核心问题在于设计随机性较好的密钥序列生成器。密钥序列生成器可看做是一个有限状态自动机，

2、由输出符号集、状态集、状态转移函数f、输出函数g和初始状态0所组成，如图4-1所示。2121mEmEmEzzz第4章 序列密码变换理论图4-1 密钥序列生成器第4章 序列密码变换理论序列密码可分为两类：同步流密码(Synchronous Stream Cipher)和自同步流密码(Self-Synchronous Stream Cipher)，前者的密钥序列独立于明文和密文，后者的密钥序列与已产生的一定数量的密文有关。同步流密码的加密过程可描述为这里，0是初始状态，可以由密钥K确定；f是状态转移函数;g是产生密钥序列的函数;E是由密钥序列和明文序列产生密文的函数。Kfii,1Kgzii,izi

3、mEci第4章 序列密码变换理论在同步序列密码中，只要发送端和接收端有相同的初始密钥和初始状态，就能产生出相同的密钥序列，因此说收、发双方的密钥生成器是同步的。其优点是无错误传播，一个传输错误只能影响一个符号，不会影响后继的解密结果。自同步序列密码的加密过程可描述为其中，0=(ct，ct+1，c1)是非秘密的初始状态，是初始密钥;其余符号与同步序列密码中的含义相同。11,ii ti ticcc Kgzii,izimEci第4章 序列密码变换理论4.1.1 周期序列的极小多项式及周期序列的极小多项式及m序列序列通常，密钥流生成器中的驱动部分是一个反馈移位寄存器。线性反馈移位寄存器LFSR(Lin

4、ear Feedback Shift Register)的理论非常成熟，它的实现简单、速度快、便于分析，因而成为构造密钥流生成器最重要的部件之一。移位寄存器是一种有限状态自动机，它由一系列的存储单元、若干个乘法器和加法器通过电路连接而成。假设共有n个存储单元(此时称该移位寄存器为n级)，每个存储单元可存储一比特信息，在第i时刻各个存储单元中的比特序列(aiai+1ai+n1)称为移位寄存器的状态，(a0a1an1)为初始状态。在第j个时钟脉冲到来时，存储单元中的数据向前移动一位，状态由(ajaj+1aj+n1)变为(aj+1aj+2aj+n)，同时，按照固定规则产生输入比特和输出比特。图4-2

5、描述了GF(2)上的n级LFSR。第4章 序列密码变换理论图4-2 GF(2)上的n级LFSR第4章 序列密码变换理论产生输入数据的变换规则称为反馈函数。给定了当前状态和反馈函数，可以唯一确定输出和下一时刻的状态。通常，反馈函数是一个n元布尔函数。定义定义4-1 设LFSR的输出序列为a=a0a1a2，则称满足对任意iZ+，ai=ai+p的最小正整数p为序列的周期。具有有限周期的序列称为周期序列。更一般地，如果存在一个下标i0，满足ai+p=ai(对所有ii0成立)则称序列a是周期为p的终归周期序列。非终归周期序列的周期定义为无穷大。第4章 序列密码变换理论通常我们将形如a0a1的序列称为半无

6、限序列，记作a，而将形如a0a1an1a0a1an1的序列称为周期为n的周期半无限序列，记作(an)。一个n级LFSR的输出序列的最长周期由以下定理确定。定理定理4-1 n级LFSR的周期2n1。周期是衡量序列伪随机性的一个重要标准，要产生性能较好的密钥序列，要求作为密钥发生器的驱动部分的移位寄存器有较长的周期。除此之外，序列的随机性还用游程分布和周期自相关函数来度量。第4章 序列密码变换理论定义定义4-2 在序列a中,若有at1at=at+1=at+l1at+l，则称(xt，xt+1，xt+l1)为一个长为l的游程。定义定义4-3 设序列(an)的周期为p，定义周期自相关函数为其中，A=|0

7、ip;ai=ai+j|;D=|0ip;aiai+j|。若p|j，则R(j)为同相自相关函数，此时A=p，D=0，故R(j)=1;若pj，则R(j)为异相自相关函数。Golomb对于二进制序列的随机性提出了三条假设4，满足这些假设的序列就被视为具有较强的随机性，或称其为伪随机序列(Pseudo-Random Sequence)。=1,2,ADR jjp第4章 序列密码变换理论这三条假设是：(1)若序列的周期为偶数，则在一个周期内，0、1的个数相等；若序列的周期为奇数，则在一个周期内，0、1的个数相差1。(2)在一个周期内，长度为l的游程数占游程总数的，且对于任意长度，0游程与1游程个数相等。(3

8、)所有的异相自相关函数值相等。这三条假设也可以推广到GF(q)上的序列。12l第4章 序列密码变换理论LFSR可以用线性函数递归地定义，末端存储器的输入引入多项式f(x)=c0+c1x+c2x2+cn1xn1其中，未定元x(xak=ak1)称为延迟算子。f(x)称为LFSR的联结多项式。f(x)的互反多项式称为LFSR的特征多项式。1011110njjijniniiniacacacaca 12110nnnncxcxcxcxf第4章 序列密码变换理论已知二元周期序列a=a0a1a2，其周期p(a)=L，显然，由联结多项式为1+xL1的L级LFSR(称为纯轮换移位寄存器)可以产生序列a，联结多项式

9、为1+x2L1，1+x3L1，的LFSR也可以产生a。我们将能产生a的LFSR的联结多项式组成的集合记作J(a)：J(a)=g(x)|g(x)F2x，g(x)a=0 设ma(x)是J(a)中次数最低的首一多项式，则J(a)=h(x)ma(x)|h(x)F2x即J(a)中的多项式都是ma(x)的倍式。事实上，可以证明J(a)是多项式环GF(2)x的一个理想，其生成元为ma(x)。通常称ma(x)为周期序列a的极小多项式，也称极小联结式。显然，用ma(x)作为联结多项式产生序列a是效率最高的一种方案。第4章 序列密码变换理论由于序列的周期与其联结多项式密切相关，下面我们介绍多项式的周期，并用多项式

10、的周期来研究序列的周期。定义定义4-4 设g(x)为GF(2)上的多项式，deg(g(x)1，g(0)0，使g(x)|(1xL)成立的最小正整数L称为g(x)的周期(又称阶或指数)，记作p(g)。注：如果g(0)=0，则可将g表示为如下形式：g(x)=xlh(x)h(0)0此时，g(x)的周期定义为h(x)的周期。如果LFSR的联结多项式中的cn10，则称该LFSR是非退化的。第4章 序列密码变换理论定理定理4-2 设ma(x)是非退化LFSR产生的序列a的极小多项式，则p(a)=p(ma)，即a的周期等于多项式ma(x)的周期。由定理4-2知，n级LFSR的极小多项式周期的上界与其输出序列的

11、周期上界相同，均为2n1。设f(x)F2x，deg(f(x)1，如果f(x)不能分解为GF(2)中两个非平凡多项式的乘积，则称f(x)是GF(2)上的不可约多项式(或既约多项式)。如果f(x)是GF(2)上的n次不可约多项式，并且其周期达到上界2n1，则称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章 序列密码变换理论定义定义4-5 周期为2n1的n级LFSR的输出序列称为m序列。m序列是由n级线性移位寄存器所能产生的最长周

12、期序列，同时，它也是研究最为成熟的序列。除了具有最长周期之外，它还有许多良好的伪随机性质，因而在密码学和扩频通信等领域中得到了广泛应用。m序列的基本特性由以下定理给出2。第4章 序列密码变换理论定理定理4-4 GF(q)上的n级m序列a具有以下性质：(1)a的周期为qn1，线性复杂度为n。(2)对任意xGF(q)，x0，x在a的一个周期内出现qn1次，0出现qn11次，特别地，GF(2)上的m序列在一个周期内0的个数为2n1，1的个数为2n11。(3)a的极小多项式生成的所有非0序列均为m序列，它们是a的平移序列。(4)设(a(j)(j=1，2，k)为a的k个平移序列，任取k个常数xjGF(q

13、)，则序列或为全0序列，或为a的一个平移序列。kjjjaxb1第4章 序列密码变换理论(5)对任意k(1kn)，称为序列a的一个k维状态向量。在连续qn1个k维状态向量中，GF(q)k中的每个非0向量出现qnk次，0向量出现qnk1次。(6)如果aj=aj+1=aj+k1=xGF(q)，且aj1x，aj+kx，则称(ajaj+1aj+k1)是一个长为k的x游程。kkjjjjqGFaaas11,0,1,2njsjq第4章 序列密码变换理论将序列a的一个周期首尾相连，则游程分布如下：游程的总数为qn1；1kn2时，对xGF(q)，长为k的x游程有(q1)2qnk2个；长为n1的0游程有q1个；对x

14、0，长为n1的x游程有q2个，长为n的x游程有1个。第4章 序列密码变换理论(7)设序列a的h间隔采样序列为a(h，d)，即a(h，d)=adad+had+2h，则a(h，d)是m序列当且仅当h与qn1互素。当gcd(h，qn1)=1时，m序列a(h，d)的极小多项式与起始采样位置d无关，仅仅与采样间隔h有关；不同的采样间隔对应着不同的极小多项式。(8)对任意h=1，2，qn2，d=0，1，qn2且gcd(h，qn1)=1，h间隔采样序列a(h，d)遍历了所有的n级m序列。下述定理给出了产生m序列的充要条件。第4章 序列密码变换理论定理定理4-5 设GF(2)上n级LFSR的联结多项式为f(x

15、)，用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，aN1为输入，输出产生该序列的最短LFS

16、R的特征多项式fN(x)及其阶数lN。第4章 序列密码变换理论B-M算法算法输入：N，序列a0，a1，aN1。第一步：n0，f0(x)，l01，0。第二步：计算dn=fn(D)an，其中，D为延迟算子(Dak=ak1)。(1)当dn=0时，fn+1(x)，ln+1fn(x)，ln转第三步；(2)当dn=1，且l0=l1=ln=0时，fn+1(x)，ln+11+xn+1，n+1转第三步；第4章 序列密码变换理论(3)当dn=1，且lmlm+1=lm+2=ln(mn)时，第三步：若nN1，nn+1，转第二步。输出：fN(x)，lN。B-M算法的时间复杂性为O(N2)，空间复杂性为O(N)。B-M算

17、法广泛应用于BCH码的译码中。一个二元随机序列a0a1a2可视作一个二元对称信源的输出，当前输出位an与以前输出段a0a1an1之间是完全独立的，因此，即使已知a0，a1，an1，an仍是不可预测的。而对于n级m序列，由B-M算法，只要得知其前2n位，就能以较快的速度求出序列的任一位。111,max,1n mnnnnmmnnfxlfxd dxfxl nl 第4章 序列密码变换理论4.1.2 序列的线性复杂度序列的线性复杂度 度量有限长或周期序列的随机性的方法有很多，但最常用的方法是由Lempel和Ziv建议的“线性复杂度”方法8，用产生该序列的最短LFSR的长度来度量，这种方法本质上衡量了序列

18、的线性不可预测性。定义定义4-6 一个有限序列a=a0a1at的线性复杂度，是指对于选定的初始状态，生成序列a所需要的线性反馈移位寄存器的最小阶数，记作C(a)。对于全0序列，约定其复杂度为0。定理定理4-6 设a=a0a1a2是二元周期序列，且序列a的线性复杂度C(a)=L1，则只要知道a中任意相继的2L位就可确定整个序列及产生a的极小多项式。第4章 序列密码变换理论事实上，B-M算法给出了确定序列线性复杂度的有效方法，由于B-M算法可以求得任一给定序列的线性复杂度，从而使序列的线性复杂度成为同步序列密码的一个重要强度指标。在序列密码中，线性复杂度小的序列不能用作密钥序列，但也不是说，线性复

19、杂度大的序列就一定能作为密钥序列。比如周期为p的序列：0 0 0 0 1 0 0 1 0 如果p很大，则产生该序列的LFSR长度也很大，然而该序列显然不能作为密钥序列。任何周期序列的线性复杂度显然不超过它的周期。此外还可以利用矩阵的秩来研究序列的线性复杂度。第4章 序列密码变换理论定理定理4-7 设域GF(q)上的序列a=a0a1an1，则a的线性复杂度等于矩阵Ga当1，2，n1取遍GF(q)中所有值时的最小秩。证明:设Ga的最小秩为r(Ga)，将矩阵Ga的第一行至第n行分别标记为0至n1。若a的线性复杂度C(a)=l，则存在线性递推关系:(4-1)1232112114321123211232

20、10nnnnnnnnnnaaaaaaaaaaaaaaaaaG 10,0,1,1,li lijjjjaac incGF q 第4章 序列密码变换理论从而对于lin1，只要适当地选择1，2，n1，便可将Ga的第i行表示为前面l行的线性组合，因此r(Ga)1。但由线性复杂度的定义，l是使式(4-1)成立的最小整数，因而也是第l行的前nl个分量能够表示成前面各行的对应分量线性组合的最小整数。故前l行线性独立，从而r(Ga)l，故r(Ga)=l。定理4-7描述了有限长序列的线性复杂度的秩表示，下面讨论无限序列的线性复杂度的秩表示。第4章 序列密码变换理论定理定理4-8 一个周期半无限序列(an)的线性复

21、杂度等于矩阵的秩，即C(an)=rankM(an)这里，Si(a)表示序列a循环左移i位得到的序列，称矩阵M(an)为循环矩阵。aSaSaaaaaaaaaaaMnnnnn1201021110第4章 序列密码变换理论证明证明:在周期半无限序列(an)=a0a1an1a0a1an1中，ai=ai+n(i0)。显然，(an)的线性复杂度至多为n，如果C(an)=l，则对1i8，n=4k，m=2k，2dk，再设cGF(2)m，定义d次函数f(x)：GF(2)mGF(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的转置

22、，则显然f(x)是GF(2)m上的Bent函数。TdiiTcxxxxxf121第4章 序列密码变换理论定义定义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-20 Bent序列的线性复杂度。此外，典型的前馈序列还有几何序列、No序列等，详细构造可见参考文献2。tatataftsm,21,2,1,0ttaaii mdsCd2第4章 序列密码变换理论4.2.2 多路复合序列多路复合序列多路复合

23、序列生成器涉及到多个LFSR，其中一个LFSR用于控制其它LFSR的输出。常见的多路复合序列有Geffe序列、J-K触发器及Pless序列等。1.Geffe序列序列Geffe序列生成器由三个LFSR组成，其中LFSR2作为控制生成器使用，如图 4-5所示。第4章 序列密码变换理论图4-5 Geffe序列生成器(一)第4章 序列密码变换理论当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。若设LFSRi(i=1，2，3)的输入序列为a(i)，输出序列为b，则有 Geffe序列生成器也可以表示为如图4-6所示的形式。123212323 0,1,

24、2,kkkkkkkkkkba aaaa aa aak第4章 序列密码变换理论图4-6 Geffe序列生成器(二)第4章 序列密码变换理论图中，LFSR1和LFSR3作为多路复合器的输入；LFSR2控制多路复合器的输出。定理定理4-21 在如图4-6所示的Geffe序列生成器中，设LFSRi(i=1，2，3)的特征多项式分别为di次本原多项式，且di两两互素，则所生成的Geffe序列的周期为，线性复杂度为(d1+d3)d2+d3。Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的，因而不失为一种理想的伪随机序列。3112idi第4章 序列密码变换理论2.J-K触发器触发器J-K触

25、发器如图4-7所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck1。第4章 序列密码变换理论图4-7 J-K触发器第4章 序列密码变换理论设J、K端的输入分别为x1和x2，则由此可得J-K触发器的真值表如表4-1所示。1121xcxxckk第4章 序列密码变换理论利用J-K触发器可以构造非线性序列生成器，如图4-8所示。图4-8 利用J-K触发器构造的非线性序列生成器第4章 序列密码变换理论图中，a、b为驱动序列，且 (4-8)设驱动序列a和b分别为n1级和n2级m序列，如果n1、n2互素且a0+b0=1，则序列c的周期为 。kkkkkkkkkacbaac

26、bac111121221nncp第4章 序列密码变换理论由式(4-8)易知:因此，如果知道序列c中两个相邻位的值ck1和ck，就可以推断出ak或bk。进而可以由足够多的这类信息分析得到序列a和b。为了克服这个缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器14。1,0,11kkkkkcbcac第4章 序列密码变换理论3.Pless生成器生成器Pless生成器由八个LFSR、四个J-K触发器和一个循环计数器构成，由循环计数器进行选通控制，如图4-9所示。第4章 序列密码变换理论图4-9 Pless生成器第4章 序列密码变换理论4.2.3 钟控序列钟控序列钟

27、控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图4-10所示。图4-10 钟控序列第4章 序列密码变换理论当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2，因此LFSR2重复输出前一位。输出序列c称为钟控序列。设LFSR1和LFSR2的输出序列分别为，周期分别为p1和p2，钟控序列c的周期为p3，则有如下关系：其中，。12ppab和2213,gcdpwppp 101piiaw第4章 序列密码变换理论再设的极小多项式分别为GF(2)上的本原多项式f1(x)和f2(x)，deg

28、(f1)=d1，deg(f2)=d2，且d1|d2，则，由m序列的性质知，从而gcd(w，p2)=1，所以 此外，也可推导出c的线性复杂度为，极小多项式为。12ppab和121221,21ddpp112dw121221213ddppp1212dd1221dxf第4章 序列密码变换理论在实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型。典型的钟控序列有Jennings复合序列15、停走生成器(stop-and-go generator)16、Gunther生成器17及缩减序列18。以下仅对停走生成器做一简要介绍，其它序列的具体构造请参考有关文献。定义定义4-12 设GF(2)上的两个n

29、级m序列为a和b，它们的极小多项式分别为f(x)和g(x)，定义整数函数G(t)为(4-9)1000,1,2,tiiGG ta t第4章 序列密码变换理论令，则序列u=u0u1u2称为停走序列。所谓停走序列是指由序列a控制b的停或走而生成的序列，实际上是由a控制的对b的不等距采样序列。其周期和线性复杂度由下述定理给出。,0,1,2,tG tubt第4章 序列密码变换理论定理定理4-22 停走序列u的极小多项式为，周期为(2n1)2，线性复杂度为n(2n1)。停走序列的概念可以进一步推广到两个级数不同m序列或者多个同级m序列的情形。定理4-23 设a为GF(2)上的n级m序列，b为GF(2)上的

30、r级m序列，函数G(t)如式(4-9)中定义，序列u=u0u1u2定义为ut=bG(t)t=0，1，2，则u的线性复杂度为n(2r1)。12 nxg第4章 序列密码变换理论定理定理4-24 设为GF(2)上的k个n级m序列，如果将这k个序列用停走生成器进行级联，即用控制得到序列控制得到序列 控制得到序列，则的线性复杂度不小于n(2n1)k1。停走序列的线性复杂度有着良好的稳定性，这由以下定理给出。()(1,2,)iaik(1)a(2)a(2)(2),ua(3)a(3)(1)nua()na()nu第4章 序列密码变换理论定理定理4-251 设停走序列u如定义4-12所述，则其重量复杂度满足以下关

31、系：(1)WC1(u)(2n1)(2nn1)；(2)WC2(u)(2n1)(2nNn1)，其中N是2n1的最大真因子。第4章 序列密码变换理论钟控序列是对线性序列进行改造，提高序列线性复杂度的一种有效方法。与多路复合序列及前馈序列相比，通常认为钟控序列有以下两个优越性2：(1)钟控序列的线性复杂度“指数地依赖于”驱动LFSR的级数，而不像前馈序列和多路复合序列那样，“线性地依赖于”驱动LFSR的级数，从而稳定性较强；(2)钟控序列生成器易于控制其线性复杂度。但钟控序列也有不足之处，除线性复杂度之外，有些钟控序列其它方面的伪随机性能常常不理想，比如有过多的长游程。第4章 序列密码变换理论4.3

32、序列密码的安全性序列密码的安全性为了使密钥序列有较强的随机性，从而使密码体制足够安全，人们对序列密码中的密钥生成器提出了如下一些基本要求：(1)初始密钥K的变化量足够大，一般应在2128种以上；(2)密钥序列k的周期一般不小于255；(3)k具有均匀的游程分布；(4)k不能由一个低级(比如，小于106级)的LFSR产生，也不能与由低级LFSR产生的序列具有较高相似度；(5)利用统计方法由k提取关于密钥生成器的结构或初始密钥K的信息在计算上是不可行的；(6)具有混乱性，即k的每一位与K的大多数比特有关；第4章 序列密码变换理论(7)具有扩散性，即改变K中任何一位，均会引起k的较大改变。目前对序列

33、密码的攻击方法主要有分别征服攻击、线性攻击、最佳仿射攻击、线性伴随式攻击、线性一致性攻击、快速相关攻击、线性时序逻辑逼近、熵漏分析等多种有效的分析方法。第4章 序列密码变换理论线性攻击是一种已知明文攻击，主要针对线性复杂度较低的序列，用B-M算法破解密钥序列。分别征服攻击(Divide and Conquer，DC攻击)19利用非线性组合序列对驱动序列的依赖性进行攻击。最佳仿射攻击(Best Affine Attack，BAA攻击)1利用序列线性复杂度的不稳定性，当一个高线性复杂度的序列与一个低线性复杂度的序列“距离很近”时，BAA攻击有效。以下主要讨论BAA攻击和DC攻击。在进行BAA攻击或

34、DC攻击时，序列密码体制的模型如图4-11所示。第4章 序列密码变换理论图4-11 序列密码体制模型第4章 序列密码变换理论有限域GF(q)上的s元非线性布尔函数f(x)具有如下的一般形式：(4-10)其中，a0，ai，aij，GF(q)。当函数f(x)的输入序列均为m序列时，关于输出密钥序列的复杂度有如下结论。ssjiijiisxxxaxxaxaaxxxf2112021,第4章 序列密码变换理论定理定理4-26 设GF(q)上s个最大长度序列由式(4-10)中的函数f(x)进行组合，如果产生这s个最大长度序列的LFSR的极小多项式次数Li(i=1，s)互不相同且均大于2，则由f(x)产生的序

35、列有最大线性复杂度f*(L1，L2，Ls)。其中，这里的计算在实数域中进行。ssijisxxxaaaaxxxf21*12*021*,第4章 序列密码变换理论4.3.1 布尔函数的最佳仿射逼近与布尔函数的最佳仿射逼近与BAA攻击攻击定义定义4-13 设f(x)：GF(2)nGF(2)，如果存在仿射函数wx+l(wGF(2)n，lGF(2)，使得取最大值，则称wx+l是f(x)的一个最佳仿射逼近。布尔函数的最佳仿射逼近可以用Walsh谱值来研究，以下的结论与实例来自参考文献1。用第二种Walsh谱值描述的最佳逼近定理如下。nGFxlwxxf2第4章 序列密码变换理论引理引理4-2 令Pf(wx+l

36、)为函数f(x)与仿射函数wx+l相等的概率，则有 (4-11)(4-12)11 222nffPwxSwwGF wSwSwxPfff121第4章 序列密码变换理论 证明:由第二种Walsh谱的定义，有由此即得式(4-11)，再由定理3-2可得式(4-12)。由引理4-2易证得如下的最佳逼近定理。1:22:12 12fnnfSwx f xwxx f xwxx f xwxPwx 第4章 序列密码变换理论定理定理4-27 设f(x)：GF(2)nGF(2)，a=max|Sf(w)|：wGF(2)n=|Sf(w0)|则有：(1)如果Sf(w0)0，则w0 x为f(x)的最佳仿射逼近，且与f(x)相等的

37、概率为；(2)如果Sf(w0)2(r1+rs)。第4章 序列密码变换理论BAA攻击的主要思想是利用已知信息构造一个新的级数不超过的LFSR，以它来近似地替代原密钥序列生成器；构造方法则是用一个低复杂度的线性序列去逼近高复杂度的非线性序列。由定理4-27知，如果求出w=(w1，w2，wn)GF(2)n,使谱值的绝对值|Sf(w)|达到最大，且(1tn)，而其它wj=0，则f(x)的最佳仿射逼近为这里当Sf(w)0时，l=0，否则l=1。从而得到序列:siir1121tiiiwww 121lkkkktiii lxxxxLtiii21第4章 序列密码变换理论在LFSR的输出序列的所有线性组合序列中，

38、(k)与密钥序列k的相关性最好，且两者相等的概率为，这里a为最大谱值|Sf(w)|。例例4-1 设图4-11中的s=5，r1=3，r2=4，r3=5，r4=6，r5=7，非线性组合函数f(x)的真值表为f=(0011 0011 1100 1100 0011 0011 1100 1100)，再设已知如下51 bit的密钥序列段：k51=1001 1000 0110 1000 1000 0100 01001101 0101 0110 1100 1011 00112a第4章 序列密码变换理论如果每个LFSR的联结多项式均为本原多项式，则由定理4-26，有L(k)=6677，计算出最大谱值a=15/1

39、6，最大谱值点为(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章 序列密码变换理论4.3.2 DC攻击攻击“Divide and Conquer

40、”是一种图论算法，意为将一个待求解问题分解成许多子问题，然后对每个子问题求解，最后再综合。Siegenthler于1985年将这种方法用于分析二元加法非线性组合序列密码20，针对图4-11中所示的密码体制设计了一种分别征服攻击方法，该方法大大地降低了寻找密钥所需的试验次数。第4章 序列密码变换理论DC攻击是一种惟密文攻击，其基本思路是：根据非线性组合器的输出序列k与组合函数f(x)的每个输入序列(a(i)之间的相关性，用统计方法恢复各个LFSR的初始状态和反馈函数。在图4-11的密码体制中，如果令GF(2)上所有次数为ri的本原多项式数量为Ri，则第i个LFSR的未知参数有个，因此，总的密钥量

41、为。而Siegenthler提出的DC攻击方法将实施穷尽攻击时所需的次减少到了次。12iriRsiriiR112niriiR112niriiR112第4章 序列密码变换理论假设攻击者掌握了以下信息：(1)足够长的密文序列；(2)非线性组合函数f(x)；(3)所有LFSR的级数ri(i=1，s)；(4)语言编码及语言统计特性。第4章 序列密码变换理论在进行DC攻击时，首先为密码体制建立如下的统计模型。假设函数f(x)的输入是由一些相互独立同分布的随机变量所产生的，这些随机变量的分布函数为pA，且对所有i和n，有，即为均匀分布。函数f(x)生成一些独立同分布的随机变量,其概率分布为pK，这里P(K

42、n=0)=P(Kn=1)且P(Kn=)=qj。再假定明文序列x由二元无记忆信源产生，且P(Xn=0)=P0。(1,)inA is 2110ininAPAPsnnnnAAAfK,21jnX第4章 序列密码变换理论由于密文Yn与Kn和Xn有关，而Kn又与有关，因而Yn间接地与有关，所以Yn中必定含有LFSRi的信息。DC攻击通过计算LFSRi的输出序列与密文序列之间的相关度或符合率pe来提取子密钥的信息。inAinA第4章 序列密码变换理论定义定义4-14 两个长度为N的序列Y1Y2YN与之间的相关度定义为这里，与各个统计独立且同分布，其概率分布为pA，其中。序列Y1Y2YN与之间的符合率pe定义

43、为于是。iNiiAAA21111212 0,1,2,NNiijjjjjjYAYAisNN 0nAinA2110ininAPAPiNiiAAA210001 12ijennnnnniipP KAP XP KAP XPqPq einnpAYP11第4章 序列密码变换理论由定义知，pe越大说明序列Y1Y2YN与之间的符合率越大，从而密文序列中含有关于LFSRi的子密钥的信息量就越大。DC攻击中还包括假设检验、错误决策分析等过程，这里不一一详述，具体可参考参考文献1及20。Siegenthler指出，当LFSR的级数足够大时，DC攻击由于计算量太大而无法实现20。同时由于目前没有有效的方法来确定所有n次

44、本原多项式，因而DC攻击只能应用于驱动LFSR的级数较小的序列密码。iNiiAAA21第4章 序列密码变换理论4.4 序列密码的应用序列密码的应用序列密码是一种方便快捷的加密方法，许多序列密码在现实中得到了广泛应用，如RC4、A5和SNOW。本节将对这些密码体制进行介绍。4.4.1 RC4密码密码RC4加密算法是Ron Rivest于1987年设计的密钥长度可变的序列密码算法。该算法在最初的7年中为专利，算法的细节必须在签署保密协议后才能得到。后来RC4通过互联网流传到全世界并得到了关注和研究，随后被广泛地应用于商业加密中。第4章 序列密码变换理论与前面介绍的基于LFSR的随机数产生器不同，R

45、C4的密钥序列使用了称为Table-shuffling的方法产生，即利用一张很大的表生成随机密钥，而这张表可以在自身的控制下变化。RC4主要有以下特征：(1)可变的密钥长度；(2)以字节为单位的加密；(3)密钥构成了所有8 bit的置换；(4)简单、高效；(5)可以抵抗现有的攻击方法。第4章 序列密码变换理论下面我们介绍这种密码体制的细节。RC4算法工作于OFB模式，其密钥序列与明文序列相互独立，它有一个88的S盒，记作S0，S1，S255，每个Si都是数字0255的置换，这个置换由可变长度的密钥控制。RC4密码包括初始化算法和伪随机密钥生成算法两部分。初始化时，首先给各个S盒赋初值：S0=0

46、，S1=1，S255=255。再用密钥K填充另一个256字节的数组，不断地重复使用密钥直至填充到整个数组中。第4章 序列密码变换理论初始化算法如下：for(i=0;i255;i+)si=i;j=0;for(i=0;i255;i+)j=(j+si+ki)%256;swap(si，sj);第4章 序列密码变换理论在初始化过程中，密钥的主要功能是将S盒搅乱，计数器i确保S盒的每个元素都得到处理，而j则保证S盒的搅乱是随机的。而不同的S盒在经过子密钥生成算法的处理后可以得到不同的密钥序列：i=j=0;while(明文未结束)+i%=n;j=(j+si)%n;swap(si，sj);sub_k=s(si

47、+sj)%n);第4章 序列密码变换理论加密时，子密钥sub_k与明文异或产生密文；解密时，sub_k与密文异或产生明文。RC4的运算速度很快，可以达到DES加密的10倍左右。RSA数据安全公司宣称RC4具有较高的非线性特性，并可以抵抗差分分析和线性分析。有几十种加密产品中使用了RC4，如Lotus Notes、苹果计算机的AOCE和Oracle安全SQL数据库中都使用了RC4作为加密算法。RC4还应用在无线局域网通信协议(Wired Equivalent Privacy，WEP)以及蜂窝数字数据包规范中。第4章 序列密码变换理论4.4.2 A5密码密码在GSM(Group Special M

48、obile)移动通信系统中，A5被用于加密从电话到基站的信息。A5由三个并列的LFSR组成，它们的级数分别为19、22和23。所有的联结多项式系数都比较少(称为稀疏多项式)。其初态由密钥独立地赋值，输出是三个LFSR输出的异或。A5中采用可变钟控方式，每一个LFSR由自身中间位的时钟控制。若控制比特中有两个或三个取值为1，则产生1的寄存器移位；若两个或三个控制比特为0，则产生0的寄存器不移位。因此，A5的密钥序列是一种停走序列，在这种相互钟控的方式下，每个寄存器移位的概率为3/4，一个周期大约需要个时钟。341223第4章 序列密码变换理论攻击A5要用240次加密来确定两个LFSR的结构，再用

49、密钥流来确定第三个LFSR。A5的效率很高，可以通过所有已知的统计检验标准。它仅有的缺点是每个LFSR的级数太短，其密钥序列的最短周期为(k是最长的LFSR的级数)。为了提高安全性，可以选用级数较长以及稠密反馈多项式的LFSR。k234第4章 序列密码变换理论4.4.3 欧洲欧洲NESSIE工程及工程及eSTREAM工程简介工程简介自2000年1月至2002年12月，欧洲委员会投资33亿欧元支持其信息社会技术(IST)规划中一项名为NESSIE(New European Schemes for Signatures，Integrity，and Encryption)的工程。NESSIE工程的主

50、要目标是通过公开征集进行公开的、透明的测试评价，提出一套强大的密码标准，这些标准包括分组密码、序列密码、杂凑函数、消息认证码、数字签名方案和公钥加密方案。此外，NESSIE工程还将考虑候选密码标准所能应用的具体环境，甚至也征集评测这些候选密码标准的测试方法(如统计测试)。该工程将发展一种密码体制的评估方法(包括安全性和性能评价)和支持评估的一个软件工具箱。第4章 序列密码变换理论NESSIE工程也像DES、RIPE规划和AES的选择过程一样，采用先征集后评估的办法，但其征集范围要比NIST的AES广泛得多。NESSIE收到的五个候选同步序列密码如表4-2所示。第4章 序列密码变换理论第4章 序