资源描述：
《现代密码学第2章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章流密码2.1流密码的基本概念2.2线性反馈移位寄存器2.3线性移位寄存器的一元多项式表示2.4m序列的伪随机性2.5m序列密码的破译2.6非线性序列习题流密码可以认为是起源于20世纪20年代的Vernam密码体制。当Vernam密码中的密钥序列是随机的（0，1）序列时，它就是“一次一密”密码体制。Shannon已经证明了“一次一密”密码体制在理论上是不可破译的。这给予序列密码技术的研究和应用于强大的支持。由于随机的密钥的产生、存储和分配等方面存在一定的困难，Vernam密码在当时并没有得到广泛的应用。随着微电子技术和数
2、学理论的发展与完善，基于伪随机序列的流密码得到了长足的发展和2.1流密码的基本概念应用，在流密码中，加密和解密所用的密钥序列都是伪随机序列。伪随机序列的产生比较容易并且有比较成熟的数学理论工具。目前，流密码是世界各国的军事和外交等领域中使用的主要密码体制之一。流密码的基本思想是利用密钥k产生一个密钥流z=z0z1…，并使用如下规则对明文串x=x0x1x2…加密：y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。密钥流由密钥流发生器f产生：zi=f(k,σi)，这里σi是加密器中的记忆元件（存储器）在时刻i的状
3、态，f是由密钥k和σi产生的函数。分组密码与流密码的区别就在于有无记忆性（如图2.1）。流密码的滚动密钥z0=f(k,σ0)由函数f、密钥k和指定的初态σ0完全确定。此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，因而σi(i>0)可能依赖于k，σ0，x0，x1，…，xi-1等参数。图2.1分组密码和流密码的比较根据加密器中记忆元件的存储状态σi是否依赖于输入的明文字符，流密码可进一步分成同步和自同步两种。σi独立于明文字符的叫做同步流密码，否则叫做自同步流密码。由于自同步流密码的密钥流的产生与明文有关，因
4、而较难从理论上进行分析。目前大多数研究成果都是关于同步流密码的。在同步流密码中，由于zi=f(k,σi)与明文字符无关，因而此时密文字符yi=Ezi(xi)也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。如果与上述加密变换对应的解密变换为xi=Dzi(yi)，则可给出同步流密码体制的模型如图2.2所示。2.1.1同步流密码图2.2同步流密码体制模型同步流密码的加密变换Ezi可以有多种选择，只要保证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域CF(2)上
5、讨论的二元加法流密码（如图2.3）是目前最为常用的流密码体制，其加密变换可表示为yi=zixi。图2.3加法流密码体制模型一次一密密码是加法流密码的原型。事实上，如果zi=ki（即密钥用作滚动密钥流），则加法流密码就退化成一次一密密码。实际使用中，密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析。有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成：①有限状态集S={si
6、i=1,2,…,l}。
7、②有限输入字符集A1={A(1)j
8、j=1,2,…,m}和有限输出字符集A2={A(2)k
9、k=1,2,…,n}。③转移函数A(2)k=f1(si,A(1)j)，sh=f2(si,A(1)j)即在状态为si，输入为A(1)j时，输出为A(2)k，而状态转移为sh。2.1.2有限状态自动机例2.1S={s1,s2,s3}，A1={A(1)1,A(1)2,A(1)3}，A2={A(2)1,A(2)2,A(2)3}，转移函数由表2.1给出。（见16页表2.1）有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态
10、，若状态si在输入A(1)i时转为状态sj，且输出一字符A(2)j，则在转移图中，从状态si到状态sj有一条标有(A(1)i,A(2)j)的弧线，见图2.4。图2.4有限状态自动机的转移图例2.1中，若输入序列为A(1)1A(1)2A(1)1A(1)3A(1)3A(1)1，初始状态为s1，则得到状态序列s1s2s2s3s2s1s2输出字符序列A(2)1A(2)1A(2)2A(2)1A(2)3A(2)1同步流密码的关键是密钥流产生器。一般可将其看成一个参数为k的有限状态自动机，由一个输出符号集Z、一个状态集∑、两个函数φ和ψ以
11、及一个初始状态σ0组成（如图2.5）。状态转移函数φ:σi→σi+1，将当前状态σi变为一个新状态σi+1，输出函数ψ:σi→zi，当前状态σi变为输出符号集中的一个元素zi。这种密钥流生成器设计的关键在于找出适当的状态转移函数φ和输出函数ψ，使得输出序列z满足密钥流序列z应满足的几个条件
