第4讲序列密码pt课件_第1页
第4讲序列密码pt课件_第2页
第4讲序列密码pt课件_第3页
第4讲序列密码pt课件_第4页
第4讲序列密码pt课件_第5页
已阅读5页,还剩13页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、3x44非退化的移位寄存器非退化的移位寄存器 若反馈函数形如:若反馈函数形如: ,其中,其中 ,则称其为,则称其为线性反馈寄存线性反馈寄存器器;否则称其为;否则称其为非线性反馈移为寄存器非线性反馈移为寄存器。 其中其中 ,若,若 我们说该寄存器是我们说该寄存器是退化退化的,的,否则是否则是非退化的非退化的。( ),1icgf qin 1211 21( , , , )nnnnf x xxcx c xcx 0nc 0nc 5移位寄存器序列空间移位寄存器序列空间l符号说明:g(f)表示以f(x)为联结多项式的n级线性移位寄存器序列构成的空间l定理1:g(f)是gf(q)上的一个n维线性空间。l证明:

3、只需证明g(f)中的任意两个序列的任意线性组合也属于g(f)即可。即证: l特例:当q=2时,g(f)中任意两个序列之和仍然属于g(f)。)(,),(),(),(qgffgbafgbfga6(不)可约多项式l定义:若存在g(x),h(x),使得f(x)=g(x)h(x),则称f(x)是可约多项式;否则,称其为不可约多项式。(不不)可约多项式可约多项式7定理定理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

4、011/011/ 周期为3 001/001/ 周期为3 01/01/ 周期为2 111111. 周期为1 000000 周期为18极小多项式极小多项式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+19序列和周期序列和周期一般地,一个移存器序列表示为: 对于序列 ,若存在整数p使得对任意正整数k有 成立,称满足该式的最小正整数p为序列的周期序列的周期。lr级线性反馈移存器的

5、最长周期: ,能达到最长周期的线性移存器序列称为m序列序列。 在密码学中,我们希望参与变换的序列周期越在密码学中,我们希望参与变换的序列周期越长越好,因此对线性反馈移存器我们更感兴趣长越好,因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列,即的是能达到最长周期的序列,即m序列。序列。iaaaaa210iaaaaa210pkkaa12 r10本原多项式本原多项式 若n次多项式f(x)是不可约多项式且p(f)=qn-1,则称f(x)是gf(q)上的本原多项式。 以本原多项式为连接多项式产生的非零序列均是m序列。11m序列特性序列特性m序列的统计特性序列的统计特性1、 m序列的序列的“0、1

6、”信号的频次规律信号的频次规律性质性质1 1 :r级m序列的一个周期中,1出现 个, 0出现 个。12r121r12m序列的游程分布规律序列的游程分布规律l若干个信号连续出现的现象称游程游程。对于序列a,称a中形如0110或1001的段为一个1游游程或程或0游程游程,游程中所含1或0的个数称为该游程的长度,如0110为一个长为2的1游程,101为一个长为1的0游程。13m序列的游程分布规律序列的游程分布规律性质性质2 2:将r级m序列的一个周期段首尾相接,其游程总数为n=2r-1;其中没有长度大于r的游程;有1个长度为r的1游程,没有长度为r的0游程;没有长度为 r-1的1游程,有1个长度为r

7、-1的0游程;有 个长度为 的1游程,有 个长度 为 的0游程。)21 (rkkkr22kr22)21 (rkk14二、二、m序列特性序列特性(一)统计特性(一)统计特性1、“0、1”信号频次 性质性质1 :r级m序列的一个周期中,1出现 个, 0出现 个。12r121r2、游程分布性质性质2:在r级m序列的一个周期中,有1个长度为r的1游程和1个长度为r-1的0游程;长度为 的1游程和0游程各有 个。)21 (rkkkr2215二、二、m序列特性序列特性(二)移加特性(二)移加特性l(t)(a)是左移变换,就是将序列 a 左移t位所得 到的序列。性质性质3:若 是由r级本原线性移存器产生的m

8、序列, 则 是与 平移等价的m序列。aa) 12mod0()()(rttala性质性质4:周期为p的m序列 ,左移t 位得到序列 ,将 与 按位对齐。则在一个周期段中,序列 与序列 (0,0)的有(p-3)/4对,(1,1)、(1、0)、(0、1)的各有(p+1)/4对。aaabbb) 12mod0(rt16二、二、m序列特性序列特性(三)自相关特性(三)自相关特性 若 是一个周期为p的0、1序列,定义0 1上的映射为: ,定义 序列 的自相关函数为)(210aaaa 1) 1 (, 1)0()()()(10tipiiaatc)(210aaaa 性质性质5 5:若 是一个r级m序列,那么120, 10, 12)()()(220rrtiiittaatcr)(210aaaa 17习 题一、一个线性移存器如图,(1)写出该线性移存器的线性递推式。(2)写出该线性移存器的联接多项式。(3)写出该线性移存器生成的序列。1342二、已知 是6次本原多项式,a是 生成的m序列,(1) a的周期是多少?(2) a在的一个周期内,0、1各出现多少次?(3) a在的一个周期内,游程分布如何?1)(6xxxf)(xf18反馈多项式的含义反馈多项式的含义一个r级线性移存器的线性递推式表示为:)(2211rnacacacarnrnnn引进迟延算子d:

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论