现在密码学第讲BM算法.ppt
- 文档编号:18767147
- 上传时间:2023-11-04
- 格式:PPT
- 页数:12
- 大小:404.50KB
现在密码学第讲BM算法.ppt
《现在密码学第讲BM算法.ppt》由会员分享,可在线阅读,更多相关《现在密码学第讲BM算法.ppt(12页珍藏版)》请在冰点文库上搜索。
B-M算法,2,线性移存器,
(一)解方程法,已知序列a是由n级线性移存器产生的,且知a的连续2n位,可用解线性方程组的方法得到线性递推式。
例:
设a=01111000是4级线性移存器产生的序列的8个连续信号,求该移存器的线性递推式。
3,解:
产生a=01111000的联系多项式,设其联结多项式f(x)=1+c1x+c2x2+c3x3+x4线性递推式at=at-4+c3at-3+c2at-2+c1at-10+c3+c2+c1=11+c3+c2+c1=01+c3+c2+0=01+c3+0+0=0解得:
c3=1;c2=0;c1=0故其联结多项式为1+x3+x4,4,
(二)、B-M迭代算法,根据密码学的需要,对线性反馈移位寄存器(LFSR)主要考虑下面两个问题:
(1)如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列,即固定级数时,什么样的移存器序列周期最长。
这是从密钥生成角度考虑,用最小的代价产生尽可能好的、参与密码变换的序列。
(2)当已知一个长为N序列a时,如何构造一个级数尽可能小的LFSR来产生它。
这是从密码分析角度来考虑,要想用线性方法重构密钥序列所必须付出的最小代价。
这个问题可通过B-M算法来解决。
5,1、概念简介,设是上的长度为N的序列,而,是上的多项式,c0=1.,如果f(x)是一个能产生a并且级数最小的线性移位寄存器的联系多项式,l是该移存器的级数,则称为序列a的线性综合解。
如果序列中的元素满足递推关系:
则称产生二元序列a。
其中表示以f(x)为联系多项式的l级线性移位寄存器。
6,线性移位寄存器的综合问题可表述为:
给定一个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算法可以有效的求出。
7,2、B-M算法要点,用归纳法求出一系列线性移位寄存器:
每一个都是产生序列a的前n项的最短线性移位寄存器,在的基础上构造相应的,使得是产生给定序列前n+1项的最短移存器,则最后得到的就是产生给定N长二元序列a的最短的线性移位寄存器。
8,3、B-M算法,1、取初始值:
2、设均已求得,且,任意给定一个N长序列,按n归纳定义,记:
再计算:
称dn为第n步差值。
然后分两种情形讨论:
9,最后得到的便是产生序列a的最短线性移位寄存器。
10,B-M算法流程,11,例2、求产生周期为7的m序列一个周期:
0011101的最短线性移位寄存器。
4、实例,解:
设,首先取初值f0(x)=1,l0=0,则由a0=0得d0=1a0=0从而f1(x)=1,l1=0;同理由a1=0得d1=1a1=0从而f2(x)=1,l2=0。
由a2=1得d2=1a2=1,从而根据l0=l1=l2=0知f3(x)=1+x2+1=1+x3,l3=3,第1步,计算d3:
d3=1a3+0a2+0a1+1a0=1因为l2l3,故m=2,由此,12,第2步,计算d4:
d4=1a4+1a3+0a2+1a1=0,从而,第3步,计算d5:
d5=1a5+1a4+0a3+1a2=0,从而,第4步,计算d6:
d6=1a6+1a5+0a4+1a3=0,从而,这表明,即为产生所给序列一个周期的最短线性移位寄存器。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 现在 密码学 BM 算法