第14讲—序列密码.ppt

1、线性移位寄存器,量子密码研究室 王滨 2005年3月29日,2,移位寄存器序列的三种表示方法：,线性递推式（一元多项式）： at+n=c1at+n-1+c2at+n-2+cnat ,t=0 联结多项式： f(x)=1+c1x+c2x2+cnxn 状态转移矩阵： 满足：st+1=stTf 称st=(at,at+1,at+2,at+n-1)为n维状态,3,实例（画出移存器的逻辑框图，写出相应的线性 递推式）,多项式 答案： 线性递推式： at=at-4+at-3+at-2,4,非退化的移位寄存器,若反馈函数形如： ，其中 ，则称其为线性反馈寄存器；否则称其为非线性反馈移为寄存器。 其中 ，若 我们

2、说该寄存器是退化的，否则是非退化的。,5,移位寄存器序列空间,符号说明：G(f)表示以f(x)为联结多项式的n级线性移位寄存器序列构成的空间 定理1：G(f)是GF(q)上的一个n维线性空间。 证明：只需证明G(f)中的任意两个序列的任意线性组合也属于G(f)即可。即证： 特例：当q=2时，G(f)中任意两个序列之和仍然属于G(f)。,6,(不)可约多项式 定义：若存在g(x),h(x)，使得f(x)=g(x)h(x)，则称f(x)是可约多项式；否则，称其为不可约多项式。,(不)可约多项式,7,定理2：若f(x)|h(x)，则G(f) G(h).,例1：联结多项式为 f(x)=x4+x3+x+

3、1=(x+1)2(x2+x+1) 线性递推式：at=at-4+at-3+at-1 输出序列：000111/000111/ 周期为6 011/011/ 周期为3 001/001/ 周期为3 01/01/ 周期为2 111111. 周期为1 000000 周期为1,8,极小多项式,定义：对于一条移位寄存器序列a，称其联结多项式中次数最低的多项式为a的极小多项式。 定义：满足f(x)|1-xr 的最小正整数r为f(x)的周期，记为p(f(x)，简记为p(f)。 例子：x4+x3+x2+x+1的周期为5 (x4+x3+x2+x+1)(x+1)=x5+1,9,序列和周期,一般地，一个移存器序列表示为：

4、对于序列 ，若存在整数p使得对任意正整数k有 成立，称满足该式的最小正整数p为序列的周期。 r级线性反馈移存器的最长周期: ，能达到最长周期的线性移存器序列称为m序列。 在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即m序列。,10,本原多项式,若n次多项式f(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。 以本原多项式为连接多项式产生的非零序列均是m序列。,11,m序列特性,m序列的统计特性 1、 m序列的“0、1”信号的频次规律,性质1 ：r级m序列的一个周期中，1出现 个， 0出现 个。,12,

5、m序列的游程分布规律,若干个信号连续出现的现象称游程。对于序列a，称a中形如0110或1001的段为一个1游程或0游程，游程中所含1或0的个数称为该游程的长度，如0110为一个长为2的1游程，101为一个长为1的0游程。,13,m序列的游程分布规律,性质2：将r级m序列的一个周期段首尾相接，其游程总数为N=2r-1；其中没有长度大于r的游程；有1个长度为r的1游程，没有长度为r的0游程；没有长度为 r-1的1游程，有1个长度为r-1的0游程；有 个长度为 的1游程，有 个长度 为 的0游程。,14,二、m序列特性,（一）统计特性,1、“0、1”信号频次 性质1 ：r级m序列的一个周期中，1出现

6、 个， 0出现 个。,2、游程分布 性质2：在r级m序列的一个周期中，有1个长度为r的1游程和1个长度为r-1的0游程；长度为 的1游程和0游程各有 个。,15,二、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对。,16,二、m序列特性,（三）自相关特性,若 是一个周期为p的0、1序列，定义0 1上的映射为： ，定义 序列 的自相关函数为,性质5：若 是一个r级m序列，那么,17,习 题,一、一个线性移存器如图， （1）写出该线性移存器的线性递推式。 （2）写出该线性移存器的联接多项式。 （3）写出该线性移存器生成的序列。,二、已知 是6次本原多项式，a是 生成的m序列， （1） a的周期是多少？ （2） a在的一个周期内，0、1各出现多少次？ （3）