现在密码学第13讲 序列密码与移位寄存器.ppt

第6章 序列密码与移位寄存器 主要内容 6. 1 序列密码的基本原理 6. 2 移位寄存器与移位寄存器序列 反馈函数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) =cna1cn-1a2…c1an 其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现. 输出序列{at}满足 an+t= c1an+t-1 c2an+t-2 … cnat 其中t为非负正整数。 线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。 在线性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。 若只有一个系数不为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 维线性空间. 证明：只需证明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 线性移位寄存器序列极小多项式 序列和周期 一般地，一个移存器序列表示为： r级线性反馈移存器的最长周期: ，能达到最长周期的线性移存器序列称为m序列。 在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即m序列。 本原多项式 若n次多项式f(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。 以本原多项式为联系多项式产生的非零序列均是m序列 6. 7 m序列的伪随机性 6. 7 m序列的伪随机性 6. 7 m序列的伪随机性 m序列的游程分布规律 将LFSR的输出序列直接作为密钥序列，即将LFSR作为密钥序列产生器，可行吗？ 50年代开始用作密钥序列，并用于军用; 60年代发现其是不安全的 m序列密码的破译 设m序列的LFSR的状态为 则，其下一状态为 其中， 写成矩阵形式： 其中，依据LFSR的结构，可定义 假设敌手知道一段长为2n的明-密文对，即已知 m序列密码的破译 由此，可推出线性反馈移位寄存器连续的n+1个状态： 构造矩阵 根据 可推出： 若X可逆，则 m序列密码的破译 对于n级LFSR，只需要知道长为2n的明-密文对(mi,yi)，就可求出矩阵M，便确定出联系多项式p(x)，从而可完全确定LFSR的结构 求出n位的密钥序列ai 例： 设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥序列是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程 线性递推式（一元多项式）： at+n=c1at+n-1+c2at+n-2+…+cnat ,t=0 联系多项式(令ai=xn+t-i): f(x)=1+c1x+c2x2+…+cnxn 点击此处返回 定义6.1 如果