[精选]【安全课件】第14讲—序列密码.pptx

《[精选]【安全课件】第14讲—序列密码.pptx》由会员分享，可在线阅读，更多相关《[精选]【安全课件】第14讲—序列密码.pptx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性移位存放器量子密码研究室 2005年3月29日1移位存放器序列的三种表示方法：l 线性递推式一元多项式：at+n=c1at+n-1+c2at+n-2+cnat,t=0l 联结多项式：fx=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非退化的移位存放器 假设反响函数形如：，其中，则称其为线性反响存放器；否则称其为非线性反响移为存放器。其中，假设 我们说该存放器是退化的，否则是非退化的

2、。4移位存放器序列空间l 符号说明：Gf表示以fx为联结多项式的n级线性移位存放器序列构成的空间l 定理1：G f 是GF q 上的一个n维线性空间。l 证明：只需证明G f 中的任意两个序列的任意线性组合也属于G f 即可。即证：l 特例：当q=2时，Gf中任意两个序列之和仍然属于Gf。5不可约多项式l 定义：假设存在gx,hx，使得fx=gxhx，则称fx是可约多项式；否则，称其为不可约多项式。不可约多项式6定理2：假设fx|hx，则Gf Gh.l 例1：联结多项式为 fx=x4+x3+x+1=x+12x2+x+1l 线性递推式：at=at-4+at-3+at-1l 输出序列：000111

3、/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级线性反响移存器的最长周期:，能到达最长周

4、期的线性移存器序列称为m序列。在密码学中，我们希望参与变换的序列周期越长越好，因此对线性反响移存器我们更感兴趣的是能到达最长周期的序列，即m序列。9本原多项式 假设n次多项式fx是不可约多项式且pf=qn-1，则称fx是GFq上的本原多 项 式。以本原多项式为连接多项式产生的非零序列均是m序列。10m序列特性m序列的统计特性1、m序列的“0、1信号的频次规律性质1：r级m序列的一个周期中，1出现 个，0出现 个。11m序列的游程分布规律l 假设干个信号连续出现的现象称游程。对于序列a，称a中形如0110或1001的段为一个1游程或0游程，游程中所含1或0的个数称为该游程的长度，如0110为一个

5、长为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游程。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序列特性二移加特性Lta是左移变换，就

6、是将序列 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：若 是一个r级m序列，那么16习 题一、一个线性移存器如图，1写出该线性移存器的线性递推式。2写出该线性移存器的联接多项式。3写出该线性移存器生成的序列。1 3 4 2二、已知 是

7、6次本原多项式，a是 生成的m序列，（1）a的周期是多少？（2）a在的一个周期内，0、1各出现多少次？（3）a在的一个周期内，游程分布如何？17反响多项式的含义一个r级线性移存器的线性递推式表示为：引进迟延算子D：递推式可改写为：将上式中的D用符号x代替，引入多项式：从而有：那么对于序列a，即：189、静夜四无邻，荒居旧业贫。6月-236月-23Thursday,June 1,202310、雨中黄叶树，灯下白头人。14:15:4014:15:4014:156/1/2023 2:15:40 PM11、以我独沈久，愧君相见频。6月-2314:15:4014:15Jun-2301-Jun-2312、

8、故人江海别，几度隔山川。14:15:4014:15:4014:15Thursday,June 1,202313、乍见翻疑梦，相悲各问年。6月-236月-2314:15:4014:15:40June 1,202314、他乡生白发，旧国见青山。01 六月 20232:15:40 下午14:15:406月-2315、比不了得就不比，得不到的就不要。六月 232:15 下午6月-2314:15June 1,202316、行动出成果，工作出财富。2023/6/1 14:15:4014:15:4001 June 202317、做前，能够环视四周；做时，你只能或者最好沿着以脚为起点的射线向前。2:15:40

9、 下午2:15 下午14:15:406月-239、没有失败，只有暂时停止成功！。6月-236月-23Thursday,June 1,202310、很多事情努力了未必有结果，但是不努力却什么改变也没有。14:15:4014:15:4014:156/1/2023 2:15:40 PM11、成功就是日复一日那一点点小小努力的积累。6月-2314:15:4014:15Jun-2301-Jun-2312、世间成事，不求其绝对圆满，留一份缺乏，可得无限完美。14:15:4014:15:4014:15Thursday,June 1,202313、不知香积寺，数里入云峰。6月-236月-2314:15:401

10、4:15:40June 1,202314、意志坚强的人能把世界放在手中像泥块一样任意揉捏。01 六月 20232:15:40 下午14:15:406月-2315、楚塞三湘接，荆门九派通。六月 232:15 下午6月-2314:15June 1,202316、少年十五二十时，步行夺得胡马骑。2023/6/1 14:15:4014:15:4001 June 202317、空山新雨后，天气晚来秋。2:15:40 下午2:15 下午14:15:406月-239、杨柳散和风，青山澹吾虑。6月-236月-23Thursday,June 1,202310、阅读一切好书如同和过去最杰出的人谈话。14:15:4

11、014:15:4014:156/1/2023 2:15:40 PM11、越是没有本领的就越加自命非凡。6月-2314:15:4014:15Jun-2301-Jun-2312、越是无能的人，越喜欢挑剔别人的错儿。14:15:4014:15:4014:15Thursday,June 1,202313、知人者智，自知者明。胜人者有力，自胜者强。6月-236月-2314:15:4014:15:40June 1,202314、意志坚强的人能把世界放在手中像泥块一样任意揉捏。01 六月 20232:15:40 下午14:15:406月-2315、最具挑战性的挑战莫过于提升自我。六月 232:15 下午6月

12、-2314:15June 1,202316、业余生活要有意义，不要越轨。2023/6/1 14:15:4014:15:4001 June 202317、一个人即使已登上顶峰，也仍要自强不息。2:15:40 下午2:15 下午14:15:406月-23 MOMODA POWERPOINTLorem ipsum dolor sit amet,consectetur adipiscing elit.Fusce id urna blandit,eleifend nulla ac,fringilla purus.Nulla iaculis tempor felis ut cursus.感 谢 您 的 下 载 观 看专家告诉