第17讲--BM算法_第1页
第17讲--BM算法_第2页
第17讲--BM算法_第3页
第17讲--BM算法_第4页
第17讲--BM算法_第5页
已阅读5页,还剩9页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、2移位寄存器序列的三种表示方法:v线性递推式(一元多项式): at+n=c1at+n-1+c2at+n-2+cnat ,t=0v联结多项式: f(x)=1+c1x+c2x2+cnxnv状态转移矩阵: 满足:st+1=stTf 称st=(at,at+1,at+2,at+n-1)为n维状态3v非退化的移位寄存器v(不)可约多项式v极小多项式v序列和周期v本原多项式vm序列v1游程、游程、0游程游程vm序列的游程分布规律4线性移存器线性移存器(一)解方程法(一)解方程法 已知序列a是由n级线性移存器产生的,且知a的连续2n位,可用解线性方程组的方法得到线性递推式。 例:设a=01111000是4级线

2、性移存器产生的序列的8个连续信号,求该移存器的线性递推式。5v设其联结多项式f(x)=1+c1x+c2x2+c3x3+x4v线性递推式at=at-4+c3at-3+c2at-2+c1at-1v0+c3+c2+c1=1v1+c3+c2+c1=0v1+c3+c2+0=0v1+c3+0+0=0v解得:c3=1;c2=0;c1=0v故其联结多项式为1+x3+x46(二)、(二)、B-MB-M迭代算法迭代算法 根据密码学的需要,对线性反馈移位寄存器根据密码学的需要,对线性反馈移位寄存器(LFSR)(LFSR)主要考虑下面两个问题:主要考虑下面两个问题:(1)如何利用级数尽可能短的LFSR产生周期大、随机

3、性能良好的序列,即固定级数时,什么样的移存器序列周期最长。这是从密钥生成角度考虑,用最小的代价这是从密钥生成角度考虑,用最小的代价产生尽可能好的产生尽可能好的、参与密码变换的序列。参与密码变换的序列。 (2)当已知一个长为N序列a时,如何构造一个级数尽可能小的LFSR来产生它。这是从密码分析角度来考这是从密码分析角度来考虑,要想用线性方法重构密钥序列所必须付出的最小代价。虑,要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过这个问题可通过B-MB-M算法来解决。算法来解决。71 1、概念简介、概念简介设 是 上的长度为N的序列,而 ),(11. 0Naaaa2F是 上的多项式,c0

4、=1.2Fllxcxcxccxf2210)(lxf),(如果f(x)是一个能产生a并且级数最小的线性移位寄存器的反馈多项式,l是该移存器的级数,则称 为序列序列a的的线性综合解线性综合解。如果序列中的元素满足递推关系: 则称 产生二元序列a。其中 表示以f(x)为反馈多项式的l级线性移位寄存器。)2(1, 1,2211Nllkacacacalklkkklxf),(lxf),(8 几点说明:几点说明: 2、规定:规定:0级线性移位寄存器是以级线性移位寄存器是以f( (x)=1)=1为反馈多项式的为反馈多项式的线性移位寄存器,且线性移位寄存器,且n长长(n=1, 2, , N)全零序列,仅由全零序

5、列,仅由0级线性级线性移位寄存器产生。移位寄存器产生。事实上,以f(x)=1为反馈多项式的递归关系式是:ak=0,k=0, 1, , n-1.因此,这一规定是合理的。 1、反馈多项式反馈多项式f( (x) )的次数的次数 l。因为产生因为产生a且级数最小的线性且级数最小的线性移位寄存器可能是退化的,在这种情况下移位寄存器可能是退化的,在这种情况下 f(x)的次数的次数l;并且此;并且此时时 f(x)中的中的cl=0=0,因此在反馈多项式,因此在反馈多项式f(x)中中c0=1=1,但不要求,但不要求cl=1=1。 3、给定一个N长二元序列a,求能产生a并且级数最小的线性移位寄存器,就是求a的线性

6、综合解的线性综合解。利用利用B-MB-M算法算法可以有效的求出。可以有效的求出。92、B-M算法要点算法要点用归纳法求出一系列线性移位寄存器:nnlxf),(Nnlxfnn, 2 , 1,)(0每一个 都是产生序列a的前n项的最短线性移位寄存器,在 的基础上构造相应的 ,使得 是产生给定序列前n+1项的最短移存器,则最后得到的 就是产生给定N长二元序列a的最短的线性移位寄存器。nnlxf),(NNlxf),(11),(nnlxfnnlxf),(11),(nnlxf11),(nnlxf103 3、B-MB-M算法算法 1、取初始值:0, 1)(00lxf 2、设 均已求得,且)0(Nn nnlx

7、flxflxf),(,),(,),(1100nlll10nnlxf),(任意给定一个N长序列 ,按n归纳定义1, 2, 1, 0Nn),(11. 0Naaaa记: 再计算:称dn为第n步差值。然后分两种情形讨论: , 1,)()(0)()(1)(0nlnlnnncxcxccxfnnnnlnnlnnnnnacacacd)(1)(1)(011最后得到的 便是产生序列a的最短线性移位寄存器。NNlxf),(12B - M算法流程13例2、求产生周期为7的m序列一个周期:0011101的最短线性移位寄存器。4、实例实例解:设 ,首先取初值 f0(x)=1, l0=0 ,则由a0=0得d0=1a0=0从

8、而 f1(x)=1, l1=0 ;同理由a1=0得d1=1a1=0从而 f2(x)=1, l2=0 。00111016543210aaaaaaa由a2=1得d2=1a2=1,从而根据l0= l1 = l2=0 知 f2(x)=1+x2+1 =1+x3, l3=3 第1步,计算d3:d3=1a3+ 0a2 + 0a1 + 1a0=1因为l2l3,故m=2,由此31 , 3max313 , 3max1)()()(4322334lxxxfxxfxf14 第2步,计算d4:d4=1a4 + 1a3 + 0a2 + 1a1=0,从而31)()(45345llxxxfxf 第3步,计算d5:d5=1a5 + 1a4 + 0

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论