【安全课件】第14讲—序列密码课件.pptx
线性移位寄存器线性移位寄存器量子密码研究室 2005年3月29日1移位寄存器序列的三种表示方法：移位寄存器序列的三种表示方法：l线性递推式（一元多项式）：at+n=c1at+n-1+c2at+n-2+cnat ,t=0l联结多项式：f(x)=1+c1x+c2x2+cnxnl状态转移矩阵：满足：st+1=stTf 称st=(at,at+1,at+2,at+n-1)为n维状态2实例实例（画出移存器的逻辑框图，写出相应的线性（画出移存器的逻辑框图，写出相应的线性 递推式）递推式）多项式多项式答案：答案：线性递推式：at=at-4+at-3+at-2x1x2x3x43非退化的移位寄存器非退化的移位寄存器 若反馈函数形如：若反馈函数形如：，其中，其中 ，则称其为，则称其为线性反馈寄存线性反馈寄存器器；否则称其为；否则称其为非线性反馈移为寄存器非线性反馈移为寄存器。其中其中 ，若，若 我们说该寄存器是我们说该寄存器是退化的，退化的，否则是否则是非退化的非退化的。4移位寄存器序列空间移位寄存器序列空间l符号说明：G(f)表示以f(x)为联结多项式的n级线性移位寄存器序列构成的空间l定理1：G(f)是GF(q)上的一个n维线性空间。l证明：只需证明G(f)中的任意两个序列的任意线性组合也属于G(f)即可。即证：l特例：当q=2时，G(f)中任意两个序列之和仍然属于G(f)。5(不)可约多项式l定义：若存在g(x),h(x)，使得f(x)=g(x)h(x)，则称f(x)是可约多项式；否则，称其为不可约多项式。(不不)可约多项式可约多项式6定理定理2：若：若f(x)|h(x)，则，则G(f)G(h).l例1：联结多项式为 f(x)=x4+x3+x+1=(x+1)2(x2+x+1)l线性递推式：at=at-4+at-3+at-1l输出序列：000111/000111/周期为6 011/011/周期为3 001/001/周期为3 01/01/周期为2 111111.周期为1 000000 周期为17极小多项式极小多项式l定义：对于一条移位寄存器序列a，称其联结多项式中次数最低的多项式为a的极小多项式。l定义：满足f(x)|1-xr 的最小正整数r为f(x)的周期，记为p(f(x)，简记为p(f)。l例子：x4+x3+x2+x+1的周期为5 (x4+x3+x2+x+1)(x+1)=x5+18序列和周期序列和周期一般地，一个移存器序列表示为：对于序列 ，若存在整数p使得对任意正整数k有 成立，称满足该式的最小正整数p为序列的周期序列的周期。r级线性反馈移存器的最长周期:，能达到最长周期的线性移存器序列称为m序列序列。在在密密码码学学中中，我我们们希希望望参参与与变变换换的的序序列列周周期期越越长长越越好好，因因此此对对线线性性反反馈馈移移存存器器我我们们更更感感兴兴趣趣的是能达到最长周期的序列，即的是能达到最长周期的序列，即m序列。序列。9本原多项式本原多项式 若n次 多 项 式f(x)是 不 可 约 多 项 式 且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。以本原多项式为连接多项式产生的非零序列均是m序列。10m序列特性序列特性m序列的统计特性序列的统计特性1、m序列的序列的“0、1”信号的频次规律信号的频次规律性质性质1 1：r级m序列的一个周期中，1出现 个，0出现 个。11m序列的游程分布规律序列的游程分布规律l若干个信号连续出现的现象称游程游程。对于序列a，称a中形如0110或1001的段为一个1游游程或程或0游程游程，游程中所含1或0的个数称为该游程的长度，如0110为一个长为2的1游程，101为一个长为1的0游程。12m序列的游程分布规律序列的游程分布规律性质性质2 2：将r级m序列的一个周期段首尾相接，其游程总数为N=2r-1；其中没有长度大于r的游程；有1个长度为r的1游程，没有长度为r的0游程；没有长度为 r-1的1游程，有1个长度为r-1的0游程；有 个长度为 的1游程，有 个长度 为 的0游程。13二、二、m序列特性序列特性（一）统计特性（一）统计特性1、“0、1”信号频次 性质性质1：r级m序列的一个周期中，1出现 个，0出现 个。2、游程分布性质性质2：在r级m序列的一个周期中，有1个长度为r的1游程和1个长度为r-1的0游程；长度为 的1游程和0游程各有 个。14二、二、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对。15二、二、m序列特性序列特性（三）自相关特性（三）自相关特性 若 是一个周期为p的0、1序列，定义0 1上的映射为：，定义 序列 的自相关函数为性质性质5 5：若 是一个r级m序列，那么16习 题一、一个线性移存器如图，（1）写出该线性移存器的线性递推式。（2）写出该线性移存器的联接多项式。（3）写出该线性移存器生成的序列。1342二、已知 是6次本原多项式，a是 生成的m序列，（1）a的周期是多少？（2）a在的一个周期内，0、1各出现多少次？（3）a在的一个周期内，游程分布如何？17反馈多项式的含义反馈多项式的含义一个r级线性移存器的线性递推式表示为：引进迟延算子D：递推式可改写为：将上式中的D用符号x代替，引入多项式：从而有：那么对于序列a，即：181、有时候读书是一种巧妙地避开思考的方法。3月-233月-23Wednesday,March 29,20232、阅读一切好书如同和过去最杰出的人谈话。17:26:1717:26:1717:263/29/2023 5:26:17 PM3、越是没有本领的就越加自命不凡。3月-2317:26:1717:26Mar-2329-Mar-234、越是无能的人，越喜欢挑剔别人的错儿。17:26:1717:26:1717:26Wednesday,March 29,20235、知人者智，自知者明。胜人者有力，自胜者强。3月-233月-2317:26:1717:26:17March 29,20236、意志坚强的人能把世界放在手中像泥块一样任意揉捏。29 三月 20235:26:17 下午17:26:173月-237、最具挑战性的挑战莫过于提升自我。三月 235:26 下午3月-2317:26March 29,20238、业余生活要有意义，不要越轨。2023/3/29 17:26:1717:26:1729 March 20239、一个人即使已登上顶峰，也仍要自强不息。5:26:17 下午5:26 下午17:26:173月-2310、你要做多大的事情，就该承受多大的压力。3/29/2023 5:26:17 PM17:26:1729-3月-2311、自己要先看得起自己，别人才会看得起你。3/29/2023 5:26 PM3/29/2023 5:26 PM3月-233月-2312、这一秒不放弃，下一秒就会有希望。29-Mar-2329 March 20233月-2313、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Wednesday,March 29,202329-Mar-233月-2314、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。3月-2317:26:1729 March 202317:26谢谢大家谢谢大家
