第2章 流密码100906教材

第2章流密码2.1流密码的基本概念2.2线性反馈移位寄存器2.3线性移位寄存器的一元多项式表示2.4非线性序列习题

2.1流密码的基本概念序列密码又称流密码。它是将明文消息字符串逐位地加密成密文字符。现代密码体制前面我们学习过所谓的古典密码体制，其特点是对字母(或文字)表进行操作(移位或替换)。以下我们开始学习现代密码体制。现代密码的基本出发点是将信息数字化(Digitize)，这使人们可以利用更多的数学进行研究和开展想象，并同计算机密切联系。数字化是现代科技的重要特征之一。数据信息几乎充斥人们日常生活的方方面面，并且越来越为人们所重视。比如，今天传统的金融和商业手段越来越多地被计算机所代替，甚至已经有人研究所谓“电子货币”；又如，有人说未来战争的重要武器就是a(atomic),b(biological),c(chemical),d(digital)；等等。现代密码体制序列（流）密码模型一般序列密码：同步序列密码：自同步序列密码：（常见的密文反馈模式）KGKG为计数器模式：KG为内部反馈模式：（si+1连同s0均与k无关）（s0可能与k有关！）收发方严格同步没有错误扩散具有自同步能力错误扩散有限若则称为加法序列密码。实用中可能更为简单在实用中，同步序列密码是最为常见的。该种密码一般并不要求把加密变换Eki设计得如何复杂，甚至采用更为简单的加法：即可；此时，安全性的关键在于密钥序列生成器KG的设计。其实，一个KG就是一个以前讲古典密码时提到过的伪随机密钥源。有关其安全性的基本要求我们以后再讲；为了了解它的一般构造方法，我们必须首先学习所谓的线性反馈移位寄存器。流（序列）密码2.2线性反馈移位寄存器移位寄存器是流密码产生密钥流的一个主要组成部分。一般反馈移位寄存器（FSR）一般地，一个n-FSR（n级反馈移位寄存器）的图示如下：ai+n=f(ai,ai+1,…,ai+n-1)（反馈）a

记si=(ai,ai+1,…,ai+n-1)——在第i时刻的状态，s0称为初态。反馈函数诸存储器存储器编号———级数i=0，1，2，

输出序列一般反馈移位寄存器（FSR）研讨：一个n-FSR（指给定f）可产生

个不同的序列；一个n-FSR序列必呈某种周期性，若周期性重复从第k(k=0,1,2,…)项开始，则k

。n-FSR序列

序列的初态状态变化：(先导)(ai,ai+1,…,ai+n-1)

(ai+1,ai+2,…,ai+n)(后继)一个n-FSR序列的状态走势必呈如下形状：（以每点对应的状态为初态的序列都平移等价）ai+n=f(ai,ai+1,…,ai+n-1)线性反馈移位寄存器（LFSR）当一n-FSR的反馈函数为线性齐次式，即f(ai,ai+1,…,ai+n-1)=c1ai+n-1+c2ai+n-2++cnai(cj=0,1)时，称之为n-LFSR。习惯上，人们常进行下标变换：k=i+n于是，对上述n-LFSR，其序列a满足下列递推关系式：ak=c1ak-1+c2ak-2++cnak-n(kn)其结构示意图通常（在不明确c1,c2,…,cn时）画成：a……[c1,c2,…,cn]称为结构常数。cncn-1c1ak线性反馈移位寄存器（LFSR）对于一个n-LFSR，当其结构常数[c1,c2,…,cn]明确给定时，我们往往把该n-LFSR的结构示意图画得更简洁，如以下例：例1.如果一个4-LFSR的结构常数为[1,0,1,1]，则该4-LFSR的结构示意图为若给定上述4-LFSR的初态为(0,1,1,1)，则可以列出其状态的变化过程，并求出相应的输出序列。(0111000111000111000111000…)aak线性反馈移位寄存器（LFSR）其实，仅仅给出一个n-LFSR的如例1之状态图，也就明确了该n-LFSR：例2.如果一个4-LFSR的结构示意图为则该4-LFSR的结构常数为

，递推关系为

。进一步地可求出对应初态(1,0,0,0)，(0,0,1,0)，(0,1,1,0)的(输出)序列。aak[0,1,0,1]ak=0·ak-1+1·ak-2+0·ak-3+1·ak-4=ak-2+ak-4(k4)线性反馈移位寄存器（LFSR）对一个给定的n-LFSR，其状态空间GF(2)n中所有2n个点以“先导-后继”关系弧线相连接，得到的图称为该n-LFSR的状态图。对于n-LFSR[c1,c2,…,cn]，若cn=1，则其状态图均由圈构成；而若cn=0，则其任意输出序列除前面1bit外将是(n-1)-LFSR[c1,c2,…,cn-1]的输出序列（退化情形）。以下研究总是指非退化情形。线性反馈移位寄存器（LFSR）一个n-LFSR序列的状态图要么是单点(0,0,…,0)；要么是一个不含点(0,0,…,0)的圈。对于n-LFSR，将其状态图中每一点都用对应状态的第一个分量标注，这时得到的各个圈称为序列圈。由这些序列圈可以更明显地看出n-LFSR的2n个不同序列之间的关系：两序列平移等价，当且仅当它们是同一序列圈上不同点开始围绕此圈周而复始地运转下去的结果。若视平移等价为本质相同，则n-LFSR只能产生其状态图中所含圈数个本质不同的序列。由一个n-LFSR的所有序列圈也可确定其状态图(思考)。线性反馈移位寄存器（LFSR）0,1序列a=a0a1a2

若满足：存在正整数p，使得ai=ai+p，对一切非负整数i成立则称之为周期序列，且把满足上式的最小正整数p称为周期，记为p(a)。一n-LFSR的所有输出序列均为周期序列，且周期不超过

。称达到最大周期2n-1的n-LFSR序列为(n-级)m-列。显然，若某n-LFSR产生一个m-序列，则其任何非（全）零的输出序列均是m-序列，此时称之为m-序列生成器。2.3线性移位寄存器的一元多项式表示对GF(2)上给定序列a=a0a1a2…

，称为a的形式幂级数表示，记为A(x)。GF(2)上多项式与n-LFSR[c1,c2,…,cn-1,1]一一对应，称为LFSR的特征多项式。记2n-1个非零序列的全体为G(p(x))。定义2.1给定序列{ai}，幂级数A(x)=∑aixi-1称为该序列的生成函数。

定理2.1设p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x))中任一序列{ai}的生成函数A(x)满足：

A(x)=(x)/p(x)其中(x)=∑cn-ixn-i∑ajxj-1定理2.2p(x)|q(x)的充要条件是G(p(x))G(q(x))。定义2.2设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。结论：n级LFSR输出序列的周期r不依赖于初始条件，而依赖于特征多项式p(x)。LFSR遍历2n-1个非零状态，这时序列的周期达到最大2n-1，这种序列就是m序列。问题：特征多项式满足什么条件时，LFSR的输出序列为m序列。定理2.4设p(x)是n次不可约多项式，周期为m，序列{ai}∈G(p(x))，则{ai}的周期为m。例2.4f(x)=x4+x3+x2+x+1为GF(2)上的不可约多项式，这可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)为特征多项式的LFSR的输出序列可由ak=ak-1ak-2ak-3ak-4(k≥4)和给定的初始状态求出，设初始状态为0001，则输出序列为000110001100011…，周期为5，不是m序列。定义2.3若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式。例2.5设p(x)=x4+x+1，由于p(x)|(x15-1)，但不存在小于15的常数l，使得p(x)|(xl-1)，所以p(x)的阶为15。p(x)的不可约性可由x,x+1,x2+x+1都不能整除p(x)得到，所以p(x)是本原多项式。若LFSR以p(x)为特征多项式，则输出序列的递推关系为ak=ak-1ak-4(k≥4)若初始状态为1001，则输出为100100011110101100100011110101…周期为24-1=15，即输出序列为m序列。上述定理告诉我们：(n-级)m-列的构造问题(n次)本原多项式的构造问题。关于n次本原多项式，目前有快速、可行算法：根据一个已知的n次本原多项式，找到所有其它n次本原多项式；当n较大时，检验一个n次多项式是否本原只得依赖于定义，这往往很难，好在已有前人的文献可查；n次本原多项式的数量很多：一共个，其中为Euler函数（(N)的定义为：在{1,2,…,N-1}中与N互素者的数目，(1)=1）。n-LFSR的一般理论结果流密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。

2.4m序列的伪随机性为讨论序列的随机性，我们先讨论随机序列的一般特性。

设{ai}=(a1a2a3…)为0、1序列，

形如和的一段序列分别称为a的长为k的0-游程与长为L的1-游程定义2.4：GF(2)上周期为T的序列{ai}的自相关函数定义为R(τ)=(1/T)∑(-1)ak(-1)ak+τ,0≤τ≤T-1定义中的和式表示序列{ai}与{ai+τ}（序列{ai}向后平移τ位得到）在一个周期内对应位相同的位数与对应位不同的位数之差。当τ=0时，R(τ)=1；当τ≠0时，称R(τ)为异相自相关函数。Golomb对伪随机周期序列提出了应满足的如下3个随机性公设：①在序列的一个周期内，0与1的个数相差至多为1。②在序列的一个周期内，长为i的游程占游程总数的1/2i(i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等。③异相自相关函数是一个常数。公设①说明{ai}中0与1出现的概率基本上相同;②说明0与1在序列中每一位置上出现的概率相同;③意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息。从密码系统的角度看，一个伪随机序列还应满足下面的条件：①{ai}的周期相当大。②{ai}的确定在计算上是容易的。③由密文及相应的明文的部分信息，不能确定整个{ai}。定理2.7GF(2)上的n长m序列{ai}具有如下性质：①在一个周期内，0、1出现的次数分别为2n-1-1和2n-1。②在一个周期内，总游程数为2n-1；对1≤i≤n-2，长为i的游程有2n-i-1个，且0、1游程各半；长为n-1的0游程一个，长为n的1游程一个。③{ai}的自相关函数为密钥序列生成器(KG)基本要求<序列密码>在序列密码的设计中，人们往往将加密变换简单地取为加法(即人们经常使用的是加法序列密码)，这时保密性的关键在于KG的设计。对于KG，虽然种子密钥k较短、其相应的存储器长度也受限，但人们总是设法将它设计成：在现有的计算资源和能力下，难以破解所产生的密钥序列；或者也可以说，按现有的计算资源和能力估算，破解所产生的密钥序列的代价远远超过由此而能获取的利益。为了这样的目的，人们就目前的想象和预见，提出以下基本要求：密钥序列生成器(KG)基本要求种子密钥k的变化量足够大，一般应在264以上；KG产生的密钥序列k具极大周期，一般不小于255；k具有均匀的n-元分布，即在一个周期环上，某特定形式的n-长bit串与其求反，两者出现的频数大抵相当；(例如，均匀的游程分布)k不可由一个低级（比如，小于106级）的LFSR产生，也不可与一个低级LFSR产生的序列只有比率很小的相异项；利用统计方法由k提取关于KG结构或K的信息在计算上不可行；混乱性.即k的每一bit均与k的大多数bit有关；扩散性.即k任一bit的改变要引起k在全貌上的变化。KG的一般结构通常，人们总是把KG设计得具有一定的结构特点，从而稍加分析和论证其强度，以增加使用者的置信度。如此，积习而成以下模式：驱动子系统f（可线性）非线性组合子系统F种子密钥k…

…k=k0k1k2

f——

一般由LFSR或NLFSR等序列生成器构成，提供若干周期大、统计特性好的序列(称为驱动序列)。F——

对多条驱动序列，综合运用下面介绍的基本编码手段，有效地破坏和掩盖其中存在的规律或关系。KG结构分解示意图

例2.6设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程即而从而得到所以密钥流的递推关系为在前面已介绍密钥流生成器可分解为驱动子系统和非线性组合子系统，非线性序列驱动子系统常用一个或多个线性反馈移位寄存器来实现，

非线性组合子系统用非线性组合函数F来实现。

本节介绍第2部分非线性组合子系统。

J-K触发器如图2.14所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即其中x1和x2分别是J和K端的输入。由此可得J-K触发器的真值表，如表2.3。（见26页表2.3）2.6.1J-K触发器图2.14J-K触发器图2.15利用J-K触发器的非线性序列生成器在图2.15中，令驱动序列{ak}和{bk}分别为m级和n级m序列，则有如果令c-1=0，则输出序列的最初3项为当m与n互素且a0+b0=1时，序列{ck}的周期为(2m-1)(2n-1)。例2.7令m=2,n=3，两个驱动m序列分别为{ak}=0,1,1,…和{bk}=1,0,0,1,0,1,1,…于是，输出序列{ck}是0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,