文档介绍：M 序列与 B-M 算法
1
1、 m序列的统计特性
m序列的“0、1”信号的频次规律
性质1 :r级m序列的一个周期中,1出现个,
0出现个。
(一)m序列的性质
2
m序列的游程分布规律
若干个信号连续出现的现象称游程。对于序列a,称a中形如01…10或10…01的段为一个1游程或0游程,游程中所含1或0的个数称为该游程的长度,如0110为一个长为2的1游程,101为一个长为1的0游程。
3
m序列的游程分布规律
性质2:将r级m序列的一个周期段首尾相接,其游程总数为N=2r-1;其中没有长度大于r的游程;有1个长度为r的1游程,没有长度为r的0游程;没有长度为 r-1的1游程,有1个长度为r-1的0游程;有个长度为的1游程,有个长度为的0游程。
4
2、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对。
5
3、m序列的自相关特性
若是一个周期为p的0、1序列,定义{0 1}上的映射η为: ,定义序列的自相关函数为
性质5:若是一个r级m序列,那么
6
(二)、B-M迭代算法
根据密码学的需要,对线性反馈移位寄存器(LFSR)主要考虑下面两个问题:
(1)如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列,即固定级数时,什么样的移存器序列周期最长。这是从密钥生成角度考虑,用最小的代价产生尽可能好的、参与密码变换的序列。
(2)当已知一个长为N序列a时,如何构造一个级数尽可能小的LFSR来产生它。这是从密码分析角度来考虑,要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过B-M算法来解决。
7
1、概念简介
设是上的长度为N的序列,而
是上的多项式,c0=1.
如果f(x)是一个能产生a并且级数最小的线性移位寄存器的反馈多项式,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、反馈多项式f(x)的次数l。因为产生a且级数最小的线性移位寄存器可能是退化的,在这种情况下 f(x)的次数<l;并且此时 f(x)中的cl=0,因此在反馈多项式f(x)中c0=1,但不要求cl=1。
3、给定一个N长二元序列a,求能产生a并且级数最小的线性移位寄存器,就是求a的线性综合解。利用B-M算法可以有效的求出。
9
2、B-M算法要点
用归纳法求出一系列线性移位寄存器:
每一个都是产生序列a的前n项的最短线性移位寄存器,在的基础上构造相应的,使得是产生给定序列前n+1项的最短移存器,则最后得到的就是产生给定N长二元序列a的最短的线性移位寄存器。
10