文档介绍：B-M 算法 1 2上节内容复****移位寄存器序列的三种表示方法: ?线性递推式(一元多项式) : a t+n =c 1a t+n-1 +c 2a t+n-2 +…+c na t ,t>=0 ?联结多项式: f(x)=1+c 1 x+c 2x 2+…+c nx n ?状态转移矩阵: 满足: s t+1 =s tT f称s t =(a t ,a t+1 ,a t+2,…,a t+n-1 )为n维状态 3几个概念?非退化的移位寄存器?(不)可约多项式?极小多项式?序列和周期?本原多项式?m序列?1游程、 0游程?m序列的游程分布规律 4 线性移存器(一)解方程法已知序列 a是由 n级线性移存器产生的,且知 a 的连续 2n位,可用解线性方程组的方法得到线性递推式。例:设 a=01111000 是4级线性移存器产生的序列的8个连续信号,求该移存器的线性递推式。 5 解:产生 a =01111000 ……的联结多项式?设其联结多项式 f(x)=1+c 1 x+c 2x 2 +c 3x 3 +x 4 ?线性递推式 a t =a t-4 +c 3a t-3 +c 2a t-2 +c 1a t-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+x 3 +x 4 6 (二)、 B-M 迭代算法根据密码学的需要,对线性反馈移位寄存器(LFSR) 主要考虑下面两个问题: (1)如何利用级数尽可能短的 LFSR 产生周期大、随机性能良好的序列,即固定级数时,什么样的移存器序列周期最长。这是从密钥生成角度考虑,用最小的代价产生尽可能好的、参与密码变换的序列。(2)当已知一个长为 N序列 a时,如何构造一个级数尽可能小的 LFSR 来产生它。这是从密码分析角度来考虑,要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过 B-M 算法来解决。 7 1、概念简介设是上的长度为 N的序列,而),,,( 11. 0?? Naaaa? 2F是上的多项式, c 0=1. 2F xf?????? 2210)(lxf ),( 如果 f(x) 是一个能产生 a 并且级数最小的线性移位寄存器的反馈多项式, l是该移存器的级数,则称为序列 a的线性综合解。如果序列中的元素满足递推关系: 则称产生二元序列 a 。其中表示以f(x) 为反馈多项式的 l级线性移位寄存器。)2(1,,1,, 2211??????????Nllkacacaca lklkkk?? lxf ),(lxf ),(8 线性移位寄存器的综合问题可表述为:给定一个线性移位寄存器的综合问题可表述为:给定一个 N N长长二元序列二元序列 a a,如何求出产生这一序列的最小级数的线性移,如何求出产生这一序列的最小级数的线性移位寄存器,即最短的线性移存器? 位寄存器,即最短的线性移存器? 几点说明: 2 、规定: 0级线性移位寄存器是以 f(x)=1 为反馈多项式的线性移位寄存器,且 n长(n =1, 2, …, N)全零序列,仅由 0级线性移位寄存器产生。事实上,以 f(x)=1 为反馈多项式的递归关系式是:a k =0 , k= 0, 1, …, n-,这一规定是合理的。 1 、反馈多项式 f(x)的次数?l。因为产生 a且级数最小的线性移位寄存器可能是退化的,在这种情况下 f(x)的次数<l;并且此时f(x)中的 c l=0,因此在反馈多项式 f(x)中c 0=1,但不要求 c l=1。 3 、给定一个 N长二元序列 a,求能产生 a并且级数最小的线性移位寄存器,就是求 a的线性综合解。利用 B-M 算法可以有效的求出。 9 2、 B-M 算法要点用归纳法求出一系列线性移位寄存器: nnlxf ),(Nnlxf nn,,2,1,)( 0????每一个都是产生序列 a的前 n项的最短线性移位寄存器,在的基础上构造相应的, 使得是产生给定序列前 n+1 项的最短移存器, 则最后得到的就是产生给定 N长二元序列 a的最短的线性移位寄存器。 nnlxf ),( NNlxf ),( 11 ),( ??nnlxf nnlxf ),( 11 ),( ??nnlxf 11 ),( ??nnlxf 10 3、B-M 算法 1、取初始值: 0,1)( 00??lxf2、设均已求得,且)0(Nn?? nnlxflxflxf ),(,, ),(, ),( 1100? nlll???? 10 nnlxf ),(任意给定一个 N长序列,按 n归纳定义 1,,2,1,0??N n?),,,( 11. 0?? Naaaa?记: 再计算: 称d n为第 n步