【文档说明】【安全课件】第14讲—序列密码.pptx，共(18)页，155.478 KB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-287948.html

以下为本文档部分文字说明：

线性移位寄存器量子密码研究室王滨2005年3月29日1移位寄存器序列的三种表示方法：⚫线性递推式（一元多项式）：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维状态2实例（画出移存器的逻辑框图，写出相应的线性递推式）多项式答案：线性递推式：at=at-4+at-3+at-2432()1fxxxx=x

1x2x3x43非退化的移位寄存器若反馈函数形如：，其中，则称其为线性反馈寄存器；否则称其为非线性反馈移为寄存器。其中，若我们说该寄存器是退化的，否则是非退化的。(),1icGFqin121121(,,

,)nnnnfxxxcxcxcx−=+++0nc0nc=4移位寄存器序列空间⚫符号说明：G(f)表示以f(x)为联结多项式的n级线性移位寄存器序列构成的空间⚫定理1：G(f)是GF(q)上的一个n维线性空间。⚫证明：只需证明G(f)中的任意两个序列的任意线性组合也

属于G(f)即可。即证：⚫特例：当q=2时，G(f)中任意两个序列之和仍然属于G(f)。)(,),(),(),(qGFfGbafGbfGa+5(不)可约多项式⚫定义：若存在g(x),h(x)，使得f(x)=g(

x)h(x)，则称f(x)是可约多项式；否则，称其为不可约多项式。(不)可约多项式6定理2：若f(x)|h(x)，则G(f)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//011//……周期为3001//001//……周期为301//01//……周期为2111111…..周期为1000000……周期为17极小多项式⚫定义：对于

一条移位寄存器序列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+18序列和周期一般地，一个移存器序列表示为：•对于序列，若存在整数p使得对任意正整数k有成立，称满足该式的最小正整数p为序列的周期。r级线性反馈移存器的最长周期:，能达到最长周期的线性移

存器序列称为m序列。•在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即m序列。iaaaaa210=iaaaaa210=pkkaa+=12−r9本原多项式若n次多项式f

(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。以本原多项式为连接多项式产生的非零序列均是m序列。10m序列特性m序列的统计特性1、m序列的“0、1”信号的频次规律性质1：r级m序列的一个周期中，1出现个，0出现个。12−r12

1−−r11m序列的游程分布规律⚫若干个信号连续出现的现象称游程。对于序列a，称a中形如01…10或10…01的段为一个1游程或0游程，游程中所含1或0的个数称为该游程的长度，如0110为一个长为2的1游程，101为一个长为1的0游程。12m序列的游程分布规律性质2：将r级m序列的一

个周期段首尾相接，其游程总数为N=2r-1；其中没有长度大于r的游程；有1个长度为r的1游程，没有长度为r的0游程；没有长度为r-1的1游程，有1个长度为r-1的0游程；有个长度为的1游程，有个长度为的0游程。)21(−rkkkr−−22kr−−22)21(−rkk13

二、m序列特性（一）统计特性1、“0、1”信号频次性质1：r级m序列的一个周期中，1出现个，0出现个。12−r121−−r2、游程分布性质2：在r级m序列的一个周期中，有1个长度为r的1游程和1个长度为r-1的0游程；长度为的1游程和0游程各有个。)21(−rk

kkr−−2214二、m序列特性（二）移加特性L(t)(a)是左移变换，就是将序列a左移t位所得到的序列。性质3：若是由r级本原线性移存器产生的m序列,则是与平移等价的m序列。aa)12mod0()()(−rttaLa性质4：周期为p的m序列，左移t

位得到序列，将与按位对齐。则在一个周期段中，序列与序列（0，0）的有(p-3)/4对，（1，1）、（1、0）、（0、1）的各有(p+1)/4对。aaabbb)12mod0(−rt15二、m序列特性（三）自相关特性若是一个周期为p的0、1序列，定义{01}

上的映射η为：，定义序列的自相关函数为)(210aaaa=1)1(,1)0(−==)()()(10tipiiaatC+−==)(210aaaa=性质5：若是一个r级m序列，那么−−=−==+−=120,10,12)()()(220rrtiiittaatCr

)(210aaaa=16习题一、一个线性移存器如图，（1）写出该线性移存器的线性递推式。（2）写出该线性移存器的联接多项式。（3）写出该线性移存器生成的序列。1342二、已知是6次本原多项式，a是生成的m序列，（1）a的周期是多少？（2）a在的一个周期内，0、1各出现多少次？（3）a

在的一个周期内，游程分布如何？1)(6=xxxf)(xf17反馈多项式的含义一个r级线性移存器的线性递推式表示为：)(2211rnacacacarnrnnn=−−−引进迟延算子D：IDaaDaDaikkikk===−−01,,递推式可改写为：02

210=nrrnnnaDcaDcDacIac将上式中的D用符号x代替，引入多项式：1)(111=−−xcxcxcxfrrrr从而有：)(,0)(rnaDfn=那么对于序列a，0)(=aDf即：0)(2210=nrraDcDcDcc10

=c18