第17讲--m序列与BM算法(密码学).ppt

第17讲--m序列与BM算法(密码学).ppt

ID:61955603

大小:418.00 KB

页数:14页

时间:2021-04-01

第17讲--m序列与BM算法(密码学).ppt_第1页
第17讲--m序列与BM算法(密码学).ppt_第2页
第17讲--m序列与BM算法(密码学).ppt_第3页
第17讲--m序列与BM算法(密码学).ppt_第4页
第17讲--m序列与BM算法(密码学).ppt_第5页
资源描述:

《第17讲--m序列与BM算法(密码学).ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、M序列与B-M算法1、m序列的统计特性m序列的“0、1”信号的频次规律性质1:r级m序列的一个周期中,1出现个,0出现个。(一)m序列的性质2m序列的游程分布规律若干个信号连续出现的现象称游程。对于序列a,称a中形如01…10或10…01的段为一个1游程或0游程,游程中所含1或0的个数称为该游程的长度,如0110为一个长为2的1游程,101为一个长为1的0游程。3m序列的游程分布规律性质2:将r级m序列的一个周期段首尾相接,其游程总数为N=2r-1;其中没有长度大于r的游程;有1个长度为r的1游程,没有长度为r的0游程;没有长度为r-1的1游程

2、,有1个长度为r-1的0游程;有个长度为的1游程,有个长度为的0游程。42、m序列的移加特性L(t)(a)是左移变换,就是将序列a左移t位所得到的序列。性质3:若是由r级本原线性移存器产生的m序列,则是与平移等价的m序列。性质4:周期为p的m序列,左移t位得到序列,将与按位对齐。则在一个周期段中,序列与序列(0,0)的有(p-3)/4对,(1,1)、(1、0)、(0、1)的各有(p+1)/4对。53、m序列的自相关特性若是一个周期为p的0、1序列,定义{01}上的映射η为:,定义序列的自相关函数为性质5:若是一个r级m序列,那么6(二)、B-M

3、迭代算法根据密码学的需要,对线性反馈移位寄存器(LFSR)主要考虑下面两个问题:(1)如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列,即固定级数时,什么样的移存器序列周期最长。这是从密钥生成角度考虑,用最小的代价产生尽可能好的、参与密码变换的序列。(2)当已知一个长为N序列a时,如何构造一个级数尽可能小的LFSR来产生它。这是从密码分析角度来考虑,要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过B-M算法来解决。71、概念简介设是上的长度为N的序列,而是上的多项式,c0=1.如果f(x)是一个能产生a并且级数最小的线

4、性移位寄存器的反馈多项式,l是该移存器的级数,则称为序列a的线性综合解。如果序列中的元素满足递推关系:则称产生二元序列a。其中表示以f(x)为反馈多项式的l级线性移位寄存器。8线性移位寄存器的综合问题可表述为:给定一个N长二元序列a,如何求出产生这一序列的最小级数的线性移位寄存器,即最短的线性移存器?几点说明:2、规定:0级线性移位寄存器是以f(x)=1为反馈多项式的线性移位寄存器,且n长(n=1,2,…,N)全零序列,仅由0级线性移位寄存器产生。事实上,以f(x)=1为反馈多项式的递归关系式是:ak=0,k=0,1,…,n-1.因此,这一规定

5、是合理的。1、反馈多项式f(x)的次数l。因为产生a且级数最小的线性移位寄存器可能是退化的,在这种情况下f(x)的次数

6、位寄存器。103、B-M算法1、取初始值:2、设均已求得,且任意给定一个N长序列,按n归纳定义记:再计算:称dn为第n步差值。然后分两种情形讨论:11最后得到的便是产生序列a的最短线性移位寄存器。12例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。由a2=1得d2=1•a2=1,从而根据l0=l1=l2=0知f3(x)=1+x2+1=1+x3,

7、l3=3第1步,计算d3:d3=1·a3+0·a2+0·a1+1·a0=1因为l2

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。