第7讲BM算法ppt课件.pptVIP

B-M 算 法 量子密码研究室 王 滨 2005年4月6日 上节内容复习 移位寄存器序列的三种表示方法： 线性递推式（一元多项式）： at+n=c1at+n-1+c2at+n-2+…+cnat ,t=0 联结多项式： f(x)=1+c1x+c2x2+…+cnxn 状态转移矩阵： 满足：st+1=stTf 称st=(at,at+1,at+2,…,at+n-1)为n维状态 几个概念 非退化的移位寄存器 (不)可约多项式 极小多项式 序列和周期 本原多项式 m序列 1游程、0游程 m序列的游程分布规律 解：产生 a…的联结  多项式 设其联结多项式f(x)=1+c1x+c2x2+c3x3+x4 线性递推式at=at-4+c3at-3+c2at-2+c1at-1 0+c3+c2+c1=1 1+c3+c2+c1=0 1+c3+c2+0=0 1+c3+0+0=0 解得：c3=1；c2=0；c1=0 故其联结多项式为1+x3+x4 * * 线性移存器 （一）解方程法 已知序列a是由n级线性移存器产生的，且知a的连续2n位，可用解线性方程组的方法得到线性递推式。 例：设a4级线性移存器产生的序列的8个连续信号，求该移存器的线性递推式。 （二）、B-M迭代算法 根据密码学的需要，对线性反馈移位寄存器(LFSR)主要考虑下面两个问题： （1）如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列，即固定级数时，什么样的移存器序列周期最长。这是从密钥生成角度考虑，用最小的代价产生尽可能好的、参与密码变换的序列。 （2）当已知一个长为N序列a时，如何构造一个级数尽可能小的LFSR来产生它。这是从密码分析角度来考虑，要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过B-M算法来解决。 1、概念简介 设 是 上的长度为N的序列，而 是 上的多项式，c0=1. 如果f(x)是一个能产生a并且级数最小的线性移位寄存器的反馈多项式，l是该移存器的级数，则称 为序列a的线性综合解。 如果序列中的元素满足递推关系： 则称 产生二元序列a。其中 表示以f(x)为反馈多项式的l级线性移位寄存器。 线性移位寄存器的综合问题可表述为：给定一个N长二元序列a，如何求出产生这一序列的最小级数的线性移位寄存器，即最短的线性移存器？ 几点说明： 2、规定：0级线性移位寄存器是以f(x)=1为反馈多项式的线性移位寄存器，且n长(n=1, 2, …, N)全零序列，仅由0级线性移位寄存器产生。事实上，以f(x)=1为反馈多项式的递归关系式是：ak=0，k=0, 1, …, n-1.因此，这一规定是合理的。 1、反馈多项式f(x)的次数?l。因为产生a且级数最小的线性移位寄存器可能是退化的，在这种情况下 f(x)的次数l；并且此时 f(x)中的cl=0，因此在反馈多项式f(x)中c0=1，但不要求cl=1。 3、给定一个N长二元序列a，求能产生a并且级数最小的线性移位寄存器，就是求a的线性综合解。利用B-M算法可以有效的求出。 2、B-M算法要点 用归纳法求出一系列线性移位寄存器： 每一个 都是产生序列a的前n项的最短线性移位寄存器，在 的基础上构造相应的 ，使得 是产生给定序列前n+1项的最短移存器，则最后得到的 就是产生给定N长二元序列a的最短的线性移位寄存器。 3、B-M算法 1、取初始值： 2、设 均已求得，且 任意给定一个N长序列 ，按n归纳定义 记： 再计算： 称dn为第n步差值。然后分两种情形讨论： （ⅰ） 若=0，则令： 。 （ⅱ） 若=1，则需区分以下两种情形： 当：时， 取：。 当有m（），使：。 便置：