现在密码学第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 t 00 时状态t t +1+1 时状态反馈移位寄存器序列反馈移位寄存器的状态序列,点此查看定义6.1),(11ntttntaaafav 反馈函数f(a1,a2,an)是n元布尔函数，即n个变元a1,a2,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。v 如果f(a1,a2,an)是a1,a2,an的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift regi

3、ster）。此时f可写为f(a1,a2,an) =cna1cn-1a2c1an其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现.输出序列at满足an+t= c1an+t-1 c2an+t-2 cnat其中t为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。132第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中至少有一个不

4、为0，否则f(a1,a2,an)0，这样的话，在n个脉冲后状态必然是000，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定cn=1，若若 我们说该寄存器是我们说该寄存器是退化的，退化的，否则是否则是非退化的非退化的。 。0nc 6. 3 线性移位寄存器的表示线性移位寄存器的一元多项式表示线性移位寄存器的矩阵表示点击各项查看详细的表示方法6. 4 线性移位寄存器序列的周期性定义6.2 设 是GF(q) 上的一个无穷序列, 如果存在正整数p, 使得对任意i 0, 都有则称 为周期序列. 满足该式的最小正整数称为该序

5、列的周期, 通常记为定理6.1 设 是GF(q) 上的一个无穷序列, p是一个正整数, 如果对任意i 0, 都有 成立则 的周期一定整除p, 即定义6.3设 是一个GF(q) 上的n 阶线性移位寄存器序列. 如果 则称 为GF(q) 上的n 阶m序列.定理6.2一个GF(q) 上的n 阶线性移位寄存器序列 一定是周期序列, 并且6. 5 移位寄存器序列空间移位寄存器序列空间v 符号说明：G(f)表示以f(x)为联系多项式的n级线性移位寄存器序列构成的序列空间v 定理6.3 设f(x) 是GF(q) 上的一个常数项为1 的一元n 次多项式, 则由f(x) 所确定的线性移位寄存器的序列空间G(f)

6、 是GF(q) 上的一个n 维线性空间.v 证明：只需证明G(f)中的任意两个序列的任意线性组合也属于G(f)即可。即证： v 特例：当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).v 例1：联结多项式为 f(x)=x4+x3+x+1=(x+1)2(x2+

7、x+1)v 线性递推式：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+1v 序列和周期一般地，一个移存器序列表示为： r级线性反馈移存器的最长周期: ，能达到最长周期的线性移存器序列称为m序列。 在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即m

8、序列。.210iaaaaa12 r本原多项式本原多项式v 若n次多项式f(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。v 以本原多项式为联系多项式产生的非零序列均是m序列6. 7 m序列的伪随机性GF(2) 上的随机序列的一般特性1. 分布特性对任意的 都有2. 相关特性对任意的 有3. 游程特性对任意的i 0, k 1, 有 点击查看GF(2) 上伪随机序列的性质6. 7 m序列的伪随机性定义6.8 设 是GF(2) 上的一个周期为T 的序列。称为序列 的自相关函数。6. 7 m序列的伪随机性定理6.11 设 是GF(2) 上的一个n 阶m序列, 则 在一

9、个周期内, 0 和1 的出现次数分别为 和 在一个周期内, 游程总数为 ; 对任意的 长为i 的0 游程和1 游程都有 个; 长为 的0 游程有一个, 长为n 的1游程有一个. 的自相关函数为自相关函数反映一个周期内平均每位的相同程度自相关函数反映一个周期内平均每位的相同程度m m序列的游程分布规律序列的游程分布规律性质性质2 2：将n级m序列的一个周期段首尾相接，其游程总数为N=2n-1；其中没有长度大于n的游程；有1个长度为n的1游程，没有长度为n的0游程；没有长度为 n-1的1游程，有1个长度为n-1的0游程；有 个长度为 的1游程，有 个长度 为 的0游程。)21 (nkkkn22kn

10、22)21 (nkk习 题例、已知 是6次本原多项式，a是 生成的m序列，（1） a的周期是多少？（2） a在的一个周期内，0、1各出现多少次？（3） a在的一个周期内，游程分布如何？1)(6xxxf)(xf将LFSR的输出序列直接作为密钥序列，即将LFSR作为密钥序列产生器，可行吗？50年代开始用作密钥序列，并用于军用;60年代发现其是不安全的m m序列密码的破译序列密码的破译设m序列的LFSR的状态为则，其下一状态为其中，写成矩阵形式：其中，依据LFSR的结构，可定义iinninninacacaca1211. ? (i=1,2,)2mod1iiMSSnccccM.0.1000.010321

11、TininiiaaaS),.,(111TininiiaaaS),.,(12假设假设敌手知道一段敌手知道一段长为长为2n2n的明的明- -密文对密文对，即已知，即已知于是，于是，可求出一段长为可求出一段长为2n2n的密钥序列的密钥序列z z 其中其中nnyyyymmmm221221.,.iiiiiinymzmmzzzzz)(.221m m序列密码的破译序列密码的破译m m序列密码的破译序列密码的破译v由此，可推出线性反馈移位寄存器连续的n+1个状态：11 21 222 312 311122122nnnnnnnnnnnSz zzaaaSz zza aaSzzza aa记为记为记为构造矩阵构造矩阵根

12、据根据 可推出：可推出：若若X X可逆，则可逆，则TnnSSSY),.,(12TnnSSSX),.,(112mod1iiMSS2modMXY 2mod1YXMm m序列密码的破译序列密码的破译m m序列密码的破译序列密码的破译v对于n级LFSR，只需要知道长为2n的明-密文对(mi,yi)，就可求出矩阵M，便确定出联系多项式p(x)，从而可完全确定LFSR的结构 求出n位的密钥序列ai 12211432321321232125431432.0.1000.010.nnnnnnnnnnnnnaaaaaaaaaaaaccccaaaaaaaaaaaa122114323213212321.).().(n

13、nnnnnnnnnnaaaaaaaaaaaaccccaaaaxy例：例： 设敌手得到密文串设敌手得到密文串101101011110010101101011110010和相应的明文串和相应的明文串011001111111001011001111111001，因此可计算出相应的密钥流为，因此可计算出相应的密钥流为110100100011010010000101101011。进一步假定敌手还知道密钥序列是使用。进一步假定敌手还知道密钥序列是使用5 5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前的前1010个比特和明文串中的前个比特和明文

14、串中的前1010个比特建立如下方程个比特建立如下方程例题例题987658765476543654325432154321109876)()(aaaaaaaaaaaaaaaaaaaaaaaaacccccaaaaa点击此处返回定义6.1 如果一个GF(q) 上的n 阶反馈移位寄存器的反馈函数形如其中 则称其为线性反馈移位寄存器; 否则, 称其为非线性反馈移位寄存器.显然, 一个n 阶线性移位寄存器序列满足递推关系式点击此处返回点击此处返回设一个GF(q) 上的n 阶线性移位寄存器的反馈函数为其中，该线性移位寄存器的输出序列满足递推关系式即令D 表示线性移位寄存器序列的延迟算子, 即令则用未定元x 取代D, 我们称一元多项式为线性移位寄存器的联系多项式.v 线性递推式（一元多项式）： at+n=c1at+n-1+c2at+n-2+cnat ,t=0v 联系多项式(令ai=xn+t-i): f(x)=1+c1x+c2x2+cnxn点击此处返回实例实例（画出移存器的逻辑框图，写出相应的线性（画出移存器的逻辑框图，写出相应的线性 递推式）递推式）多项式多项式答案：答案：线性递推式： at=at-4+at-3+at-2432( )1f xxxxx1x2x3x4点击此处返回则其联系多项式