第14讲—序列密码.ppt

线性移位寄存器、量子密码研究室王滨2005年3月29日、2、移位寄存器系列的3种表现方法：线性递归式(一项多项式):at n=c1at n-1 c2at n-2 cnat，t=0连接多项式： f(x )=1 c1x c2x2 cnxn状态转换矩阵：满足ST1=sttf:ST=(at at 1，at 2，at n-1 )为n维状态，3实例(描绘存储器的逻辑框图，写出相应的线性递归式)，多项式的答案：线性递归式： at=at-1 4、非简并移位寄存器、反馈函数形式：其中，称为线性反馈寄存器的其他情况下，非线性反馈称为移位寄存器。 这里，如果说该寄存器劣化，则说该寄存器没有劣化。 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，定理f(x)|h(x )的话g (h )例1 :连接多项式是f(x)=x4 x3 x 1=(x 1)2(x2 x 1)线性递归式： at=at-4 at-3 at-1输出序列： 000111/000111/周期是6011 001/周期是301/01/ 周期是2111111周期是1000000周期是1、8，极小多项式，定义：对于移位寄存器序列a，在其连接多项式中次数最低的多项式被称为a的极小多项式。 定义：将满足f(x)|1-xr的最小正整数r设为f(x )的周期简称为p(f(x ) )、p(f )。 例如，x4 x3 x2 x 1的周期是5 (x4x3x2x1) (x1 )=x51，9，9，序列和周期，一般地，如果存在整数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个周期中、1个出现个、0个出现个。 另外，12，m序列的行程长度分布规则，几个信号连续出现的现象被称为行程长度。 关于系列a，将a中的像0110或1001这样的段称为一个行程长度或0行程长度，将行程中包含的1或0的个数称为该行程长度的长度，例如0110是一个长度为2的一行程长度，101是一个长度为1的长度将13、m序列的游程长度分布规则、性质2:r级m序列的一个周期段顺利地连接起来，其游程长度总数为N=2r-1，其中有没有比r长的游程长度的长度为r的一个行程，没有长度为r的没有0行程的长度为r-1的一个行程，长度为r-1 、14、二、m序列特性、(一)统计特性、1、“0，1”信号频度特性1 :在r级m序列的一个周期中出现1，0。 2、行程长度分布的性质2:r等级m序列的一个周期中，有一个长度为r的一个行程长度和一个长度为r-1的0行程长度的一个行程和零行程分别有。 另外，15、2、m序列特性、(2)位移特性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序列的话，01上的映射:定义序列的自相关函数，性质5:r级m序列的话，17、练习问题、一、线性存储器如图所示，(1)写该线性存储器的线性递归式。 (2)写出该线性存储器的结合多项式。 (3)写出该线性存储器生成的序列。 二、已知是6次本