现代密码学第二章.ppt

《现代密码学第二章.ppt》由会员分享，可在线阅读，更多相关《现代密码学第二章.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章：第二章：流密码一、流密码的基本概念一、流密码的基本概念二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列三、非线性组合序列三、非线性组合序列四、钟控序列四、钟控序列2022/12/11一、流密码的基本概念一、流密码的基本概念有关的概念有关的概念若m1的取值为 0或1，则称m1为一个比特（bit）。n个比特m1m2m3 mn，称为一个长度为n的比特串。无穷个比特m1m2m3 mnmn+1，称为一个比特流。两个比特流：m=m1m2m3 mnmn+1，k=k1k2k3 knkn+1，做运算得到如下一个新的比特流：c=c1c2c3 cncn+1，2022/12/12一、流密码的基本概念一、流

2、密码的基本概念其中cn=mn+kn(mod2)，n=1，2，3，称比特流c是比特流m与比特流k的逐位模2加，或逐比特异或。记作c=m+k注意：此时有m=c+kk=m+c2022/12/13一、流密码的基本概念一、流密码的基本概念当（1）明文是比特流m，称为明文流；（2）加密密钥和解密密钥相同，是比特流k，称为密钥流；（3）密文是比特流c，称为密文流；（4）加密算法和解密算法相同，加密：c=m+k；解密：m=c+k。则称这样的加解密算法为流密码，又称其为序列密码。2022/12/14一、流密码的基本概念一、流密码的基本概念随机性：密钥流的理想情形随机性：密钥流的理想情形假设密钥流k是由完全随机的

3、方式生成的。因此从攻击者的角度来看，密钥流k应该是真正的随机序列，满足：k1，k2，k3，kn，kn+1，都是具有等概率分布随机变量，P(kl=0)=P(kl=1)=1/2，且它们相互独立。2022/12/15一、流密码的基本概念一、流密码的基本概念任意两个不相重叠的密文段，它们所对应的密钥段都是相互独立的。换句话说，每一次加密都使用与以前的密钥段完全无关的新密钥段。再换句话说，此时的加密方式是一次一密的。因此，此时达到了最高的安全性标准：无条件安全（完善保密）。这样的密钥流k具有以下三条重要的性质：2022/12/16一、流密码的基本概念一、流密码的基本概念（1）P(kl=0)=P(kl=1

4、)=1/2。（1）当n充分大时，k1k2 k3 kn中0和1的个数各占约一半。（2）P(k1k2 kl=10 01)=P(k1k2 kl=01 10)=1/2l。（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。2022/12/17一、流密码的基本概念一、流密码的基本概念2022/12/18一、流密码的基本概念一、流密码的基本概念伪随机性：密

5、钥流的实用情形伪随机性：密钥流的实用情形实用的密钥流k不可能由完全随机的方式生成。出于商用目的和标准化要求，密钥流k必须由确定的方式自动生成。不过从攻击者的角度来看，密钥流k很像真正的随机序列，称为伪随机序列。伪随机序列应该满足前面提到的性质（1）（2）（3）。这三条性质就是著名的Golomb随机性假设。2022/12/19一、流密码的基本概念一、流密码的基本概念两个不相重叠的密文段，它们所对应的密钥段可能不同，但未必没有依赖关系。换句话说，此时的加密方式未必是一次一密的。因此，此时未必达到无条件安全。因此，伪随机的密钥流只能力争做到计算安全。2022/12/110一、流密码的基本概念一、流密

6、码的基本概念现在对流密码进行已知明文攻击。设攻击者Eve在以往截获了密文段c1c2c3 cn，并知道了对应的废弃明文段m1m2m3 mn，因此计算出了对应的废弃密钥段k1k2k3 kn。希望：由k1k2k3 kn难以预测后续密钥段kn+1kn+2。这种不可预测性又称为伪随机性。因此希望密钥流k满足Golomb随机性假设（1）（2）（3）。但这还不够，还必须具有“很高的线性复杂度”。（将在以后介绍）2022/12/111二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列线性反馈移位寄存器序列线性反馈移位寄存器序列若比特流k由如下的方式生成：（1）选择长度为n的比特串k1k2k3 kn；（2）当

7、ln后，kl=c1kl-1+c2kl-2+cnkl-n。其中常数c1、c2、cn都是比特值，且cn=1。2022/12/112二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列则称比特流k为n阶线性反馈移位寄存器序列，又称为n阶线性递归序列；称常数c1、c2、cn为抽头系数；称比特串k1k2k3 kn为初始状态；称f(x)=1+c1x1+c2x2+cnxn为此线性反馈移位寄存器序列的极小多项式。2022/12/113线性反馈移位寄存器线性反馈移位寄存器(linear feedback shift register)(LFSR)2022/12/114二、线性反馈移位寄存器序列二、线性反馈移位寄

8、存器序列线性反馈移位寄存器序列的性质线性反馈移位寄存器序列的性质（不给出证明）（不给出证明）设比特流k为n阶线性反馈移位寄存器序列。（1）k是周期序列，最小周期不超过2n-1。（2）k由抽头系数c1，c2，cn和初始状态k1k2k3 kn唯一确定。（3）如果k的最小周期达到了2n-1，此时称k为n阶m序列。m序列具有以下的特殊性质。（Golomb随机性假设）2022/12/115二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列（3.1）k在自己的一个最小周期内（即连续2n-1个比特内），0出现2n-1-1次，1出现2n-1次。（3.2）取定j，3jn，观察k的连续2n-1个长l的比特串：k

9、lkl+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游程）2022/12/116二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列（3.3）对任何1j2n-2，下式为0。（自相关函数）2022/12/117二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列从以上性质可以看

10、出，n阶m序列满足Golomb随机性假设。而且当n并不大时，通信伙伴生成n阶m序列的复杂度很小，得到的最小周期2n-1却极大。如此看来，m序列似乎非常适合用作密钥流。其实不然。如果n阶线性反馈移位寄存器序列用作密钥流，攻击者Eve截获了密文段c1c2c3 c2n，并知道了对应的明文段m1m2m3 m2n，因此计算出了对应的废弃密钥段k1k2k3 k2n。则Eve获得了关于抽头系数c1、c2、cn的以下方程组。2022/12/118二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列kl=c1kl-1+c2kl-2+cnkl-n，其中l=n+1，n+2，2n。注意到这是在有限域GF(2)上的线性

11、方程组，很容易解出抽头系数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。2022/12/119二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列2022/12/120二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列以上方程组中的加法和乘法都是在域GF(2)上进行的（即(mod2)运算）。以上事实说明，当Eve获得了n阶线性反馈移位寄存器序列的任意连续2n个比特，Ev

12、e就获得了整个密钥流。实际上，对线性反馈移位寄存器序列还有更为有效的攻击方法。当Eve不知道阶数n时，他还可以进行测试。这种测试攻击方法被称为序列的综合。2022/12/121二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列线性反馈移位寄存器序列的综合线性反馈移位寄存器序列的综合定理定理 如果一个比特流是一个周期序列，则它一定是线性反馈移位寄存器序列。证明 设比特流k的最小周期是N。则lN后，kl=kl-N。因此比特流k为N阶线性反馈移位寄存器序列，抽头系数为 c1、c2、cN=0、0、0、1（即极小多项式f(x)=1+xN），初始状态为k1k2k3 kN。2022/12/122二、线性反

13、馈移位寄存器序列二、线性反馈移位寄存器序列定义定义 一个周期序列作为一个线性反馈移位寄存器序列，它的最小阶数称为它的线性复杂度。（注意 一个周期序列作为一个线性反馈移位寄存器序列，可以有很多不同的阶数，其中它的最小周期就是它的一个阶数。因此，周期序列的线性复杂度一定不超过它的最小周期）所谓序列的综合，就是寻找周期序列的线性复杂度n，并且求出极小多项式f(x)。序列的综合的两种最著名的算法是B-M算法和Games-Chan算法。2022/12/123二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列B-M算法算法输入：周期序列的一段长度为N的比特串sN=s0s1s2sN-1。目的：求出比特串s

14、N的最短的线性递归关系。当N周期序列的线性复杂度的2倍时，该线性递归关系的阶数就是线性复杂度，该线性递归关系就给出了抽头系数。2022/12/124二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列步骤1：找n0使得n当j=0 n0-1时，sj=0；当j=n0时，sj=1。n取初始值n对于j=0 n0-1，令dj=0；对于j=n0，令dj=sl；n对于0jn0，令fj(x)=1，lj=0；n再对于j=n0+1，令fj(x)=1+dj-1xj，lj=j。2022/12/125二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列步骤2：设(fj(x),lj)；0jn已经求出。如果n=N，则直接转

15、步骤3；否则计算ndn=fn(E)snn（此处E是“时间延迟算子”。即：当fn(x)=a0+a1x+a2x2+atxt时，fn(E)sn=a0sn+a1sn-1+a2sn-2+atsn-t。）2022/12/126二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列（1）如果dn=0，则n令fn+1(x)=fn(x)；ln+1=ln；n转步骤2。（2）如果dn=1，则：找出m使得nlm0，kl=g(sl,sl+1,sl+n-1)。其中g(x1,x2,xn)为非线性的n维布尔函数。则称比特流k为非线性前馈序列。称m序列s为驱动序列。2022/12/138三、非线性组合序列三、非线性组合序列202

16、2/12/139三、非线性组合序列三、非线性组合序列当非线性前馈序列用作密钥流时，通常只有三个部分可能作为通信伙伴的原始密钥：初始状态，极小多项式，非线性布尔函数。有以下三种不同的用法：（1）原始密钥是初始状态，而将极小多项式和非线性布尔函数公开。此时原始密钥最短，但需要精心设计非线性布尔函数。（2）原始密钥是初始状态和极小多项式，而将非线性布尔函数公开。此时原始密钥长一些，但对非线性布尔函数的要求低一些。（3）原始密钥是初始状态、极小多项式、非线性布尔函数。此时原始密钥最长，但对非线性布尔函数的要求最低。2022/12/140三、非线性组合序列三、非线性组合序列为什么为什么g必须是非线性函数

17、？必须是非线性函数？如果g是线性函数，则前馈序列k还是n阶m序列，并且与驱动序列s有相同的极小多项式（不给出证明）。如果g是仿射函数，则前馈序列k是n阶m序列的补序列。希望：非线性前馈序列的线性复杂度极大，应该与2n具有相同的数量级。2022/12/141三、非线性组合序列三、非线性组合序列前馈序列前馈序列k的伪随机性如何？的伪随机性如何？2n-1是前馈序列k的一个周期（容易证明）。换句话说，前馈序列k的最小周期必然是2n-1的因子。希望：前馈序列k的最小周期就是2n-1。希望：前馈序列k是0-1基本均衡的，即在一个最小周期内0和1的数量近似相等。这些都需要精心地设计非线性布尔函数g。前馈序列

18、最难做到的是游程分布的伪随机性和自相关的的伪随机性。2022/12/142三、非线性组合序列三、非线性组合序列非线性组合序列非线性组合序列若比特流k由如下的方式生成：（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)为驱动序列。2022/12/143三、非线性组合序列三、非线性组合序列2022/12/144三、非线性组合序列三、非线性组合序列J-K触发器触发器 J和和K分别表示两个分别表示两个m序列，它们

19、在任意时刻的输序列，它们在任意时刻的输出是出是J-K触发器的输入。这两个输入与触发器的输入。这两个输入与J-K触发器上一个时触发器上一个时刻的内部状态刻的内部状态ql-1相结合，得到相结合，得到J-K触发器本时刻的内部状态触发器本时刻的内部状态ql，同时，同时J-K触发器在本时刻输出该状态触发器在本时刻输出该状态ql。如下表所示。如下表所示。一般令一般令q-1=0。J0011K0101本时刻的状态及输出：ql上一状态：ql-101上一状态取补：1-ql-12022/12/145四、钟控序列四、钟控序列钟控序列钟控序列钟控序列的种类很多，大体上采用如下的结构：（1）选择2个同步的m序列s(j)=

20、s(j)1s(j)2s(j)3；j=1，2；（2）在任何一个时刻，根据s(1)的“当前情况”，决定是否输出s(2)的“对应比特”；当输出时，输出s(2)的“哪些比特”。最终输出的序列就是钟控序列。称s(1)为控制序列。称s(2)为受控序列。请注意，钟控序列与非线性前馈序列不同。钟控序列并不是每个时刻都输出一个比特。2022/12/146四、钟控序列四、钟控序列2022/12/147四、钟控序列四、钟控序列钟控序列的的设计思想：对m序列进行适当的“变形”和“剪裁”，使得原本线性复杂度很低的m序列变成线性复杂度级高的钟控序列。设m序列的阶为n。作为密钥流，钟控序列与非线性前馈序列相比，有以下的优点

21、和缺点（不给出证明）：（1）钟控序列能够更容易地使线性复杂度达到极大。（2）钟控序列不是等间隔输出，而是不定时的输出，使得必须额外地进行时间同步，配备缓存器。（3）钟控序列对m序列的某些比特跳过不输出，造成了一定的浪费。2022/12/148四、钟控序列四、钟控序列停停-走生成器走生成器此工作属于Beth T.。所给出的停-走生成器如下。设GF(2)上两个n级m-序列：控制序列a=a0a1a2；受控序列b=b0b1b2。记G(t)=a0+a1+a2+at-1。（不是(mod2)加法）停-走序列u=u0u1u2为：ut=bG(t)，t=0,1,2,。2022/12/149四、钟控序列四、钟控序列

22、缩减序列：互缩序列缩减序列：互缩序列 此工作属于Don Coppersmith。所给出的互缩序列如下。设GF(2)上两个n级m-序列：控制序列a=a0a1a2；受控序列b=b0b1b2。当at=1时，输出bt；当at=0时，放弃输出。如此得到的输出序列 u=u0u1u2称为互缩序列。2022/12/150四、钟控序列四、钟控序列缩减序列：广义自缩序列缩减序列：广义自缩序列 所给出的广义自缩序列如下。设GF(2)上一个n级m-序列a=a0a1a2。取G=(g0,g1,gn-1)GF(2)n。记vt=g0at+g1at-1+gn-1at-n+1。当at=1时，输出vt；当at=0时，放弃输出。如此

23、得到的输出序列 b=b0b1b2称为广义自缩序列。可以看出，控制序列是a=a0a1a2，受控序列是v=v0v1v2，其中 vt=g0at+g1at-1+gn-1at-n+1。2022/12/151四、钟控序列四、钟控序列注解一：关于受控序列注解一：关于受控序列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具有相同的极小多项式，仅仅初始状态不同。这就是序

24、列被称为“广义自缩序列”的理由）2022/12/152四、钟控序列四、钟控序列注解二：关于广义自缩序列的最小周期注解二：关于广义自缩序列的最小周期 控制序列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的因子。2022/12/153四、钟控序列四、钟控序列因此，一个问题是怎样选择向量GGF(2)n，使得广义自缩序列的

25、最小周期达到最大（即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 的抽头系数。2022/12/154四、钟控序列四、钟控序列部分试验结果表明：除了以上三种特殊情况以外，广义自缩序列的最小周期似乎总是达到最大（即2n-1）。至今还没有找到这样的广义自缩序列：其最小周期既不是1，也不是2，也不是2n-1。于是有猜想：广义自缩序列的最小周期

26、总是属于1，2，2n-1。这个猜想目前还没有得到证明。2022/12/155四、钟控序列四、钟控序列注解三：注解三：关于广义自缩序列的均衡性关于广义自缩序列的均衡性 当G是全0向量时，广义自缩序列是全0序列；当G=(1,0,0)时，广义自缩序列是全1序列；当G不是以上两种情况，广义自缩序列在其任意连续2n-1个比特都是0-1均衡的，即“1”和“0”各出现2n-2次。2022/12/156四、钟控序列四、钟控序列注解四：注解四：关于广义自缩序列的线性复杂度关于广义自缩序列的线性复杂度 由于所有的广义自缩序列的最小周期都是2的幂，因此其线性复杂度大于其最小周期的一半。特别当广义自缩序列的最小周期是

27、2n-1时，其线性复杂度大于2n-2。作为密钥流这是非常理想的结果。2022/12/157四、钟控序列四、钟控序列注解五：注解五：关于广义自缩序列的游程分布关于广义自缩序列的游程分布 当广义自缩序列不是全0序列或全1序列（即G不是全0向量，也不等于(1,0,0)）：广义自缩序列连续出现的0的个数不超过n2-n；广义自缩序列连续出现的1的个数不超过n2-n。(这个理论结果远远不够理想。不过试验结果为：连续出现的0的个数和连续出现的1的个数总不超过2n)2022/12/158四、钟控序列四、钟控序列注解五：注解五：关于广义自缩序列的自相关性关于广义自缩序列的自相关性 当广义自缩序列不是全0序列或全1序列（即G不是全0向量，也不等于(1,0,0)）：令k固定。当n趋向于无穷大时，k阶自相关函数值A(k)趋向于0。其中A(k)如下式。2022/12/159