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

1、第6章 序列密码与移位寄存器,主要内容,序列密码的基本原理,移位寄存器与移位寄存器序列,线性移位寄存器的表示,线性移位寄存器序列的周期性,线性移位寄存器的序列空间,线性移位寄存器序列的极小多项式,m 序列的伪随机性,B-M 算法与序列的线性复杂度,线性移位寄存器的非线性组合,6. 1 序列密码的基本原理,设明文、密钥、密文都是一个(0, 1)序列，他们分别为,则加密变换为,解密变换为,6. 2 移位寄存器与移位寄存器序列,一个q 元域GF(q) 上的n 阶反馈移位寄存器由n 个寄存器和一个反馈函数构成, 如图所示.,反馈移位寄存器的工作原理： 当一个时钟脉冲来临时, 第i级寄存器的内容传送给第

2、i-1 级寄存器, i = 2, 3, , n.第1 级寄存器的内容为反馈移位寄存器的输出. 反馈函数f的值传送给第n 级寄存器.,t 0 时状态,t +1 时状态,反馈移位寄存器序列,反馈移位寄存器的状态序列,反馈函数f(a1,a2,an)是n元布尔函数，即n个变元a1,a2,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。 如果f(a1,a2,an)是a1,a2,an的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register）。此时f可写为 f(a1,a2,an) =cna1cn-1

3、a2c1an 其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现.,输出序列at满足 an+t= c1an+t-1 c2an+t-2 cnat 其中t为非负正整数。 线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。,第7时刻 0 0 1,第0时刻 0 0 1,第1时刻 1 0 0,第2时刻 1 1 0,第3时刻 1 1 1,第4时刻 0 1 1,第5时刻 1 0 1,第6时刻 0 1 0,产生序列为：1001110,在线性反馈移位寄存器中总是假定c1,c2,cn中至少有一个不为0，否则f(a1,a2,an)0，这样的

4、话，在n个脉冲后状态必然是000，且这个状态必将一直持续下去。 若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。 一般对于n级线性反馈移位寄存器，总是假定cn=1，若 我们说该寄存器是退化的，否则是非退化的。 。,6. 3 线性移位寄存器的表示,6. 4 线性移位寄存器序列的周期性,6. 5 移位寄存器序列空间,符号说明：G(f)表示以f(x)为联系多项式的n级线性移位寄存器序列构成的序列空间 定理6.3 设f(x) 是GF(q) 上的一个常数项为1 的一元n 次多项式, 则由f(x) 所确定的线性移位寄存器的序列空间G(f) 是GF(q) 上的一个n 维线性空间. 证明：只需证

5、明G(f)中的任意两个序列的任意线性组合也属于G(f)即可。即证： 特例：当q=2时，G(f)中任意两个序列之和仍然属于G(f)。,定理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-1,6. 6 线性移位寄存器序列极小多项式,定义：对于一

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序列。,本原多项式,若n次多项式f(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的

7、本原多项式。 以本原多项式为联系多项式产生的非零序列均是m序列,6. 7 m序列的伪随机性,GF(2) 上的随机序列的一般特性,1. 分布特性 对任意的 都有,2. 相关特性 对任意的 有,3. 游程特性 对任意的i 0, k 1, 有,6. 7 m序列的伪随机性,定义6.8 设 是GF(2) 上的一个周期为T 的序列。,称为序列 的自相关函数。,6. 7 m序列的伪随机性,定理6.11 设 是GF(2) 上的一个n 阶m序列, 则 在一个周期内, 0 和1 的出现次数分别为 和 在一个周期内, 游程总数为 ; 对任意的 长为i 的0 游程和1 游程都有 个; 长为 的0 游程有一个, 长为n

8、 的1游程有一个. 的自相关函数为,自相关函数反映一个周期内平均每位的相同程度,m序列的游程分布规律,性质2：将n级m序列的一个周期段首尾相接，其游程总数为N=2n-1；其中没有长度大于n的游程；有1个长度为n的1游程，没有长度为n的0游程；没有长度为 n-1的1游程，有1个长度为n-1的0游程；有 个长度为 的1游程，有 个长度 为 的0游程。,习 题,例、已知 是6次本原多项式，a是 生成的m序列， （1） a的周期是多少？ （2） a在的一个周期内，0、1各出现多少次？ （3） a在的一个周期内，游程分布如何？,将LFSR的输出序列直接作为密钥序列，即将LFSR作为密钥序列产生器，可行吗

9、？ 50年代开始用作密钥序列，并用于军用; 60年代发现其是不安全的,m序列密码的破译,设m序列的LFSR的状态为 则，其下一状态为 其中， 写成矩阵形式： 其中，依据LFSR的结构，可定义,(i=1,2,),假设敌手知道一段长为2n的明-密文对，即已知,于是，可求出一段长为2n的密钥序列z 其中,m序列密码的破译,m序列密码的破译,由此，可推出线性反馈移位寄存器连续的n+1个状态：,构造矩阵 根据 可推出： 若X可逆，则,m序列密码的破译,m序列密码的破译,对于n级LFSR，只需要知道长为2n的明-密文对(mi,yi)，就可求出矩阵M，便确定出联系多项式p(x)，从而可完全确定LFSR的结构

10、 求出n位的密钥序列ai,x,y,例： 设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥序列是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程,例题,Thank You !,定义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,实例（画出移存器的逻辑框图，写出相应的