文档介绍：B-M B-M 算算法法量子密码研究室量子密码研究室王王滨滨 2005 2005 年年4 4月月6 6日日 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 a =01111000 =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 ),(任意给定一个