GF(2)上的一个无限序列a=(a1,a2,……,an,……)称为二元序列。
周期:对于二元序列a,如果存在正整数l,使得对于一切正整数k都有ak=a(k+l),则称a是周期的。满足上述条件的最小正整数称为a的周期,记为p(a)。
游程的定义
设a是GF(2)上周期为p(a)的周期序列。将a的一个周期依次排列在一个圆周上使a(p(a))与a1相连,把这个圆周上形如
的一连串两两相邻的项分别称为a的一个周期中一个1游程或一个0游程。而1游程中1的个数或0游程中0的个数称为游程的长度。例如011110为1的4游程,10001为0的3游程。
自相关函数
GF(2)上周期为T的序列{ai}的自相关函数定义为
Golomb伪随机公设
3个随机性公设:
满足这三个随机性公设的序列就是伪随机序列。反馈移位寄存器
移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成,如下图所示:
在任意时刻,这些级的内容构成该反馈移位寄存器的状态,每一状态对应于GF(2)上的一个n维向量,共有2的n次方种可能的状态。每一时刻的状态可用n维向量(a1,a2,…,an)表示,其中ai是第i级存储器的内容。
反馈函数初始状态由用户确定。反馈函数f(a1,a2,…,an)是n元布尔函数,即函数的自变量和因变量只取0和1这两个可能的值。函数中的运算有逻辑与、逻辑或、逻辑补等运算。
线性反馈移位寄存器LFSR(linear feedback shift register)
LFSR的反馈函数的一般形式为:
线性反馈移位寄存器实现起来简单,速度快,而且有较为成功的理论,成为构造密钥流生成器的最重要的部件之一。
我们总是假定c1,c2,…,cn中至少有一个不为0,否则f(a1,a2,…,an)=0,总是假定cn=1。
LFSR的性质:
LFSR输出序列的性质:完全由其反馈函数确定
n级LFSR状态数:最多有(2^n)个
n级LFSR的状态周期:<=(2^n)-1
输出序列的周期=状态周期,<=(2^n)-1
选择合适的反馈函数可使序列的周期达到最大值(2^n)-1,周期达到最大值的序列称为m序列。
已知序列获得相应的反馈多项式有两种方法: 解方程法——已知序列{a}是由n级线性移位寄存器产生的,并且知道{a}的连续2n位,可用解线性方程组的方法得到反馈多项式 线性反馈移位寄存器综合解——Berlekamp-Massey算法 线性反馈移位寄存器综合 根据密码学的需要,对线性反馈移位寄存器(LFSR)主要考虑下面两个问题: (1)如何利用级数尽可能短的LFSR产生周期大、随即性能良好的序列。 (2)已知一个长为N的序列a时,如何构造一个级数尽可能小的LFSR来产生它。 如果f(x)是一个能产生a并且级数最小的线性移位寄存器的特征多项式,l是该移位寄存器的级数,则称<f(x),l>为序列a的线性综合解。 给定一个N长二元序列a,求能产生a并且级数最小的线性移位寄存器,就是求a的线性综合解,我们可以利用B-M算法有效的求出。 线性移位寄存器的一元多项式表示
设n级线性移位寄存器的输出序列满足递推关系
用延迟算子D(Dak=ak-1)作为未定元,给出的反馈多项式为:
这种递推关系可用一个一元高次多项式
表示,称这个多项式为LFSR的特征多项式。
根据初始状态的不同,由递推关系生成的非恒零的序列有2n-1个,记这2n-1个非零序列的全体为G(p(x))。
给定序列{ai},幂级数
称为该序列的生成函数。生成函数满足:
不可约多项式
设p(x)是n次不可约多项式,周期为m,序列{ai}属于G(p(x)),则{ai}的周期为m。
m-序列产生的必要条件
n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约的。
m序列满足Golomb的3个随机性公设,所以m序列有伪随机性。
|