第7讲 序列密码体制

应用密码学张仕斌万武南张金全孙宣东编著西安电子科技大学出版社二00九年十二月2023/2/51第4章序列密码体制2023/2/52知识点：

序列密码的概念

线性反馈移位寄存器

序列和周期

非线性序列简介

常用序列密码2023/2/53起源-一次一密无条件安全：在理论上是不可破译的但：要求密钥与明文具有相同长度、且不可重复使用，增加了密钥分配与管理的困难对策：用一个较小的密钥来伪随机地生成密钥流。①人们试图以序列密码方式仿效“一次一密”密码②序列密码的理论已经比较成熟，而且具有工程实现容易、效率高等特点③采用一个短的种子密钥来控制某种算法产生出长的密钥序列，供加、解密使用，而短的种子密钥的存储、分配都较容易2023/2/54分组密码使用的是一个不随时间变化的固定变换，具有扩散性好、插入敏感等优点；其缺点是：加密处理速度慢。序列密码vs.分组密码分组密码以一定大小的分组作为每次处理的基本单元，而序列密码则以一个元素（如一个字母或一个比特）作为基本的处理单元。序列密码使用一个随时间变化的加密变换，具有转换速度快、低错误传播的优点，硬件实现电路更简单；其缺点是：低扩散（意味着混乱不够）、插入及修改的不敏感性。2023/2/554.1序列密码的概念序列密码算法将明文逐位转换成密文，如下图所示。密钥流发生器（也称为滚动密钥发生器）输出一系列比特流：K1，K2，K3，……Ki

。密钥流（也称为滚动密钥）跟明文比特流（m1，m2，m3，……mi

）

，进行异或运算产生密文比特流。

加密：

Ci=mi⊕Ki

在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。

解密：mi=Ci⊕Ki显然，mi⊕Ki⊕Ki=mi2023/2/56事实上，序列密码算法其安全性依赖于简单的异或运算和密钥序列。密钥流发生器生成的看似随机的密钥流实际上是确定的，在解密的时候能很好的将其再现。密钥流发生器输出的密钥越接近随机，对密码分析者来说就越困难。

如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，破译该算法就容易了。

假的Alice得到一份密文和相应的明文，她就可以将两者异或恢复出密钥流。或者，如果她有两个用同一个密钥流加密的密文，她就可以让两者异或得到两个明文互相异或而成的消息。这是很容易破译的，接着她就可以用明文跟密文异或得出密钥流。现在，无论她再拦截到什么密文消息，她都可以用她所拥有的密钥流进行解密。另外，她还可以解密，并阅读以前截获到的消息。一旦Alice得到一明文/密文对，她就可以读懂任何东西了。2023/2/57这就是为什么所有序列密码需要随机密钥的原因。密钥流发生器的输出是密钥的函数。

这样，Alice有一个明文/密文对，但她只能读到用特定密钥加密的消息。

更换密钥，攻击者就不得不重新分析。

流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如0,1数字)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。

核心问题是密钥流生成器的设计。保持收发两端密钥流的精确同步是实现可靠解密的关键技术。2023/2/58-序列密码的分类:1.自同步序列密码

自同步序列密码就是密钥流的每一位是前面固定数量密文位的函数，下图和下页图描述了其工作原理。其中，内部状态是前面n比特密文的函数。该算法的密码复杂性在于输出函数，它收到内部状态后生成密钥序列位。2023/2/59自同步流密码SSSC(Self-SynchronousStreamCipher)

内部状态i依赖于(kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且ki对i的关系还与以前的输入m1,m2,…,mi-1有关。一般在有限的n级存储下将与mi-1,…,mi-n有关。2023/2/510自同步序列密码的特点自同步

自同步的实现依赖于密文被删除或插入，因为解密只取决于先前固定数量的密文字符。自同步序列密码在同步丢失后能够自动重新建立正确的解密，只有固定数量的明文字符不能被恢复。有限的错误传播因为自同步序列密码的状态取决于n个已有的密文字符，如果一个密文字符在传输过程中被修改，则解密时最多影响到后续n个字符的解密恢复，会发生有限的错误传播。-（由于具有自同步能力，)强化了其抗统计分析的能力2023/2/5112．同步序列密码

同步流密码SSC(SynchronousStreamCipher)：

内部状态i与明文消息无关，密钥流将独立于明文。因此，对于明文而言，这类加密变换是无记忆的，但它是时变的；只有保持两端精确同步才能正常工作；无差错传播(ErrorPropagation)。2023/2/512同步序列密码的特点-在保密通信过程中，通信的双方必须保持精确的同步

对于同步序列密码，只要通信双方的密钥序列产生器具有相同的种子密钥和相同的初始状态，就能产生相同的密钥序列。-对失步的敏感性

-收方的解密将一直错误，直到重新同步为止

-容易检测插入、删除、重播等主动攻击无错误传播当通信中某些密文字符产生了错误（如0变成1，或1变成0），只影响相应字符的解密，不影响其它字符。

对主动攻击时异常敏感而有利于检测。

2023/2/513-序列密码-密钥流序列应具备的性质密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：

-极大的周期；

-良好的统计特性；

-抗线性分析；

-抗统计分析。实际上,序列密码不可能做到“一次一密”但若密钥流生成器生成的密钥周期足够长，且随机性好，其安全强度可以得到保证！因此，序列密码的设计核心在于密钥流生成器的设计，序列密码的安全强度取决于密钥流生成器生成的密钥周期、复杂度、随机（伪随机）特性等。2023/2/514常见的密钥序列产生器目前，最为流行和实用的密钥流产生器大多基于线性反馈移位寄存器。如下图所示，其驱动部分是一个或多个线性反馈移位寄存器。LFSR………FLFSR1LFSR2LFSRn……FFF2023/2/515预备知识：布尔函数一般地，我们把n元布尔函数定义为如下映射：记为，其中

布尔函数是研究数字逻辑电路的重要数学工具，在序列密码、分组密码和公钥密码中，布尔函数都有重要的应用。特别在序列密码中，布尔函数是重要的数学工具之一。2023/2/5161、真值表

小项表示实际上是布尔代数表达方式，即逻辑表达方式，此方法常用于布尔函数的设计实现。2、小项表示上例的小项表示为3、多项式表示因为，将小项表示中的逻辑非的形式换掉即得多项式表示。2023/2/5174.2线性反馈移位寄存器

-定义：反馈移存器的反馈逻辑电路可用一布尔函数f(a1,a2,…,an)来表示，若对应的布尔函数是线性函数，则称该反馈移存器为线性反馈移存器LFSR(linearfeedbackshiftregister)，否则称为非线性反馈移存器。ajaj-2aj-3aj-1图1线性反馈移位寄存器ajaj-2aj-3图2非线性反馈移位寄存器2023/2/518此时LFSR函数可写为：f(a1,a2,…,an)=cna1

cn-1a2…c1an上图中，常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，这样的线性函数共有2n个。输出序列{at}满足：a1+t=cnat+1cn-1at+2…c1an+t

其中，t为非负正整数。如下图所示，是一个LFSR:（1）线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一，也非常适合用硬件实现；（2）可以产生大周期序列；（3）可以产生具有良好统计性质的序列；（4）易于利用代数方法对其进行分析。n级线性移存器的线性递推式表示-优势：2023/2/519-工作原理(如下图)假设在j时刻其内部状态为：在j+1时刻其内部状态变为：其中：此时的输出为j时刻的最高级：n级反馈移位寄存器

每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成，如右图所示。2023/2/520ajaj-2aj-1第7时刻001第0时刻001第1时刻100第2时刻110第3时刻111第4时刻011第5时刻101第6时刻010产生序列为：10011101……比如：2023/2/521每一时刻的状态可用n长序列“a1,a2,…,an

”n维向量“(a1,a2,…,an)”来表示，其中ai是第i级存储器的内容。初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并计算f(a1,a2,…,an)作为下一时刻的an。反馈函数f(a1,a2,…,an)是n元布尔函数，即n个变元a1,a2,…,an

可以独立地取0和1两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。-表示方法1、线性递推式表示一个r级线性移存器的线性递推式表示为：2023/2/522an-1an-2an-3an-4an2、反馈多项式表示一个r级线性移存器的反馈多项式表示为：x1x2x3x4通常，用来表示一个LFSR。2023/2/523例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由下表求出。即输出序列为101110111011…，周期为4。2023/2/524-具体来说：在初始状态下,即0时刻在第一个时钟到来时101f(a1,a2,a3)=a1a2⊕a3第1级第2级第3级S0=(1,0,1)输出10f(a1,a2,a3)=a1a2⊕a3第1级第2级第3级S1=(0,1,1)a1=1,a2=0,a3=11输出1a02023/2/525则其输出序列和状态序列如下:

状态序列:(1,0,1)(0,1,1)(1,1,1)(1,1,0)(1,0,1)(0,1,1)….

输出序列:101110….

由上面的结果可以看出，这个反馈移位寄存器的状态序列和输出序列都是周期序列，其周期为4。在第二个时钟到来时11f(a1,a2,a3)=a1a2⊕a3第1级第2级第3级S2=(1,1,1)a1=1,a2=1,a3=01输出0a02023/2/5262023/2/527例：一个5级线性反馈移位寄存器例设一个GF(2)上的4阶线性反馈移位寄存器如下图所示，其反馈函数为f(x1，x2，x3，x4)＝x1⊕x2，初始状态为S0＝（1，0，1，1）容易验证该线性反馈移位寄存器的输出序列为：

101111000100110101111000100110……

这个线性移位寄存器序列是一个周期序列，周期为15。x4x3x2x1＋输出序列2023/2/528（1）在线性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。

注：（2）若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定cn=1。（3）n级线性反馈移位寄存器的状态周期小于等于2n-1。输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1。

2023/2/5294.3序列和周期一般地，一个移存器序列表示为：

对于序列，若存在整数p使得对任意正整数k有成立，称满足该式的最小正整数p为序列的周期。

即：n级线性反馈移存器的最长周期:，能达到最长周期的线性移存器序列称为m序列。-在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即m序列。定义1：n级线性反馈移位寄存器产生的序列{ai}的周期达到最大值2n-1时，称{ai}为n级m序列。2023/2/530（1）如何利用级数尽可能小的线性移位寄存器产生周期长、统计性能好的序列；（2）已知一个序列{ai}，如何构造一个尽可能短的线性移位寄存器来产生它。-m序列的随机性：序列密码的安全性取决于密钥流的安全性，要求密钥流序列有良好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。2023/2/5311.

Golomb随机性假设

为了度量周期序列的随机性，Golomb提出了下列三条标准：凡满足这三条随机性假设的序列，被Golomb称为伪随机序列或者伪噪声序列。（1）一个周期中0、1的个数相差不超过1个；（2）一个周期段中，长度为k的游程占游程总数的（这里假定至少有两个长为k的游程）；（3）周期自相关函数是二值函数。2、m序列统计特性性质1

：r级m序列的一个周期中，1出现个,0出现个。1）m序列的“0、1”信号的频次规律2）m序列的游程分布规律2023/2/532

若干个信号连续出现的现象称游程。对于序列a，称a中形如01…10或10…01的段为一个1游程或0游程，游程中所含1或0的个数称为该游程的长度，如0110为一个长为2的1游程，101为一个长为1的0游程。性质2：将r级m序列的一个周期段首尾相接，其游程总数为N=2r-1；其中没有长度大于r的游程；有1个长度为r的1游程，没有长度为r的0游程；没有长度为r-1的1游程，有1个长度为r-1的0游程；有个长度为的1游程，有个长度为

的0游程。再如00110111，其前两个数字是00，称长为2的0游程；接着是11，是长为2的1游程；再下来是长为1的0游程和长为3的0游程。选讲2023/2/533

3）

m序列的自相关特性

若是一个周期为p的0、1序列，定义{0,1}上的映射为：，定义序列的自相关函数为:性质3：若是一个r级m序列，那么

Golomb随机性假设只是随机性的必要条件，一随机序列应该满足Golomb随机性假设。但满足上述标准的周期序列并不一定能满足我们对密钥流序列在安全性上的要求，这种安全性是寓于随机性之中的。选讲2023/2/534例如：m序列完全满足Golomb随机性假设，但m序列是高度可预测的。-线性移位寄存器的输出序列因为n级线性移位寄存器的输出序列{ai}满足递推关系:

an+k=c1an+k-1c2an+k-2…cnak，对任何k≥1成立。这种递推关系可用一个一元高次多项式

p(x)=1+c1x+…＋cn-1xn-1＋cnxn

表示，称这个多项式为LFSR的特征多项式。由于ai∈GF(2)(i=1,2,…,n)，所以共有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个，记2n-1个非零序列的全体为G(p(x))。定义2：给定序列{ai}，幂级数，称为该序列的生成函数。2023/2/535

定义3：设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。（选讲）

定理2：若序列{ai}的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则{ai}的周期r|p。（选讲）n级LFSR输出序列的周期r不依赖于初始条件，而依赖于特征多项式p(x)。实际上，我们感兴趣的是LFSR遍历2n-1个非零状态，这时序列的周期达到最大2n-1，这种序列就是m序列。特征多项式满足什么条件时，LFSR的输出序列为m序列。

定义4：仅能被非零常数或者本身的常数倍除尽，不能被其他多项式整除的多项式称为不可约多项式。定理3：n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约多项式。2023/2/536但该定理的逆命题不成立，即LFSR产生的特征多项式为不可约多项式，但其输出序列不一定是m序列。例3：设f(x)=x4+x3+x2+x+1是GF(2)上的不可约多项式，但是它的输出序列是000110001100011…，周期是5，不是m序列。解：f(x)的不可约性由多项式x，x+1，x2+x+1不能整除f(x)而得。对于k≥5，输出序列用ak=ak-1ak-2ak-3ak－4

检验即可。定义5：若n次不可约多项式p(x)的阶为2n-1，称其为n次本原多项式。（选讲）定理4：{ai}为n级m序列的充要条件是其特征多项式p(x)为