现代密码学课件第2章

现代密码学

第2章流密码

2.1流密码的基本概念2.2线性反馈移位寄存器2.3线性移位寄存器的一元多项式表示2.4m序列的伪随机性2.5m序列的破译2.6非线性序列2.1流密码的基本概念第二章流密码

流密码的基本思想是利用密钥产生一个密钥流，并使用如下规则对明文串加密：。密钥流由密钥流发生器产生：，这里是加密器中的记忆元件（存储器）在时刻的状态，是由密钥和产生的函数。分组密码流密码图2-1分组密码和流密码的比较2.1流密码的基本概念第二章流密码分组密码与流密码的区别就在于有无记忆性，如下图。

在同步流密码中，由于与明文字符无关，因而此时密文字符也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。如果与上述加密变换对应的解密变换为，则我们可给出同步流密码的模型如图所示。图2.1.1同步流密码体制模型2.1.1同步流密码第二章流密码图2.1.1-1加法流密码体制模型2.1.1同步流密码第二章流密码

同步流密码的加密变换可以有多种选择，只要保证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域上讨论的二元加法流密码（如下图）是目前最为常用的流密码体制，其加密变换可表示为。第二章流密码2.1.2有限状态自动机

有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成：有限状态集有限输入字符集和有限输出字符集转移函数即在状态为，输入为

时，输出为

，而状态转移为。第二章流密码2.1.2有限状态自动机例2-1

转移函数由表2-1给出。有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态，若状态在输入时转为状态，且输出一字符，则在转移图中，从状态到状态有一条标有

的弧线。第二章流密码2.1.2有限状态自动机表2-1转移函数和第二章流密码2.1.2有限状态自动机例2-1图2-1有限状态自动机的转移图例2-1中，若输入序列为，初始状态为，则得到状态序列输出字符序列：第二章流密码2.1.2密钥流产生器同步流密码的关键是密钥流产生器。一般可将其看成一个参数为的有限状态自动机，由一个输出符号集、一个状态集、两个函数和以及一个初始状态组成（如图2-5）。状态转移函数，将当前状态变为一个新状态，输出函数，当前状态变为输出符号集中的一个元素。这种密钥流生成器设计的关键在于找出适当的状态转移函数和输出函数，使得输出序列满足密钥流序列应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数。第二章流密码2.1.2密钥流产生器图2.1.2-1作为有限状态自动机的密钥流生成器

图2.1.2-2密钥流生成器的分解第二章流密码2.1.2密钥流产生器

由于具有非线性的的有限状态自动机理论很不完善，相应的密钥流产生器的分析工作受到极大的限制。相反地，当采用线性的和非线性的时，我们将能够进行深入的分析并可以得到好的生成器。为方便，可将这类生成器分成驱动部分和非线性组合部分。驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列。而非线性组合部分要利用这些序列组合出满足要求的密钥流序列。

目前最为流行和实用的密钥流产生器如图所示，其驱动部分是一个或多个线性反馈移位寄存器。第二章流密码2.1.2密钥流产生器图2-7常见的两种密钥流产生器第二章流密码2.2线性反馈移位寄存器

移位寄存器是流密码产生密钥流的一个主要组成部分。上一个级反馈移位寄存器由个二元存储器与一个反馈函数组成，如图2-2所示。图2-2-1上的n级反馈移位寄存器2.2线性反馈移位寄存器第二章流密码例2-2

下图是一个3级反馈移位寄存器，其初始状态为，输出可由下表求出。图2-2-2一个3级反馈移位寄存器第二章流密码2.2线性反馈移位寄存器例2-2状态输出状态输出10111011110011001111…………0111…………表2-2一个3级反馈移位寄存器的状态和输出第二章流密码2.2线性反馈移位寄存器例2-2即输出序列为10111011101，周期为4。如果移位寄存器的反馈函数是的线性函数，则称之为线性反馈移位寄存器LFSR（LinearFeedbackShiftRegister）。此时可写为

第二章流密码2.2线性反馈移位寄存器图2-10上的级线性反馈移位寄存器

其中常数或1，是模2加法。或1可用开关的断开和闭合来实现，如图2-10所示。第二章流密码2.2线性反馈移位寄存器输出序列满足,其中为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。第二章流密码2.2线性反馈移位寄存器例2-3

下图是一个5级线性反馈移位寄存器，其初始状态为，可求出输出序列为100110100100001010111011000111110011…周期为31。图2-11

一个5级线性反馈移位寄存器第二章流密码2.2线性反馈移位寄存器例2-3

在线性反馈移位寄存器中总是假定中至少由一个不为0，否则，这样的话，在个脉冲后状态必然是，且这个状态必将一直持续下去。第二章流密码2.3线性反馈移位寄存器的一元多项式表示设级线性移位寄存器的输出序列满足递推关系（*）对任何成立。这种递推关系可用一个一元高次多项式表示，称这个多项式为LFSR的特征多项式或特征多项式。设级线性移位寄存器对应于递推关系（*），由于，所以共有组初始状态，即有个递推序列，其中非恒零的有个，记个非零序列的全体为。2.3线性反馈移位寄存器的一元多项式表示第二章流密码定义2-1给定序列，幂级数称为该序列的生成函数。定理2-1设是上的多项式，中任一序列的生成函数满足：其中第二章流密码2.3线性反馈移位寄存器的一元多项式表示定理2-1证明：两边分别乘以，再求和，可得移项整理得即注意在上有。第二章流密码2.3线性反馈移位寄存器的一元多项式表示定理2-2

的充要条件是

。证明：若，可设，因此所以若

，则，即第二章流密码2.3线性反馈移位寄存器的一元多项式表示定理2-2反之，若，则对于多项式，存在序列以为生成函数。特别的，对于多项式，存在序列以为生成函数。由于，序列，所以存在函数，使得

的生成函数也等于，从而，即，所以。上述定理说明可用N级LFSR产生的序列，也可用级数更多的LFSR来产生。第二章流密码2.3线性反馈移位寄存器的一元多项式表示定义2-2设是上的多项式，使的最小称为的周期或阶。定理2-3若序列的特征多项式定义在上，是的周期，则的周期。第二章流密码2.3线性反馈移位寄存器的一元多项式表示证明：由周期的定义得，因此存在，使得，又由可以得到式子

所以。因的次数不超过。

由知的次数不超过。又知

的次数不超过，所以的次数不超过式

。将写成，可看出对于任意正整数都有。设，则，所以，即。第二章流密码2.3线性反馈移位寄存器的一元多项式表示定义2-3仅能被非0常数或自身的常数倍除尽，但不能被其它多项式除尽的多项式称为即约多项式或不可约多项式。定理2-4设是次不可约多项式，周期为，序列

，则的周期为。2.3线性反馈移位寄存器的一元多项式表示第二章流密码定理2-4证明：设的周期为，由定理2-3有，所以。设为的生成函数，，即，的次数不超过。而2.3线性反馈移位寄存器的一元多项式表示第二章流密码定理2-4证明：于是，即为因是不可约的且的次数不超过

，所以，，因此。综上。第二章流密码2.3线性反馈移位寄存器的一元多项式表示定理2-5

级LFSR产生的序列有最大周期的必要条件是其特征多项式为不可约的。证明：设级LFSR产生的序列周期达到最大，除0序列外，每一序列的周期由特征多项式惟一决定，而与初始状态无关。设特征多项式为，若可约，可设为

，其中是不可约多项式，且次数。由于，而中序列的周期一方面不超过

，另一方面又等于，这是矛盾的，所以是不可约多项式，该定理的逆不成立。2.3线性反馈移位寄存器的一元多项式表示第二章流密码

例2-4为上的不可约多项式，这是因为一次多项式都不能整除，因此任一三次多项式也不能整除。而二次多项式有（在上），。由都不能整除知都不能整除，二次不可约多项式不能整除可直接验证。以为特征多项式的LFSR的输出序列可由和给定的初始状态求出，设初始状态为0001，则输出序列为00011000110001…，周期为5，不是序列。2.3线性反馈移位寄存器的一元多项式表示第二章流密码定义2-4若次不可约多项式的阶为，则称是次本原多项式。定理2-6设，为序列的充要条件是为本原多项式。2.3线性反馈移位寄存器的一元多项式表示第二章流密码定理2-6证明：

若是本原多项式，则其阶为，由定理2-4得的周期等于，即为序列。反之，若为序列，即其周期等于，由定理2-5知是不可约多项式。由定理2-3知的周期整除的阶，而的阶不超过，所以的阶为，即是本原多项式。2.3线性反馈移位寄存器的一元多项式表示第二章流密码例2-5设，由于，但不存在小于15的常数，使得，所以的阶为15。类似于例2-4，的不可约性可由都不能整除得到，所以是本原多项式。若LFSR以为特征多项式，则输出序列的递推关系为

若初始状态为1001，则输出为10010001111010110010001111010周期为，即输出序列为序列。2.4m序列的伪随机性第二章流密码流密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。2.4m序列的伪随机性第二章流密码为讨论序列的随机性，我们先讨论随机序列的一般特性。设为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。定义2-5上周期为的序列的自相关函数定义为当时，；当时，称为异相自相关函数。2.4m序列的伪随机性第二章流密码Golomb对伪随机周期序列提出了应满足的如下三个随机性公设：在序列的一个周期内，0与1的个数相差至多为1。在序列的一个周期内，长为1的游程占游程总数的，长为2的游程占游程总数的，，长为的游程占游程总数的，，且在等长的游程中0的游程个数和1的游程个数相等。异自相关函数是一个常数。2.4m序列的伪随机性第二章流密码从密码系统的角度看，一个伪随机序列还应满足下面的条件：的周期相当大。的确定是计算上容易的。由密文及相应的明文的部分信息,不能确定整个。下一定理说明，序列满足Golomb的三个随机性公设。2.4m序列的伪随机性第二章流密码

定理2-7上的长序列具有如下性质：在一个周期内，0、1出现的次数分别为和。在一个周期内，总游程数为；对，长为的游程有个，且0、1游程各半；长为的0游程一个，长为的1游程一个；的自相关函数为

2.4m序列的伪随机性第二章流密码

定理2-7

证明：在长序列的一个周期内，除了全0状态外，每个长状态（共有个）都恰好出现一次，这些状态中有个在位是1，其余个状态在位是0。2.4m序列的伪随机性

定理2-7

证明：第二章流密码对，易证结论成立。对，当时，长序列的一个周期内，长为的0游程数目等于序列中如下形式的状态数目：，其中个可任取0或1。这种状态共有个。同理可得长为的1游程数目也等于，所以长为的游程总数为

。由于寄存器中不会出现全0状态，所以不会出现0的游程，但必有一个1的游程，而且1的游程不会更大，因为若出现1的游程，就必然有两个相邻的全1状态，但这是不可能的。2.4m序列的伪随机性

定理2-7

证明：第二章流密码这就证明了在1的游程必然出现在如下的串中：

当这位通过移位寄存器时，便依次产生以下状态：

由于，这两个状态只能各出现一次，所以不会有1的游程。

2.4m序列的伪随机性

定理2-7

证明：第二章流密码

0的游程有一个：

它产生和两个状态。于是在一个周期内，总游程数为：

2.4m序列的伪随机性

定理2-7

证明：第二章流密码

是周期为的序列，对于任一正整数

，在一个周期内为0的位的数目正好是序列和对应位相同的位的数目。设序列满足递推关系：

故

2.4m序列的伪随机性

定理2-7

证明：第二章流密码令，由递推序列可推得递推序列，满足

也是序列。为了计算，只要用在一个周期中0的个数减去1的个数，再除以，即。（定理2-7证毕）2.5m序列的破译第二章流密码上面说过，有限域上的二元加法流密码（如图2-3）是目前最为常用的流密码体制，设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是序列。又设和是序列中两个连续的长向量，其中设序列满足线性递推关系：2.5m序列的破译第二章流密码可以表示为：或，其中2.5m序列的破译第二章流密码设敌手知道一段长为的明密文对，即已知于是可求出一段长为的密钥序列其中。由此可推出线性反馈移位寄存器连续的个状态2.5m序列的破译第二章流密码做矩阵而2.5m序列的破译第二章流密码若可逆，则下面证明的确是可逆的。 因为是由作为列向量，要证可逆，只要证明这个向量线性无关。 由序列递推关系：可推出向量的递推关系：2.5m序列的破译第二章流密码设是使线性相关的最小整数，即存在不全为0的系数，其中不妨设，使得即对于任一整数有2.5m序列的破译第二章流密码由此又推出密钥流的递推关系：

即密钥流的级数小于。若，则得出密钥流的级数小于，矛盾。所以，从而矩阵必是可逆的。2.5m序列的破译第二章流密码例2-6设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程2.5m序列的破译第二章流密码例2-6即而2.5m序列的破译第二章流密码从而得到所以密钥流的递推关系补充序列的线性复杂度：使用产生该序列的最短的LFSR的长度来度量序列的线性不可预测性。记为L(s)基本性质：1.对于n长的序列，0大于等于L(s)小于等于n2.L(s)=0,当且仅当为n长0序列3.L(s)=n,当且仅当序列为0,0,0,0,,,,,14.S周期为N，L(s)小于等于N如何计算一个已知序列的线性复杂度：B-M算法2.6非线性序列第二章流密码已介绍密钥流生成器可分解为驱动子系统和非线性组合子系统，如图2-6所示，驱动子系统常用一个或多个线性反馈移位寄存器来实现，非线性组合子系统用非线性组合函数来实现，如图2-7所示，本节介绍第二部分非线性组合子系统。为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列，显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。2.6.1Geffe序列生成器第二章流密码Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用，如图2-12所示。图2-12Geffe序列生成器

图2-13多路复合器表示的Geffe序列生成器2.6.1Geffe序列生成器第二章流密码当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。若设LFSRi的输出序列为

，则输出序列可以表示为Geffe序列生成器也可以表示为图2-13的形式，其中LFSR1和LFSR3作为多路复合器的输入，LFSR2控制多路复合器的输出。设LFSRi的特征多项式分别为次本原多项式，且两两互素，则Geffe序列的周期为线性复杂度为2.6.2J-K触发器第二章流密码图2-14J-K触发器图2-15利用J-K触发器的非线性序列生成器J-K触发器如图2-14所示，它的两个输入端分别用J和K表示，其输出不仅依赖于输入，还依赖于前一个输出位，即

2.6.2J-K触发器第二章流密码其中和分别是J和K端的输入。由此可得J-K触发器的真值表，如表2-3。JK0001010111表2-3 J-K触发器的真值表2.6.2J-K触发器第二章流密码利用J-K触发器的非线性序列生成器见图2-15，令驱动序列和分别为级和级序列，则有

如果令，则输出序列的最初三项为：

当与互素且时，序列的周期为2.6.2J-K触发器第二章流密码例2-7令，两个驱动序列分别为

和

于是，输出序列是0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,其周期为。由表达式可得

2.6.2J-K触发器第二章流密码因此，如果知道中相邻位的值和，就可以推断出和中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列和。为了克服上述缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器。2.6.3Pless生成器第二章流密码Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如图2-16所示。假定在时刻输出第个单元，则输出序列为图2-16Pless生成器2.6.4钟控序列生成器第二章流密码钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图2-17所示。图2-17最简单的钟控序列生成器2.6.4钟控序列生成器第二章流密码假设LFSR1和LFSR2分别输出序列和，其周期分别为和。当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一