第2章 流密码

1、第第2章章 流密码流密码 2.1 流密码的基本概念流密码的基本概念 2.2 线性反馈移位寄存器线性反馈移位寄存器 2.4 m序列的伪随机性序列的伪随机性 2.5 m序列密码的破译序列密码的破译 2.6 非线性序列非线性序列 流密码的是利用密钥流密码的是利用密钥k产生一个密钥流产生一个密钥流z=z0z1，并使用如并使用如 下规则对明文串下规则对明文串x=x0 x1x2加密：加密： y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。 密钥流的长度与明文长度相同。密钥流的长度与明文长度相同。 密钥流由密钥流发生器密钥流由密钥流发生器f产生：产生： zi=f(k,i)，这里这里i是加密器是

2、加密器 中的记忆元件（存储器）在时刻中的记忆元件（存储器）在时刻i的状态，的状态，f是由密钥是由密钥k和和i 产生的函数。产生的函数。 2.1 流密码的基本概念流密码的基本概念 1.密钥流强度依赖：密钥流强度依赖： 随机性随机性 不可预测性不可预测性 2.核心问题：核心问题： 密钥生成器的设计密钥生成器的设计 3.实现可靠解密的关键技术：实现可靠解密的关键技术： 同步同步 4.分组密码与流密码的区别：分组密码与流密码的区别：有无记忆性有无记忆性 流密码的滚动密钥流密码的滚动密钥z0=f(k,0)由函数由函数f、密钥密钥k和指和指 定的初态定的初态0完全确定。此后，由于输入加密器的明文完全确定。

3、此后，由于输入加密器的明文 可能影响加密器中内部记忆元件的存储状态，因而可能影响加密器中内部记忆元件的存储状态，因而 i(i0)可能依赖于可能依赖于k，0， ，x0， ，x1，xi-1等参数。等参数。 根据加密器中记忆元件的存储状态根据加密器中记忆元件的存储状态i是否依赖是否依赖 于输入的明文字符，流密码可进一步分成于输入的明文字符，流密码可进一步分成: 同步流密码同步流密码:i独立于明文字符独立于明文字符;（目前使用）（目前使用） 自同步流密码自同步流密码:i依赖于明文字符依赖于明文字符; 可将同步流密码的加密器分成可将同步流密码的加密器分成密钥流产生器密钥流产生器和和 加密变换器加密变换器

4、两个部分。两个部分。 2.1.1 同步流密码同步流密码 图图2.2 同步流密码体制模型同步流密码体制模型 同步流密码的加密变换同步流密码的加密变换Ezi可以有多种选择，只可以有多种选择，只 要保证变换是可逆的即可。要保证变换是可逆的即可。 实际使用的数字保密通信系统一般都是实际使用的数字保密通信系统一般都是二元系二元系 统统，因而在有限域，因而在有限域GF(2)上讨论的上讨论的二元加法流密码二元加法流密码 （如图（如图2.3）是目前最为常用的流密码体制，其加）是目前最为常用的流密码体制，其加 密变换可表示为密变换可表示为: : yi=zi xi。 图图2.3 加法流密码体制模型加法流密码体制模

5、型 密码设计者的最大愿望是设计一次一密的密码。密码设计者的最大愿望是设计一次一密的密码。 实际使用时，密钥流序列具有如下性质：实际使用时，密钥流序列具有如下性质： 极大的周期极大的周期 良好的统计特性良好的统计特性 抗线性分析抗线性分析 抗统计分析抗统计分析 流密码的优点：流密码的优点： 加密速度快、容易实现加密速度快、容易实现 有限状态自动机是具有离散输入和输出（输入集和有限状态自动机是具有离散输入和输出（输入集和 输出集均有限）的一种数学模型，由以下输出集均有限）的一种数学模型，由以下3部分组部分组 成：成： 有限状态集有限状态集S=si|i=1,2,l。 有限输入字符集有限输入字符集A1

6、=A(1)j|j=1,2,m 有限输出字符集有限输出字符集A2=A(2)k|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 有限状态自动机（有限状态自动机（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， 转移函数由表转移函数由

7、表2.1给出。给出。 表表2.1 转移函数转移函数f1和和f2 A1(1)A2(1)A3(1)A1(1)A2(1)A3(1) S1A1(2)A3(2)A2(2)S1S2S1S3 S2A2(2)A1(2)A3(2)S2S3S2S1 S3A3(2)A2(2)A1(2)S3S1S3S2 有限状态自动机可用有向图表示，称为有限状态自动机可用有向图表示，称为转移图转移图。 转移图的顶点对应于自动机的状态，若状态转移图的顶点对应于自动机的状态，若状态si在输在输 入入A(1)i时转为状态时转为状态sj，且输出一字符且输出一字符A(2)j，则在转移则在转移 图中，从状态图中，从状态si到状态到状态sj有一条

8、标有有一条标有(A(1)i,A(2)j)的弧的弧 线，见图线，见图2.4。 A1(1)A2(1)A3(1)A1(1)A2(1)A3(1) S1A1(2)A3(2)A2(2)S1S2S1S3 S2A2(2)A1(2)A3(2)S2S3S2S1 S3A3(2)A2(2)A1(2)S3S1S3S2 例：若输入序列为例：若输入序列为: 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 有限

9、状态自动机的转移图有限状态自动机的转移图 同步流密码的关键是密钥流产生器。一般可将其看成一个同步流密码的关键是密钥流产生器。一般可将其看成一个参数为参数为k 的有限状态自动机的有限状态自动机，由一个输出符号集，由一个输出符号集Z、一个状态集一个状态集、两个函数、两个函数 和和以及一个初始状态以及一个初始状态0组成。组成。 关键在于找出适当的状态转移函数关键在于找出适当的状态转移函数和输出函数和输出函数。 使得输出序列使得输出序列z满足密钥流序列满足密钥流序列z应满足的几个条件，并且要求在应满足的几个条件，并且要求在 设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性设备上是节省的和容

10、易实现的。为了实现这一目标，必须采用非线性 函数。函数。 2.1.3 密钥流产生器密钥流产生器 由于具有非线性的由于具有非线性的的有限状态自动机理论很的有限状态自动机理论很 不完善，相应的密钥流产生器的分析工作受到极大不完善，相应的密钥流产生器的分析工作受到极大 的限制。的限制。 当当采用线性的采用线性的和非线性的和非线性的时，将能够进行时，将能够进行 深入的分析并可以得到好的生成器；深入的分析并可以得到好的生成器； 可将这类生成器分成可将这类生成器分成驱动部分和非线性组合驱动部分和非线性组合部部 分（如图分（如图2.6）；）； 驱动部分驱动部分控制生成器的状态转移，并为非线控制生成器的状态转

11、移，并为非线 性组合部分提供统计性能好的序列；性组合部分提供统计性能好的序列； 非线性组合部分非线性组合部分要利用这些序列组合出满足要要利用这些序列组合出满足要 求的密钥流序列。求的密钥流序列。 图图2.6 密钥流生成器的分解密钥流生成器的分解 图图2.7 常见的两种密钥流产生器常见的两种密钥流产生器 目前最为流行和实用的密钥流产生器如图目前最为流行和实用的密钥流产生器如图2.7所示，所示， 其驱动部分是一个或多个线性反馈移位寄存器。其驱动部分是一个或多个线性反馈移位寄存器。 移位寄存器是流密码产生密钥流的一个主要组移位寄存器是流密码产生密钥流的一个主要组 成部分。成部分。GF(2)上一个上一

12、个n级反馈移位寄存器由级反馈移位寄存器由n个二个二 元存储器与一个反馈函数元存储器与一个反馈函数f(a1,a2,an)组成组成. 2.2 线性反馈移位寄存器线性反馈移位寄存器 图图2.8 GF(2)上的上的n级反馈移位寄存器级反馈移位寄存器 每一存储器称为移位寄存器的一级，在任一时刻，每一存储器称为移位寄存器的一级，在任一时刻， 这些级的内容构成该反馈移位寄存器的状态，每一这些级的内容构成该反馈移位寄存器的状态，每一 状态对应于状态对应于GF(2)上的一个上的一个n维向量，共有维向量，共有2n种可能种可能 的状态。每一时刻的状态可用的状态。每一时刻的状态可用n长序列长序列 a1,a2,an 或

13、或n维向量维向量 (a1,a2,an) 表示，其中表示，其中ai是第是第i级存储器的内容。级存储器的内容。 初始状态由用户确定，当第初始状态由用户确定，当第i个移位时钟脉冲到来个移位时钟脉冲到来 时，每一级存储器时，每一级存储器ai都将其内容向下一级都将其内容向下一级ai-1传递，传递， 并根据寄存器此时的状态并根据寄存器此时的状态a1,a2,an计算计算 f(a1,a2,an)，作为下一时刻的作为下一时刻的an。反馈函数反馈函数 f(a1,a2,an)是是n元布尔函数，即元布尔函数，即n个变元个变元a1,a2,an 可以独立地取可以独立地取0和和1这两个可能的值，函数中的运算这两个可能的值，

14、函数中的运算 有逻辑与、逻辑或、逻辑补等运算，最后的函数值有逻辑与、逻辑或、逻辑补等运算，最后的函数值 也为也为0或或1。 例例2.2 图图2.9是一个是一个3级反馈移位寄存器，其初始状级反馈移位寄存器，其初始状 态为态为(a1,a2,a3)=(1,0,1)，输出可由表输出可由表2.2求出。求出。 图图2.9 一个一个3级反馈移位寄存器级反馈移位寄存器 表表2.2 一个一个3级反馈移位寄存器级反馈移位寄存器 的状态和输出的状态和输出 状态状态 （a3,a2,a1) 输出输出 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 即输出序列为即输出序列为

15、101110111011，周期为，周期为4。 如果移位寄存器的反馈函数如果移位寄存器的反馈函数f(a1,a2,an)是是a1， a2，an的线性函数，则称之为的线性函数，则称之为线性反馈移位寄线性反馈移位寄 存器存器LFSR（linear feedback shift register）。）。 此时此时f可写为：可写为： f(a1,a2,an)=cna1cn-1a2c1an 其中常数其中常数ci=0或或1，是模是模2加法。加法。ci=0或或1可用可用 开关的断开和闭合来实现，如图开关的断开和闭合来实现，如图2.10所示。所示。 图图2.10 GF(2)上的上的n级线性反馈移位寄存器级线性反馈移

16、位寄存器 输出序列输出序列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)，可求出输出可求出输出 序列为序列为 10011010010000101011101

17、10001111100110 周期为周期为31。 图图2.11 一个一个5级线性反馈移位寄存器级线性反馈移位寄存器 在线性反馈移位寄存器中总是假定在线性反馈移位寄存器中总是假定c1,c2,cn中至少中至少 有一个不为有一个不为0，否则，否则f(a1,a2,an)0，这样的话，在这样的话，在 n个脉冲后状态必然是个脉冲后状态必然是000，且这个状态必将一直，且这个状态必将一直 持续下去。若只有一个系数不为持续下去。若只有一个系数不为0，设仅有，设仅有cj不为不为0， 实际上是一种延迟装置。实际上是一种延迟装置。 一般对于一般对于n级线性反馈移位寄存器，总是假定级线性反馈移位寄存器，总是假定cn=

18、1。 线性反馈移位寄存器输出序列的性质完全由其反馈线性反馈移位寄存器输出序列的性质完全由其反馈 函数决定。函数决定。 n级线性反馈移位寄存器最多有级线性反馈移位寄存器最多有2n个不同的状态。个不同的状态。 若其初始状态为若其初始状态为0 0，则其状态恒为，则其状态恒为0 0。若其初始状态非。若其初始状态非0 0，则其后继状态，则其后继状态 不会为不会为0 0。因此。因此n n级线性反馈移位寄存器的状态周期小于等于级线性反馈移位寄存器的状态周期小于等于2 2n n-1-1。其输其输 出序列的周期与状态周期相等，也小于等于出序列的周期与状态周期相等，也小于等于2 2n n-1-1。只要选择合适的反

19、馈只要选择合适的反馈 函数便可使序列的周期达到最大值函数便可使序列的周期达到最大值2 2n n-1-1， 周期达到最大值的序列称为周期达到最大值的序列称为m序列。序列。 设设n级线性移位寄存器的输出序列满足递推关系级线性移位寄存器的输出序列满足递推关系 an+k=c1an+k-1 c2an+k-2 cnak (*) 对任何成立。这种递推关系可用一个一元高次多项对任何成立。这种递推关系可用一个一元高次多项 式式 P(x)=1+c1x+cn+1xn-1cnxn 表示，称这个多项式为表示，称这个多项式为LFSR的的特征多项式特征多项式或特征或特征 多项式。多项式。 2.3 线性移位寄存器的一元多项式

20、表示线性移位寄存器的一元多项式表示 流密码的安全性取决于流密码的安全性取决于: 随机性随机性 无法预测无法预测 伪随机序列伪随机序列: 要求截获比周期短的一段时不会泄露更多信息。要求截获比周期短的一段时不会泄露更多信息。 周期：周期： 序列序列ki,使得对所有的使得对所有的ki+p=ki的最小整数的最小整数p 长为长为L的串（游程）：的串（游程）： 设设ai=(a1a2a3)为为0、1序列，例如序列，例如00110111，其前两个数字是，其前两个数字是00，称为，称为0 的的2游程；接着是游程；接着是11，是，是1的的2游程；再下来是游程；再下来是0的的1游程和游程和1的的3游程。游程。 2.

21、4 m序列的伪随机性序列的伪随机性 自相关函数自相关函数： GF(2)上周期为上周期为T的序列的序列ai的自相关函数定义的自相关函数定义 为：为： R()=(1/T) (-1)ak(-1)ak+,0T-1 定义中的和式表示序列定义中的和式表示序列ai与与ai+（序列序列ai 向后平移向后平移位得到）位得到）在一个周期内对应位相同的位在一个周期内对应位相同的位 数与对应位不同的位数之差数与对应位不同的位数之差。 同相自相关函数：同相自相关函数：当当=0时，时，R()=1； 异相自相关函数：异相自相关函数：当当0时，时，R()为异相自相关函为异相自相关函 数。数。 例：二元序列例：二元序列1110

22、01011100101110010 周期为周期为7 同相自相关函数为：同相自相关函数为：1 异相自相关函数为：异相自相关函数为：-1/7 Golomb对伪随机周期序列提出了应满足的如下对伪随机周期序列提出了应满足的如下3个个 随机性公设：随机性公设： 在序列的一个周期内，在序列的一个周期内，0与与1的个数相差至多为的个数相差至多为1。 在序列的一个周期内，长为在序列的一个周期内，长为i的游程占游程总数的的游程占游程总数的1/2i (i=1,2,)，且在等长的游程中且在等长的游程中0的游程个数和的游程个数和1的游程个数的游程个数 相等。相等。 异相自相关函数是一个常数。异相自相关函数是一个常数。

23、 这种序列叫这种序列叫PN序列，类似白噪声序列。满足公设序列，类似白噪声序列。满足公设 的序列可以用于通信、的序列可以用于通信、CDMA寻址、导航基站测距寻址、导航基站测距 等。等。 m序列满足序列满足Golomb的的3个随机性公设。个随机性公设。 从密码系统的角度看，一个伪随机序列还应满足下从密码系统的角度看，一个伪随机序列还应满足下 面的条件：面的条件： ai的周期相当大。的周期相当大。 ai的确定在计算上是容易的。的确定在计算上是容易的。 由密文及相应的明文的部分信息，不能确定整个由密文及相应的明文的部分信息，不能确定整个ai。 m序列不满足序列不满足,m序列用于通信较多，用于密钥流不够

24、安序列用于通信较多，用于密钥流不够安 全。全。 设序列设序列ai满足线性递推关系：满足线性递推关系： 设敌手知道一段长为设敌手知道一段长为2n的明密文对，即已知的明密文对，即已知 2.5 m序列密码的破译序列密码的破译 122n xx xx 122n yy yy 1122h nh nh nnh ac ac ac a 于是可求出一段长为于是可求出一段长为2n的密钥序列的密钥序列 其中其中 ,由此可推出线性由此可推出线性 反馈移位寄存器连续的反馈移位寄存器连续的n+1个状态：个状态： 1 22n zz zz iiiiii zxyxxz 11 212 2231231 1122122 nn nn nn

25、nnnnn Sz zza aa Sz zza aa Szzzaaa 记为 记为 记为 而而 若若X可逆，则可逆，则 12 231 12211 121 11 n n nnnnn nnn nn aaa aaa aaaccc aaa cccX 1 11122nnnnn cccaaaX 例例2.6 设敌手得到密文串设敌手得到密文串101101011110010和相应的明文串和相应的明文串 011001111111001，假定敌手还知道密钥流是使用，假定敌手还知道密钥流是使用5级线性反级线性反 馈移位寄存器产生的，破译过程如下：馈移位寄存器产生的，破译过程如下： （1）计算出相应的密钥流为）计算出相应的

26、密钥流为110100100001011。 （2）用密钥流中前）用密钥流中前10个比特建立如下方程个比特建立如下方程 12345 23456 6789105432134567 45678 56789 aaaaa aaaaa aaaaacccccaaaaa aaaaa aaaaa 即即 而而 54321 1 1 0 1 0 1 0 1 0 0 0 1 0 0 00 1 0 0 1 1 0 0 1 0 0 0 1 0 0 ccccc 1 1 1 0 1 00 1 0 0 1 1 0 1 0 01 0 0 1 0 0 1 0 0 10 0 0 0 1 1 0 0 1 00 1 0 1 1 0 0 1

27、0 01 0 1 1 0 从而得到从而得到 所以所以 密钥流的递推关系为密钥流的递推关系为 54321 0 1 0 0 1 1 0 0 1 0 0 1 0 0 00 0 0 0 1 0 1 0 1 1 1 0 1 1 0 ccccc 54321 1 0 0 1 0ccccc 55233iiiii ac ac aaa 本节介绍第本节介绍第2部分非线性组合子系统。部分非线性组合子系统。 2.6 非线性序列非线性序列 LFSR 虽然不能直接作为密钥流使用，但可以作为驱虽然不能直接作为密钥流使用，但可以作为驱 动源使用。动源使用。 下面介绍下面介绍4种由多个种由多个LFSR驱动的非线性序列生成器驱动的

28、非线性序列生成器。 由由3个个LFSR组成，其中组成，其中LFSR2作为控制生成器使用作为控制生成器使用 2.6.1 2.6.1 GeffeGeffe序列生成器序列生成器 图图2.12 Geffe序列生成器图序列生成器图 当当LFSR2输出输出1时，时，LFSR2与与LFSR1相连接；相连接； 当当LFSR2输出输出0时，时，LFSR2与与LFSR3相连接。相连接。 若设若设LFSRi的输出序列为的输出序列为a(i)k (i=1,2,3)，则输则输 出序列出序列bk可以表示为可以表示为 123212323 kkkkkkkkkk ba aaaa aa aa Geffe序列生成器也可以表示为图序列

29、生成器也可以表示为图2.13的形式，其中的形式，其中 LFSR1和和LFSR3作为多路复合器的输入，作为多路复合器的输入，LFSR2控控 制多路复合器的输出。设制多路复合器的输出。设LFSRi的特征多项式分别的特征多项式分别 为为ni次本原多项式，且次本原多项式，且ni两两互素，则两两互素，则Geffe序列的序列的 周期为周期为 3 1 21 i n i 图图2.13 多路复合器表示的多路复合器表示的Geffe序列生成器序列生成器 Geffe序列的周期实现了极大化，且序列的周期实现了极大化，且0与与1之间的分之间的分 布大体上是平衡的。布大体上是平衡的。 缺点：与缺点：与LFSR2的相关系数较

30、高，容易受到攻击。的相关系数较高，容易受到攻击。 图图2.14 J-K触发器触发器 2.6.2 2.6.2 J-KJ-K触发器触发器 它的两个输入端分别用它的两个输入端分别用J和和K表示，其输出表示，其输出ck不不 仅依赖于输入，还依赖于前一个输出位仅依赖于输入，还依赖于前一个输出位ck-1，即即 其中其中x1和和x2分别是分别是J和和K端的输入。由此可得端的输入。由此可得J- K触发器的真值表，如表触发器的真值表，如表2.3。 1211kk cxxcx 图图2.15 利用利用J-K触发器的非线性序列生成器触发器的非线性序列生成器 利用利用J-K触发器的非线性序列生成器见图触发器的非线性序列生

31、成器见图2.15。 在图在图2.15中，令驱动序列中，令驱动序列ak和和bk分别为分别为m级和级和n 级级m序列，则有序列，则有 如果令如果令c-1=0，则输出序列的最初则输出序列的最初3项为项为 当当m与与n互素且互素且a0+b0=1时，序列时，序列ck的周期为的周期为(2m- 1)(2n-1)。 11 1 kkkkkkkkk cabcaabca 00 11101 22211012 1 11 ca cabaa cababaaa 例例2.7 令令m=2,n=3，两个驱动两个驱动m序列分别为序列分别为 ak=0,1,1, 和和 bk=1,0,0,1,0,1,1, 于是，输出序列于是，输出序列ck

32、是是 0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0, 其周期为其周期为(22-1)(23-1)=21。 由表达式由表达式 可得可得 因此，如果知道因此，如果知道ck中相邻位的值中相邻位的值ck-1和和ck，就就 可以推断出可以推断出ak和和bk中的一个。而一旦知道足够多的中的一个。而一旦知道足够多的 这类信息，就可通过密码分析的方法得到序列这类信息，就可通过密码分析的方法得到序列ak 和和bk。 为了克服上述缺点，为了克服上述缺点，Pless提出了由多个提出了由多个J-K触触 发器序列驱动的多路复合序列方案，称为发器序列驱动的多路复合序列方案，称为Ples

33、s生成生成 器。器。 1 1 ,0 ,1 kk k kk ac c bc 11 1 kkkkkkkkk cabcaabca 由由8个个LFSR、4个个J-K触发器和触发器和1个循环计数器构成，由循环计个循环计数器构成，由循环计 数器进行选通控制。假定在时刻数器进行选通控制。假定在时刻t输出第输出第t(mod 4)个单元，则输个单元，则输 出序列为：出序列为：a0b1c2d3a4b5d6 2.6.3 2.6.3 PlessPless生成器生成器 图图2.17 最简单的钟控序列生成器最简单的钟控序列生成器 用一个用一个LFSR控制另外一个控制另外一个LFSR的移位时钟脉冲，的移位时钟脉冲， 如图如图2.17所示。所示。 2.6.4 2.6.4 钟控序列生成器钟控序列生成器 假设假设LFSR1和和LFSR2分别输出序列分别输出序列ak和和