《现代密码学第二章.ppt》由会员分享，可在线阅读，更多相关《现代密码学第二章.ppt（59页珍藏版）》请在三一办公上搜索。
1、2023/5/29,1,第二章：流密码,一、流密码的基本概念二、线性反馈移位寄存器序列三、非线性组合序列四、钟控序列,2023/5/29,2,一、流密码的基本概念,有关的概念若m1的取值为 0或1，则称m1为一个比特（bit）。n个比特m1m2m3 mn，称为一个长度为n的比特串。无穷个比特m1m2m3 mnmn+1，称为一个比特流。两个比特流：m=m1m2m3 mnmn+1，k=k1k2k3 knkn+1，做运算得到如下一个新的比特流：c=c1c2c3 cncn+1，,2023/5/29,3,一、流密码的基本概念,其中cn=mn+kn(mod2)，n=1，2，3，称比特流c是比特流m与比特流
2、k的逐位模2加，或逐比特异或。记作c=m+k注意：此时有m=c+kk=m+c,2023/5/29,4,一、流密码的基本概念,当（1）明文是比特流m，称为明文流；（2）加密密钥和解密密钥相同，是比特流k，称为密钥流；（3）密文是比特流c，称为密文流；（4）加密算法和解密算法相同，加密：c=m+k；解密：m=c+k。则称这样的加解密算法为流密码，又称其为序列密码。,2023/5/29,5,一、流密码的基本概念,随机性：密钥流的理想情形假设密钥流k是由完全随机的方式生成的。因此从攻击者的角度来看，密钥流k应该是真正的随机序列，满足：k1，k2，k3，kn，kn+1，都是具有等概率分布随机变量，P(k
3、l=0)=P(kl=1)=1/2，且它们相互独立。,2023/5/29,6,一、流密码的基本概念,任意两个不相重叠的密文段，它们所对应的密钥段都是相互独立的。换句话说，每一次加密都使用与以前的密钥段完全无关的新密钥段。再换句话说，此时的加密方式是一次一密的。因此，此时达到了最高的安全性标准：无条件安全（完善保密）。这样的密钥流k具有以下三条重要的性质：,2023/5/29,7,一、流密码的基本概念,（1）P(kl=0)=P(kl=1)=1/2。（1）当n充分大时，k1k2 k3 kn中0和1的个数各占约一半。（2）P(k1k2 kl=10 01)=P(k1k2 kl=01 10)=1/2l。（
4、2）当n充分大时，在k1k2 k3 kn中，长度为l的比特串10 01（称为0游程）的个数约有n/2l 个；长度为l的比特串01 10（称为1游程）的个数约有n/2l 个。（3）若k0，P(kl=kl+k)=P(klkl+k)=1/2。（3）若k0，当n充分大时，以下的值（称为异相自相关函数值）约为0。,2023/5/29,8,一、流密码的基本概念,2023/5/29,9,一、流密码的基本概念,伪随机性：密钥流的实用情形实用的密钥流k不可能由完全随机的方式生成。出于商用目的和标准化要求，密钥流k必须由确定的方式自动生成。不过从攻击者的角度来看，密钥流k很像真正的随机序列，称为伪随机序列。伪随机
5、序列应该满足前面提到的性质（1）（2）（3）。这三条性质就是著名的Golomb随机性假设。,2023/5/29,10,一、流密码的基本概念,两个不相重叠的密文段，它们所对应的密钥段可能不同，但未必没有依赖关系。换句话说，此时的加密方式未必是一次一密的。因此，此时未必达到无条件安全。因此，伪随机的密钥流只能力争做到计算安全。,2023/5/29,11,一、流密码的基本概念,现在对流密码进行已知明文攻击。设攻击者Eve在以往截获了密文段c1c2c3 cn，并知道了对应的废弃明文段m1m2m3 mn，因此计算出了对应的废弃密钥段k1k2k3 kn。希望：由k1k2k3 kn难以预测后续密钥段kn+1
6、kn+2。这种不可预测性又称为伪随机性。因此希望密钥流k满足Golomb随机性假设（1）（2）（3）。但这还不够，还必须具有“很高的线性复杂度”。（将在以后介绍）,2023/5/29,12,二、线性反馈移位寄存器序列,线性反馈移位寄存器序列若比特流k由如下的方式生成：（1）选择长度为n的比特串k1k2k3 kn；（2）当ln后，kl=c1kl-1+c2kl-2+cnkl-n。其中常数c1、c2、cn都是比特值，且cn=1。,2023/5/29,13,二、线性反馈移位寄存器序列,则称比特流k为n阶线性反馈移位寄存器序列，又称为n阶线性递归序列；称常数c1、c2、cn为抽头系数；称比特串k1k2k
7、3 kn为初始状态；称f(x)=1+c1x1+c2x2+cnxn为此线性反馈移位寄存器序列的极小多项式。,2023/5/29,14,线性反馈移位寄存器(linear feedback shift register)(LFSR),2023/5/29,15,二、线性反馈移位寄存器序列,线性反馈移位寄存器序列的性质（不给出证明）设比特流k为n阶线性反馈移位寄存器序列。（1）k是周期序列，最小周期不超过2n-1。（2）k由抽头系数c1，c2，cn和初始状态k1k2k3 kn唯一确定。（3）如果k的最小周期达到了2n-1，此时称k为n阶m序列。m序列具有以下的特殊性质。（Golomb随机性假设）,202
8、3/5/29,16,二、线性反馈移位寄存器序列,（3.1）k在自己的一个最小周期内（即连续2n-1个比特内），0出现2n-1-1次，1出现2n-1次。（3.2）取定j，3jn，观察k的连续2n-1个长l的比特串：klkl+1kl+2 kl+j-1，l=1,2,2n-1。10 01出现2n-l次；（长为l-2的0游程）01 10出现2n-l次。（长为l-2的1游程）观察k的连续2n-1个长n+1的比特串：klkl+n，l=1 2n-1。10 01出现1次。（长为n-1的0游程）观察k的连续2n-1个长n+2的比特串：klkl+n+1，l=1 2n-1。0110出现1次。（长为n-1的0游程）,2
9、023/5/29,17,二、线性反馈移位寄存器序列,（3.3）对任何1j2n-2，下式为0。（自相关函数）,2023/5/29,18,二、线性反馈移位寄存器序列,从以上性质可以看出，n阶m序列满足Golomb随机性假设。而且当n并不大时，通信伙伴生成n阶m序列的复杂度很小，得到的最小周期2n-1却极大。如此看来，m序列似乎非常适合用作密钥流。其实不然。如果n阶线性反馈移位寄存器序列用作密钥流，攻击者Eve截获了密文段c1c2c3 c2n，并知道了对应的明文段m1m2m3 m2n，因此计算出了对应的废弃密钥段k1k2k3 k2n。则Eve获得了关于抽头系数c1、c2、cn的以下方程组。,2023
10、/5/29,19,二、线性反馈移位寄存器序列,kl=c1kl-1+c2kl-2+cnkl-n，其中l=n+1，n+2，2n。注意到这是在有限域GF(2)上的线性方程组，很容易解出抽头系数c1、c2、cn。实际上，当Eve获得了n阶线性反馈移位寄存器序列的任何一段的连续2n个比特kj+1kj+2kj+3 kj+2n，他就获得了关于抽头系数c1、c2、cn的以下方程组。kl=c1kl-1+c2kl-2+cnkl-n，其中l=j+n+1，j+n+2，j+2n。,2023/5/29,20,二、线性反馈移位寄存器序列,2023/5/29,21,二、线性反馈移位寄存器序列,以上方程组中的加法和乘法都是在域
11、GF(2)上进行的（即(mod2)运算）。以上事实说明，当Eve获得了n阶线性反馈移位寄存器序列的任意连续2n个比特，Eve就获得了整个密钥流。实际上，对线性反馈移位寄存器序列还有更为有效的攻击方法。当Eve不知道阶数n时，他还可以进行测试。这种测试攻击方法被称为序列的综合。,2023/5/29,22,二、线性反馈移位寄存器序列,线性反馈移位寄存器序列的综合定理 如果一个比特流是一个周期序列，则它一定是线性反馈移位寄存器序列。证明 设比特流k的最小周期是N。则lN后，kl=kl-N。因此比特流k为N阶线性反馈移位寄存器序列，抽头系数为 c1、c2、cN=0、0、0、1（即极小多项式f(x)=1
12、+xN），初始状态为k1k2k3 kN。,2023/5/29,23,二、线性反馈移位寄存器序列,定义 一个周期序列作为一个线性反馈移位寄存器序列，它的最小阶数称为它的线性复杂度。（注意 一个周期序列作为一个线性反馈移位寄存器序列，可以有很多不同的阶数，其中它的最小周期就是它的一个阶数。因此，周期序列的线性复杂度一定不超过它的最小周期）所谓序列的综合，就是寻找周期序列的线性复杂度n，并且求出极小多项式f(x)。序列的综合的两种最著名的算法是B-M算法和Games-Chan算法。,2023/5/29,24,二、线性反馈移位寄存器序列,B-M算法输入：周期序列的一段长度为N的比特串sN=s0s1s2
13、sN-1。目的：求出比特串sN的最短的线性递归关系。当N周期序列的线性复杂度的2倍时，该线性递归关系的阶数就是线性复杂度，该线性递归关系就给出了抽头系数。,2023/5/29,25,二、线性反馈移位寄存器序列,步骤1：找n0使得当j=0 n0-1时，sj=0；当j=n0时，sj=1。取初始值对于j=0 n0-1，令dj=0；对于j=n0，令dj=sl；对于0jn0，令fj(x)=1，lj=0；再对于j=n0+1，令fj(x)=1+dj-1xj，lj=j。,2023/5/29,26,二、线性反馈移位寄存器序列,步骤2：设(fj(x),lj)；0jn已经求出。如果n=N，则直接转步骤3；否则计算d
14、n=fn(E)sn（此处E是“时间延迟算子”。即：当fn(x)=a0+a1x+a2x2+atxt时，fn(E)sn=a0sn+a1sn-1+a2sn-2+atsn-t。）,2023/5/29,27,二、线性反馈移位寄存器序列,（1）如果dn=0，则令fn+1(x)=fn(x)；ln+1=ln；转步骤2。（2）如果dn=1，则：找出m使得lmlm+1=lm+2=ln；令fn+1(x)=fn(x)+xn-mfm(x)；ln+1=maxln,n+1-ln；转步骤2。,2023/5/29,28,二、线性反馈移位寄存器序列,步骤3：最后得到了(fN(x),lN)。（fN(x)的全体系数就是比特串sN的一
15、个最短的齐次线性递归关系；该齐次线性递归关系的长度为lN。如果N不小于周期序列的线性复杂度的2倍，lN就是该周期序列的线性复杂度，fN(x)就是该周期序列的极小多项式。可以看出，B-M算法简单快速，攻击线性复杂度小的序列极为有效。）,2023/5/29,29,二、线性反馈移位寄存器序列,Games-Chan算法定理 比特流的最小周期为2的幂时，其线性复杂度大于其最小周期的一半。（不给出证明）设比特流的最小周期为N=2n。输入：周期序列的一个最小周期sN=s0s1s2sN-1；令Lc=0；f(x)=1。,2023/5/29,30,二、线性反馈移位寄存器序列,步骤1：令L=(s0,s1,s2,sN
16、/2-1)；R=(sN/2,sN/2+1,sN/2+2,sN-1)；计算B=L+R。步骤2：如果B0，则令Lc=Lc+N/2，f(x)=f(x)(1+x)N/2，s=B，转步骤3；如果B=0，则令s=L，转步骤3。步骤3：令N=N/2。步骤4：如果N=1，B0，则输出(Lc,f(x)，停止；如果N=1，B=0，s0，则令Lc=Lc+1，f(x)=f(x)(1-x)，输出(Lc,f(x)，停止；如果N1，则转步骤1。,2023/5/29,31,二、线性反馈移位寄存器序列,最后输出的(Lc,f(x)是序列s的线性复杂度和极小多项式。注意到虽然序列的线性复杂度大于2n-1，用Games-Chan算法
17、至多迭代n步就可求出，因此对此类大的线性复杂度，Games-Chan比B-M算法更加快速。由于需要序列的一个周期参加运算，存储量巨大，故Games-Chan算法还不能算是一个有效的算法。,2023/5/29,32,二、线性反馈移位寄存器序列,线性反馈移位寄存器序列的小结线性反馈移位寄存器序列能够实现：小的计算量（n阶线性递归生成，通常n不大）；极大的最小周期（对于m序列，最小周期为2n-1）；良好的伪随机性（对于m序列，Golomb随机性假设成立）。,2023/5/29,33,二、线性反馈移位寄存器序列,然而小的计算量得到小的线性复杂度（对于m序列，线性复杂度为n），很容易由短的一段（对于m序
18、列，由长度为2n的一段）推断出整个序列（用B-M算法）。因此，线性反馈移位寄存器序列不能作为密钥流。（能否让线性复杂度很大？不能）兼顾小的计算量和大的线性复杂度，需要使用非线性的生成方式。,2023/5/29,34,三、非线性组合序列,域GF(2)上的n维函数（n维布尔函数）n维布尔函数是这样的函数y=g(x1,x2,xn)：n个自变量x1,x2,xn取值均为0和1；因变量y取值为0和1。,2023/5/29,35,三、非线性组合序列,n维布尔函数的代数正规型：y=g(x1,x2,xn)=a(0)+a(1)x1+a(2)x2+a(n)xn+a(1,2)x1x2+a(n-1,n)xn-1xn+a
19、(1,2,3)x1x2x3+a(n-2,n-1,n)xn-2xn-1xn+a(1,n)x1xn,2023/5/29,36,三、非线性组合序列,其中常数a(0)，a(1)a(n)，a(1,2)a(n-1,n)，a(1,2,3)a(n-2,n-1,n)，a(1,n)称为系数，它们取0或1为值。使得系数不为0的项的最高次数称为n维布尔函数的次数。（关于n维布尔函数的注解：x12x1，因此只有混合高次项；又因此最高次数不超过n；系数组a(0)a(1,n)中一共有2n个系数；函数g(x1,x2,xn)与系数组相互唯一）,2023/5/29,37,三、非线性组合序列,当g(x1,x2,xn)只含有一次项时
20、，称g为线性函数；当g(x1,x2,xn)只含有0次项和一次项时，称g为仿射函数；当g(x1,x2,xn)含有高次项时，称g为非线性函数。,2023/5/29,38,三、非线性组合序列,非线性前馈序列若比特流k由如下的方式生成：（1）选择n阶m序列s=s1s2s3，其极小多项式为f(x)，其初始状态为s1s2s3 sn；（2）对每个l0，kl=g(sl,sl+1,sl+n-1)。其中g(x1,x2,xn)为非线性的n维布尔函数。则称比特流k为非线性前馈序列。称m序列s为驱动序列。,2023/5/29,39,三、非线性组合序列,2023/5/29,40,三、非线性组合序列,当非线性前馈序列用作密
21、钥流时，通常只有三个部分可能作为通信伙伴的原始密钥：初始状态，极小多项式，非线性布尔函数。有以下三种不同的用法：（1）原始密钥是初始状态，而将极小多项式和非线性布尔函数公开。此时原始密钥最短，但需要精心设计非线性布尔函数。（2）原始密钥是初始状态和极小多项式，而将非线性布尔函数公开。此时原始密钥长一些，但对非线性布尔函数的要求低一些。（3）原始密钥是初始状态、极小多项式、非线性布尔函数。此时原始密钥最长，但对非线性布尔函数的要求最低。,2023/5/29,41,三、非线性组合序列,为什么g必须是非线性函数？如果g是线性函数，则前馈序列k还是n阶m序列，并且与驱动序列s有相同的极小多项式（不给出
22、证明）。如果g是仿射函数，则前馈序列k是n阶m序列的补序列。希望：非线性前馈序列的线性复杂度极大，应该与2n具有相同的数量级。,2023/5/29,42,三、非线性组合序列,前馈序列k的伪随机性如何？2n-1是前馈序列k的一个周期（容易证明）。换句话说，前馈序列k的最小周期必然是2n-1的因子。希望：前馈序列k的最小周期就是2n-1。希望：前馈序列k是0-1基本均衡的，即在一个最小周期内0和1的数量近似相等。这些都需要精心地设计非线性布尔函数g。前馈序列最难做到的是游程分布的伪随机性和自相关的的伪随机性。,2023/5/29,43,三、非线性组合序列,非线性组合序列若比特流k由如下的方式生成：
23、（1）M个n阶m序列s(j)=s(j)1s(j)2s(j)3；j=1M；（2）对每个l0，kl=g(s(1)l,s(2)l,s(M)l)。其中g(x1,x2,xM)为非线性的M维布尔函数。则称比特流k为非线性组合序列。称M个n阶m序列s(j)为驱动序列。,2023/5/29,44,三、非线性组合序列,2023/5/29,45,三、非线性组合序列,J-K触发器 J和K分别表示两个m序列，它们在任意时刻的输出是J-K触发器的输入。这两个输入与J-K触发器上一个时刻的内部状态ql-1相结合，得到J-K触发器本时刻的内部状态ql，同时J-K触发器在本时刻输出该状态ql。如下表所示。一般令q-1=0。,
24、2023/5/29,46,四、钟控序列,钟控序列钟控序列的种类很多，大体上采用如下的结构：（1）选择2个同步的m序列s(j)=s(j)1s(j)2s(j)3；j=1，2；（2）在任何一个时刻，根据s(1)的“当前情况”，决定是否输出s(2)的“对应比特”；当输出时，输出s(2)的“哪些比特”。最终输出的序列就是钟控序列。称s(1)为控制序列。称s(2)为受控序列。请注意，钟控序列与非线性前馈序列不同。钟控序列并不是每个时刻都输出一个比特。,2023/5/29,47,四、钟控序列,2023/5/29,48,四、钟控序列,钟控序列的的设计思想：对m序列进行适当的“变形”和“剪裁”，使得原本线性复杂
25、度很低的m序列变成线性复杂度级高的钟控序列。设m序列的阶为n。作为密钥流，钟控序列与非线性前馈序列相比，有以下的优点和缺点（不给出证明）：（1）钟控序列能够更容易地使线性复杂度达到极大。（2）钟控序列不是等间隔输出，而是不定时的输出，使得必须额外地进行时间同步，配备缓存器。（3）钟控序列对m序列的某些比特跳过不输出，造成了一定的浪费。,2023/5/29,49,四、钟控序列,停-走生成器此工作属于Beth T.。所给出的停-走生成器如下。设GF(2)上两个n级m-序列：控制序列a=a0a1a2；受控序列b=b0b1b2。记G(t)=a0+a1+a2+at-1。（不是(mod2)加法）停-走序列
26、u=u0u1u2为：ut=bG(t)，t=0,1,2,。,2023/5/29,50,四、钟控序列,缩减序列：互缩序列 此工作属于Don Coppersmith。所给出的互缩序列如下。设GF(2)上两个n级m-序列：控制序列a=a0a1a2；受控序列b=b0b1b2。当at=1时，输出bt；当at=0时，放弃输出。如此得到的输出序列 u=u0u1u2称为互缩序列。,2023/5/29,51,四、钟控序列,缩减序列：广义自缩序列 所给出的广义自缩序列如下。设GF(2)上一个n级m-序列a=a0a1a2。取G=(g0,g1,gn-1)GF(2)n。记vt=g0at+g1at-1+gn-1at-n+1
27、。当at=1时，输出vt；当at=0时，放弃输出。如此得到的输出序列 b=b0b1b2称为广义自缩序列。可以看出，控制序列是a=a0a1a2，受控序列是v=v0v1v2，其中 vt=g0at+g1at-1+gn-1at-n+1。,2023/5/29,52,四、钟控序列,注解一：关于受控序列v 当G=(g0,g1,gn-1)GF(2)n是全0向量时，受控序列v是全0序列；当G=(g0,g1,gn-1)GF(2)n是不为全0的向量时，受控序列v是控制序列a的平移序列。（即：v=v0v1v2=akak+1ak+2。这是m序列的一个基本结论，不给出证明。此时，控制序列a 与受控序列v具有相同的极小多项
28、式，仅仅初始状态不同。这就是序列被称为“广义自缩序列”的理由）,2023/5/29,53,四、钟控序列,注解二：关于广义自缩序列的最小周期 控制序列a 的最小周期是2n-1，在一个最小周期中，“1”出现2n-1次；当G=(g0,g1,gn-1)GF(2)n是不为全0的向量时，受控序列v的最小周期也是2n-1。这就是说，每当广义自缩序列输出了2n-1个比特后，再输出就是重复这2n-1个比特。换句话说，2n-1是广义自缩序列的周期。再换句话说，广义自缩序列的最小周期是2n-1的因子。,2023/5/29,54,四、钟控序列,因此，一个问题是怎样选择向量GGF(2)n，使得广义自缩序列的最小周期达到
29、最大（即2n-1）。理论分析表明：（1）当G是全0向量时，广义自缩序列是全0序列；（2）当G=(1,0,0)时，广义自缩序列是全1序列；（3）当G=(0,g1,gn-1)或G=(1,g1,gn-1)时，广义自缩序列是0101或1010；其中g1=c1，g2=c1+c2，gn-1=c1+cn-1，c1cn是控制序列a 的抽头系数。,2023/5/29,55,四、钟控序列,部分试验结果表明：除了以上三种特殊情况以外，广义自缩序列的最小周期似乎总是达到最大（即2n-1）。至今还没有找到这样的广义自缩序列：其最小周期既不是1，也不是2，也不是2n-1。于是有猜想：广义自缩序列的最小周期总是属于1，2，
30、2n-1。这个猜想目前还没有得到证明。,2023/5/29,56,四、钟控序列,注解三：关于广义自缩序列的均衡性 当G是全0向量时，广义自缩序列是全0序列；当G=(1,0,0)时，广义自缩序列是全1序列；当G不是以上两种情况，广义自缩序列在其任意连续2n-1个比特都是0-1均衡的，即“1”和“0”各出现2n-2次。,2023/5/29,57,四、钟控序列,注解四：关于广义自缩序列的线性复杂度 由于所有的广义自缩序列的最小周期都是2的幂，因此其线性复杂度大于其最小周期的一半。特别当广义自缩序列的最小周期是2n-1时，其线性复杂度大于2n-2。作为密钥流这是非常理想的结果。,2023/5/29,58,四、钟控序列,注解五：关于广义自缩序列的游程分布 当广义自缩序列不是全0序列或全1序列（即G不是全0向量，也不等于(1,0,0)）：广义自缩序列连续出现的0的个数不超过n2-n；广义自缩序列连续出现的1的个数不超过n2-n。(这个理论结果远远不够理想。不过试验结果为：连续出现的0的个数和连续出现的1的个数总不超过2n),2023/5/29,59,四、钟控序列,注解五：关于广义自缩序列的自相关性 当广义自缩序列不是全0序列或全1序列（即G不是全0向量，也不等于(1,0,0)）：令k固定。当n趋向于无穷大时，k阶自相关函数值A(k)趋向于0。其中A(k)如下式。,
