《现代密码学第二章》PPT课件

《《现代密码学第二章》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、+kn(mod2)，n=1，2，3，…，称比特流c是比特流m与比特流k的逐位模2加，或逐比特异或。记作c=m‘+’k注意：此时有m=c‘+’kk=m‘+’c2021/7/223一、流密码的基本概念当（1）明文是比特流m，称为明文流；（2）加密密钥和解密密钥相同，是比特流k，称为密钥流；（3）密文是比特流c，称为密文流；（4）加密算法和解密算法相同，加密：c=m‘+’k；解密：m=c‘+’k。则称这样的加解密算法为流密码，又称其为序列密码。2021/7/224一、流密码的基本概念随机性：密钥流的理

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

4、具有以下三条重要的性质：2021/7/226一、流密码的基本概念（1）P(kl=0)=P(kl=1)=1/2。（1’）当n充分大时，k1k2k3…kn中0和1的个数各占约一半。（2）P(k1k2…kl=10…01)=P(k1k2…kl=01…10)=1/2l。（2’）当n充分大时，在k1k2k3…kn中，长度为l的比特串10…01（称为0游程）的个数约有n/2l个；长度为l的比特串01…10（称为1游程）的个数约有n/2l个。（3）若k>0，P(kl=kl+k)=P(kl≠kl+k)=1/2。（

5、3’）若k>0，当n充分大时，以下的值（称为异相自相关函数值）约为0。2021/7/227一、流密码的基本概念2021/7/228一、流密码的基本概念伪随机性：密钥流的实用情形实用的密钥流k不可能由完全随机的方式生成。出于商用目的和标准化要求，密钥流k必须由确定的方式自动生成。不过从攻击者的角度来看，密钥流k很像真正的随机序列，称为伪随机序列。伪随机序列应该满足前面提到的性质（1’）（2’）（3’）。这三条性质就是著名的Golomb随机性假设。2021/7/229一、流密码的基本概念两个不相重叠

6、的密文段，它们所对应的密钥段可能不同，但未必没有依赖关系。换句话说，此时的加密方式未必是一次一密的。因此，此时未必达到无条件安全。因此，伪随机的密钥流只能力争做到计算安全。2021/7/2210一、流密码的基本概念现在对流密码进行已知明文攻击。设攻击者Eve在以往截获了密文段c1c2c3…cn，并知道了对应的废弃明文段m1m2m3…mn，因此计算出了对应的废弃密钥段k1k2k3…kn。希望：由k1k2k3…kn难以预测后续密钥段kn+1kn+2…。这种不可预测性又称为伪随机性。因此希望密钥流k满

7、足Golomb随机性假设（1’）（2’）（3’）。但这还不够，还必须具有“很高的线性复杂度”。（将在以后介绍）2021/7/2211二、线性反馈移位寄存器序列线性反馈移位寄存器序列若比特流k由如下的方式生成：（1）选择长度为n的比特串k1k2k3…kn；（2）当l>n后，kl=c1kl-1‘+’c2kl-2‘+’…‘+’cnkl-n。其中常数c1、c2、…、cn都是比特值，且cn=1。2021/7/2212二、线性反馈移位寄存器序列则称比特流k为n阶线性反馈移位寄存器序列，又称为n阶线性递归序列

8、；称常数{c1、c2、…、cn}为抽头系数；称比特串k1k2k3…kn为初始状态；称f(x)=1‘+’c1x1‘+’c2x2‘+’…‘+’cnxn为此线性反馈移位寄存器序列的极小多项式。2021/7/2213线性反馈移位寄存器(linearfeedbackshiftregister)(LFSR)2021/7/2214二、线性反馈移位寄存器序列线性反馈移位寄存器序列的性质（不给出证明）设比特流k为n阶线性反馈移位寄存器序列。（1）k是周期序列，最小周期不超过2n-1。（2）k由抽头系数{c1，c