【安全课件】第17讲--bm算法

B-M算法量子密码研究室王滨2005年4月6日2上节内容复习移位寄存器序列的三种表示方法：线性递推式（一元多项式）：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维状态3几个概念非退化的移位寄存器(不)可约多项式极小多项式序列和周期本原多项式m序列1游程、0游程m序列的游程分布规律4线性移存器（一）解方程法已知序列a是由n级线性移存器产生的，且知a的连续2n位，可用解线性方程组的方法得到线性递推式。例：设a=01111000是4级线性移存器产生的序列的8个连续信号，求该移存器的线性递推式。5解：产生a=01111000……的联结多项式设其联结多项式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+x46（二）、B-M迭代算法根据密码学的需要，对线性反馈移位寄存器(LFSR)主要考虑下面两个问题：（1）如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列，即固定级数时，什么样的移存器序列周期最长。这是从密钥生成角度考虑，用最小的代价产生尽可能好的、参与密码变换的序列。（2）当已知一个长为N序列a时，如何构造一个级数尽可能小的LFSR来产生它。这是从密码分析角度来考虑，要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过B-M算法来解决。71、概念简介设是上的长度为N的序列，而),,,(11.0Naaaa2F是上的多项式，c0=1.2Fllxcxcxccxf2210)(lxf),(如果f(x)是一个能产生a并且级数最小的线性移位寄存器的反馈多项式，l是该移存器的级数，则称为序列a的线性综合解。如果序列中的元素满足递推关系：则称产生二元序列a。其中表示以f(x)为反馈多项式的l级线性移位寄存器。)2(1,,1,,2211Nllkacacacalklkkklxf),(lxf),(8线性移位寄存器的综合问题可表述为：给定一个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算法可以有效的求出。92、B-M算法要点用归纳法求出一系列线性移位寄存器：nnlxf),(Nnlxfnn,,2,1,)(0每一个都是产生序列a的前n项的最短线性移位寄存器，在的基础上构造相应的，使得是产生给定序列前n+1项的最短移存器，则最后得到的就是产生给定N长二元序列a的最短的线性移位寄存器。nnlxf),(NNlxf),(11),(nnlxfnnlxf),(11),(nnlxf11),(nnlxf103、B-M算法1、取初始值：0,1)(00lxf2、设均已求得，且)0(Nnnnlxflxflxf),(,,),(,),(1100nlll10nnlxf),(任意给定一个N长序列，按n归纳定义1,,2,1,0Nn),,,(11.0Naaaa记：再计算：称dn为第n步差值。然后分两种情形讨论：,1,)()(0)()(1)(0nlnlnnncxcxccxfnnnnlnnlnnnnnacacacd)(1)(1)(011（ⅰ）若nd=0，则令：nnnnllxfxf11),()(。（ⅱ）若nd=1，则需区分以下两种情形：①当：010nlll时，取：1,1)(111nlxxfnnn。②当有m（nm0），使：nmmmllll21。便置：}1,max{),()()(11nnnmmnnnlnllxfxxfxf最后得到的便是产生序列a的最短线性移位寄存器。NNlxf),(12B-M算法流程13例2、求产生周期为7的m序列一个周期：0011101的最短线性移位寄存器。4、实例解：设，首先取初值f0(x)=1,l0=0，则由a0=0得d0=1•a0=0从而f1(x)=1,l1=0；同理由a1=0得d1=1•a1=0从而f2(x)=1,l2=0。00111016543210aaaaaaa由a2=1得d2=1•a2=1，从而根据l0=l1=l2=0知f2(x)=1+x2+1=1+x3,l3=3第1步，计算d3：d3=1·a3+0·a2+0·a1+1·a0=1因为l2l3，故m=2，由此3}1,3max{}313,3max{1)()()(4322334lxxxfxxfxf14第2步，计算d4：d4=1·a4+1·a3+0·a2+1·a1=0，从而31)()(45345llxxxfxf第3步，计算d5：d5=1·a5+1·a4+0·a3+1·a2=0，从而第4步，计算d6：d6=1·a6+1·a5+0·a4+1·a3=0，从而31)()(56356llxxxfxf31)()(67367llxxxfxf这表明，即为产生所给序列一个周期的最短线性移位寄存器。3,13xx