第2章 流密码讲义

《第2章 流密码讲义》由会员分享，可在线阅读，更多相关《第2章 流密码讲义（62页珍藏版）》请在金锄头文库上搜索。

1、第2章 流密码,2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.4 m序列的伪随机性 2.5 m序列密码的破译 2.6 非线性序列,流密码的是利用密钥k产生一个密钥流z=z0z1，并使用如下规则对明文串x=x0x1x2加密： y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。 密钥流的长度与明文长度相同。 密钥流由密钥流发生器f产生： zi=f(k,i)，这里i是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和i产生的函数。,2.1 流密码的基本概念,1.密钥流强度依赖： 随机性 不可预测性 2.核心问题： 密钥生成器的设计 3.实现可靠解密的关键技术： 同步,

2、4.分组密码与流密码的区别：有无记忆性,流密码的滚动密钥z0=f(k,0)由函数f、密钥k和指定的初态0完全确定。此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，因而i(i0)可能依赖于k，0，x0，x1，xi-1等参数。,根据加密器中记忆元件的存储状态i是否依赖于输入的明文字符，流密码可进一步分成: 同步流密码:i独立于明文字符;（目前使用） 自同步流密码:i依赖于明文字符; 可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。,2.1.1 同步流密码,图2.2 同步流密码体制模型,同步流密码的加密变换Ezi可以有多种选择，只要保证变换是可逆的即可。 实际使用的数字

3、保密通信系统一般都是二元系统，因而在有限域GF(2)上讨论的二元加法流密码（如图2.3）是目前最为常用的流密码体制，其加密变换可表示为: yi=zi xi。,图2.3 加法流密码体制模型,密码设计者的最大愿望是设计一次一密的密码。 实际使用时，密钥流序列具有如下性质： 极大的周期 良好的统计特性 抗线性分析 抗统计分析 流密码的优点： 加密速度快、容易实现,有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成： 有限状态集S=si|i=1,2,l。 有限输入字符集A1=A(1)j|j=1,2,m 有限输出字符集A2=A(2)k|k=1,2,n。 转移函数A

4、(2)k=f1(si,A(1)j) sh=f2(si,A(1)j) 即在状态为si，输入为A(1)j时，输出为A(2)k，而状态转移为sh。 表示方法： 表 状态图（转移图）,2.1.2 有限状态自动机（FA,Finite state Automation）,例2.1 S=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给出。 表2.1 转移函数f1和f2,有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态，若状态si在输入A(1)i时转为状态sj，且输出一字符A(2)j，则在转移图中，从状态si到

5、状态sj有一条标有(A(1)i,A(2)j)的弧线，见图2.4。,例：若输入序列为: A(1)1A(1)2A(1)1A(1)3A(1)3A(1)1， 初始状态为s1，则得到状态序列: s1 s2 s2 s3 s2 s1 s2 输出字符序列: A(2)1A(2)1A(2)2A(2)1A(2)3A(2)1 图2.4 有限状态自动机的转移图,同步流密码的关键是密钥流产生器。一般可将其看成一个参数为k的有限状态自动机，由一个输出符号集Z、一个状态集、两个函数和以及一个初始状态0组成。 关键在于找出适当的状态转移函数和输出函数。 使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和

6、容易实现的。为了实现这一目标，必须采用非线性函数。,2.1.3 密钥流产生器,由于具有非线性的的有限状态自动机理论很不完善，相应的密钥流产生器的分析工作受到极大的限制。 当采用线性的和非线性的时，将能够进行深入的分析并可以得到好的生成器； 可将这类生成器分成驱动部分和非线性组合部分（如图2.6）； 驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列； 非线性组合部分要利用这些序列组合出满足要求的密钥流序列。,图2.6 密钥流生成器的分解,图2.7 常见的两种密钥流产生器,目前最为流行和实用的密钥流产生器如图2.7所示，其驱动部分是一个或多个线性反馈移位寄存器。,移位寄存器是流

7、密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,an)组成.,2.2 线性反馈移位寄存器,图2.8 GF(2)上的n级反馈移位寄存器,每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列 a1,a2,an 或n维向量 (a1,a2,an) 表示，其中ai是第i级存储器的内容。,初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并根据寄存器此时的状态a1,a2,an

8、计算f(a1,a2,an)，作为下一时刻的an。反馈函数f(a1,a2,an)是n元布尔函数，即n个变元a1,a2,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。,例2.2 图2.9是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出。,图2.9 一个3级反馈移位寄存器,表2.2 一个3级反馈移位寄存器 的状态和输出,即输出序列为101110111011，周期为4。,如果移位寄存器的反馈函数f(a1,a2,an)是a1，a2，an的线性函数，则称之为线性反馈移位寄存器LFSR（linear

9、feedback shift register）。 此时f可写为： f(a1,a2,an)=cna1cn-1a2c1an 其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如图2.10所示。,图2.10 GF(2)上的n级线性反馈移位寄存器,输出序列at满足 an+t=cnat cn-1at+1 c1an+t-1 其中t为非负正整数。 线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。,例2.3 图2.11是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序

10、列为 1001101001000010101110110001111100110 周期为31。,图2.11 一个5级线性反馈移位寄存器,在线性反馈移位寄存器中总是假定c1,c2,cn中至少有一个不为0，否则f(a1,a2,an)0，这样的话，在n个脉冲后状态必然是000，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。 一般对于n级线性反馈移位寄存器，总是假定cn=1。,线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。 n级线性反馈移位寄存器最多有2n个不同的状态。 若其初始状态为0，则其状态恒为0。若其初始状态非0，则其后继状态不会为0。因此n

11、级线性反馈移位寄存器的状态周期小于等于2n-1。其输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1， 周期达到最大值的序列称为m序列。,设n级线性移位寄存器的输出序列满足递推关系 an+k=c1an+k-1 c2an+k-2 cnak (*) 对任何成立。这种递推关系可用一个一元高次多项式 P(x)=1+c1x+cn+1xn-1cnxn 表示，称这个多项式为LFSR的特征多项式或特征多项式。,2.3 线性移位寄存器的一元多项式表示,流密码的安全性取决于: 随机性 无法预测 伪随机序列: 要求截获比周期短的一段时不会泄露更多信息。 周期：

12、 序列ki,使得对所有的ki+p=ki的最小整数p 长为L的串（游程）： 设ai=(a1a2a3)为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。,2.4 m序列的伪随机性,自相关函数： GF(2)上周期为T的序列ai的自相关函数定义为： R()=(1/T) (-1)ak(-1)ak+,0T-1 定义中的和式表示序列ai与ai+（序列ai向后平移位得到）在一个周期内对应位相同的位数与对应位不同的位数之差。 同相自相关函数：当=0时，R()=1； 异相自相关函数：当0时，R()为异相自相关函数。,例：二元序列111

13、001011100101110010 周期为7 同相自相关函数为：1 异相自相关函数为：-1/7,Golomb对伪随机周期序列提出了应满足的如下3个随机性公设： 在序列的一个周期内，0与1的个数相差至多为1。 在序列的一个周期内，长为i的游程占游程总数的1/2i (i=1,2,)，且在等长的游程中0的游程个数和1的游程个数相等。 异相自相关函数是一个常数。 这种序列叫PN序列，类似白噪声序列。满足公设的序列可以用于通信、CDMA寻址、导航基站测距等。 m序列满足Golomb的3个随机性公设。,从密码系统的角度看，一个伪随机序列还应满足下面的条件： ai的周期相当大。 ai的确定在计算上是容易的

14、。 由密文及相应的明文的部分信息，不能确定整个ai。 m序列不满足,m序列用于通信较多，用于密钥流不够安全。,设序列ai满足线性递推关系： 设敌手知道一段长为2n的明密文对，即已知,2.5 m序列密码的破译,于是可求出一段长为2n的密钥序列 其中 ,由此可推出线性反馈移位寄存器连续的n+1个状态：,而 若X可逆，则,例2.6 设敌手得到密文串101101011110010和相应的明文串011001111111001，假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，破译过程如下： （1）计算出相应的密钥流为110100100001011。 （2）用密钥流中前10个比特建立如下方程,即 而

15、,从而得到 所以 密钥流的递推关系为,本节介绍第2部分非线性组合子系统。,2.6 非线性序列,LFSR 虽然不能直接作为密钥流使用，但可以作为驱动源使用。 下面介绍4种由多个LFSR驱动的非线性序列生成器。,由3个LFSR组成，其中LFSR2作为控制生成器使用,2.6.1 Geffe序列生成器,图2.12 Geffe序列生成器图,当LFSR2输出1时，LFSR2与LFSR1相连接； 当LFSR2输出0时，LFSR2与LFSR3相连接。 若设LFSRi的输出序列为a(i)k (i=1,2,3)，则输出序列bk可以表示为,Geffe序列生成器也可以表示为图2.13的形式，其中LFSR1和LFSR3作为多路复合器的输入，LFSR2控制多路复合器的输出。设LFSRi的特征多项式分别为ni次本原多项式，且ni两两互素，则Geffe序列的周期为,图2.13 多路复合器表示的Geffe序列生成器,Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的。 缺点：与LFSR2的相关系数较高，容易受到攻击。,图2.14 J-K触发器,2.6.2 J-K触发器,它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即 其中x1和x2分别是J和K端的输入。由