第13讲序列密码与移位寄存器

第6章序列密码与移位寄存器主要内容序列密码的基本原理移位寄存器与移位寄存器序列线性移位寄存器的表示线性移位寄存器序列的周期性线性移位寄存器的序列空间线性移位寄存器序列的极小多项式m序列的伪随机性B-M算法与序列的线性复杂度线性移位寄存器的非线性组合6.1序列密码的基本原理设明文、密钥、密文都是一个(0,1)序列，他们分别为则加密变换为解密变换为点击查看序列密码体制的模型6.2移位寄存器与移位寄存器序列一个q元域GF(q)上的n阶反馈移位寄存器由n个寄存器和一个反馈函数构成,如图所示.反馈移位寄存器的工作原理：当一个时钟脉冲来临时,第i级寄存器的内容传送给第i-1级寄存器,i=2,3,···,n.第1级寄存器的内容为反馈移位寄存器的输出.反馈函数f的值传送给第n级寄存器.t≥0时状态t+1时状态反馈移位寄存器序列反馈移位寄存器的状态序列,点此查看定义6.1),,,(11ntttntaaafa反馈函数f(a1,a2,…,an)是n元布尔函数，即n个变元a1,a2,…,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。如果f(a1,a2,…,an)是a1,a2,…,an的线性函数，则称之为线性反馈移位寄存器LFSR（linearfeedbackshiftregister）。此时f可写为f(a1,a2,…,an)=cna1+cn-1a2+…c1an其中常数ci=0或1，+是模2加法。ci=0或1可用开关的断开和闭合来实现.输出序列{at}满足an+t=c1an+t-1+c2an+t-2+…+cnat其中t为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。132第7时刻001第0时刻001第1时刻100第2时刻110第3时刻111第4时刻011第5时刻101第6时刻010产生序列为：1001110……在线性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定cn=1，若我们说该寄存器是退化的，否则是非退化的。。0nc6.3线性移位寄存器的表示线性移位寄存器的一元多项式表示线性移位寄存器的矩阵表示点击各项查看详细的表示方法6.4线性移位寄存器序列的周期性定义6.2设是GF(q)上的一个无穷序列,如果存在正整数p,使得对任意i≥0,都有则称为周期序列.满足该式的最小正整数称为该序列的周期,通常记为定理6.1设是GF(q)上的一个无穷序列,p是一个正整数,如果对任意i≥0,都有成立则的周期一定整除p,即定义6.3设是一个GF(q)上的n阶线性移位寄存器序列.如果则称为GF(q)上的n阶m序列.定理6.2一个GF(q)上的n阶线性移位寄存器序列一定是周期序列,并且6.5移位寄存器序列空间符号说明：G(f)表示以f(x)为联系多项式的n级线性移位寄存器序列构成的序列空间定理6.3设f(x)是GF(q)上的一个常数项为1的一元n次多项式,则由f(x)所确定的线性移位寄存器的序列空间G(f)是GF(q)上的一个n维线性空间.证明：只需证明G(f)中的任意两个序列的任意线性组合也属于G(f)即可。即证：特例：当q=2时，G(f)中任意两个序列之和仍然属于G(f)。)(,),(),(),(qGFfGbafGbfGa定理6.4设f(x)和h(x)是GF(q)上的两个常数项为1的一元多项式.如果f(x)|h(x),即f(x)整除h(x),则由f(x)所确定的线性移位寄存器的序列空间G(f)是由h(x)所确定的线性移位寄存器的序列空间G(h)的子空间,即G(f)⊆G(h).例1：联结多项式为f(x)=x4+x3+x+1=(x+1)2(x2+x+1)线性递推式：at=at-4+at-3+at-16.6线性移位寄存器序列极小多项式定义：对于一个移位寄存器序列a，称其联系多项式中次数最低的多项式为a的极小多项式。定义：满足f(x)|1-xr的最小正整数r为f(x)的周期，记为p(f(x))，简记为p(f)。例子：x4+x3+x2+x+1的周期为5(x4+x3+x2+x+1)(x+1)=x5+1序列和周期一般地，一个移存器序列表示为：•r级线性反馈移存器的最长周期:，能达到最长周期的线性移存器序列称为m序列。•在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即m序列。......210iaaaaa12r本原多项式若n次多项式f(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。以本原多项式为联系多项式产生的非零序列均是m序列6.7m序列的伪随机性GF(2)上的随机序列的一般特性1.分布特性对任意的都有2.相关特性对任意的有3.游程特性对任意的i≥0,k≥1,有点击查看GF(2)上伪随机序列的性质6.7m序列的伪随机性定义6.8设是GF(2)上的一个周期为T的序列。称为序列的自相关函数。6.7m序列的伪随机性定理6.11设是GF(2)上的一个n阶m序列,则①在一个周期内,0和1的出现次数分别为和②在一个周期内,游程总数为;对任意的长为i的0游程和1游程都有个;长为的0游程有一个,长为n的1游程有一个.③的自相关函数为自相关函数反映一个周期内平均每位的相同程度m序列的游程分布规律性质2：将n级m序列的一个周期段首尾相接，其游程总数为N=2n-1；其中没有长度大于n的游程；有1个长度为n的1游程，没有长度为n的0游程；没有长度为n-1的1游程，有1个长度为n-1的0游程；有个长度为的1游程，有个长度为的0游程。)21(nkkkn22kn22)21(nkk习题例、已知是6次本原多项式，a是生成的m序列，（1）a的周期是多少？（2）a在的一个周期内，0、1各出现多少次？（3）a在的一个周期内，游程分布如何？1)(6xxxf)(xf将LFSR的输出序列直接作为密钥序列，即将LFSR作为密钥序列产生器，可行吗？50年代开始用作密钥序列，并用于军用;60年代发现其是不安全的m序列密码的破译设m序列的LFSR的状态为则，其下一状态为其中，写成矩阵形式：其中，依据LFSR的结构，可定义iinninninacacaca1211......(i=1,2,…)2mod1iiMSSnccccM......0...1000...010321TininiiaaaS),,...,(111TininiiaaaS),,...,(12假设敌手知道一段长为2n的明-密文对，即已知于是，可求出一段长为2n的密钥序列z其中nnyyyymmmm221221......,......iiiiiinymzmmzzzzz)(......221m序列密码的破译m序列密码的破译由此，可推出线性反馈移位寄存器连续的n+1个状态：1121222312311122122nnnnnnnnnnnSzzzaaaSzzzaaaSzzzaaa记为记为记为构造矩阵根据可推出：若X可逆，则TnnSSSY),,...,(12TnnSSSX),,...,(112mod1iiMSS2modMXY2mod1YXMm序列密码的破译m序列密码的破译对于n级LFSR，只需要知道长为2n的明-密文对(mi,yi)，就可求出矩阵M，便确定出联系多项式p(x)，从而可完全确定LFSR的结构①求出n位的密钥序列ai②12211432321321232125431432..................0...1000...010............nnnnnnnnnnnnnaaaaaaaaaaaaccccaaaaaaaaaaaa122114323213212321............)...()...(nnnnnnnnnnnaaaaaaaaaaaaccccaaaaxy例：设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥序列是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程例题987658765476543654325432154321109876)()(aaaaaaaaaaaaaaaaaaaaaaaaacccccaaaaa点击此处返回定义6.1如果一个GF(q)上的n阶反馈移位寄存器的反馈函数形如其中则称其为线性反馈移位寄存器;否则,称其为非线性反馈移位寄存器.显然,一个n阶线性移位寄存器序列满足递推关系式点击此处返回点击此处返回设一个GF(q)上的n阶线性移位寄存器的反馈函数为其中，该线性移位寄存器的输出序列满足递推关系式即令D表示线性移位寄存器序列的延迟算子,即令则用未定元x取代D,我们称一元多项式为线性移位寄存器的联系多项式.线性递推式（一元多项式）：at+n=c1at+n-1+c2at+n-2+…+cnat,t=0联系多项式(令ai=xn+t-i):f(x)=1+c1x+c2x2+…+cnxn点击此处返回实例（画出移存器的逻辑框图，写出相应的线性递推式）多项式答案：线性递推式：at=at-4+at-3+at-2432()1fxxxxx1x2x3x4点击此处返回则其联系多项式为？5a4a2a1a输出序列3a点击此处返回设一个GF(q)上的n阶线性移位寄存器的反馈函数为其中，该线性移位寄存器在时刻t时的状态为令因为该线性移位寄存器在时刻t+1时的状态其中所以我们有我们称为线性移位寄存器的构造矩阵。点击此处返回在序列的一个周期内,0与1的个数相差至多为1序列的异相自相关函数是一个常数在序列的一个周期内,长为i的游程数占游程总数的另外,在等长的游程中,0游程的个数与1游程的个数相等