6,m序列特性

《密码学》课程多媒体课件移位寄存器基础m序列特性序列密码编码技术前馈函数设计准则快速相关攻击第三章序列密码《密码学》课程多媒体课件主要内容：随机性的描述、m序列特性重点：m序列特性难点：m序列的采样特性m序列特性《密码学》课程多媒体课件一、随机性的描述1、Golomb随机性假设为了度量周期序列的随机性，Golomb提出了下列三条标准：（1）一个周期中0、1的个数相差不超过1个；（2）一个周期段中，长度为i的游程占游程总数的这里假定至少有两个长为i的游程；（3）周期自相关函数是二值函数。i2/1《密码学》课程多媒体课件二、m序列特性（一）统计特性1、“0、1”信号频次性质1：r级m序列的一个周期中，1出现个，0出现个。12r121r《密码学》课程多媒体课件132001001100110111011101010产生序列为：1001110……《密码学》课程多媒体课件2、游程分布性质2：在r级m序列的一个周期中，（1）长度为r的1游程有1个；（2）长度为r-1的0游程有1个；（3）长度为的0、1游程各有个；（4）游程总数为个，且0、1游程各占一半。)21(rkkkr2212r《密码学》课程多媒体课件132001001100110111011101010产生序列为：1001110……《密码学》课程多媒体课件（二）移加特性性质3：若是由r级本原线性移存器产生的m序列,则是与平移等价的m序列。aa)12mod0()()(rttaLa注：其中L(t)(a)表示序列a左移t位所得序列。《密码学》课程多媒体课件132001001100110111011101010产生序列为：10011101001110……《密码学》课程多媒体课件性质4：周期为p的m序列a，左移t位得到序列b，将a与b按位对齐，则在一个周期段中，序列a与序列b（0，0）的对有(p-3)/4对；（1，1）的对有(p+1)/4对；（1、0）的对有(p+1)/4对；（0、1）的对有(p+1)/4对。)12mod0(rt《密码学》课程多媒体课件（三）自相关特性若是一个周期为p的0、1序列，定义{01}上的映射η为：，定义序列的自相关函数为)(210aaaa1)1(,1)0()()()(10tipiiaatC)(210aaaa性质5：若是一个r级m序列，那么120,10,12)()()(220rrtiiittaatCr)(210aaaa《密码学》课程多媒体课件（四）m序列的采样特性为序列a的以t为起点的k采样序列，并称k为采样距。设是周期为2n－1的m序列，k为正整数，t为非负整数，则称序列0{}iiaa(,)0{}ktiktiaa《密码学》课程多媒体课件定理：设a是周期为2n－1的m序列，k为正整数。则(1)当gcd(k,2n－1)＝1时，序列a的k采样序列都是周期为2n－1的m序列;(2)当存在非负整数d：0≤d≤n,使k＝2d时，序列a的k采样序列都与序列a平移等价。(3)当gcd(k,2n－1)≠1时，序列a的k采样序列仍是线性递归序列，但周期可能2n－1。推论：利用采样方法可采出所有的n次本原多项式,共个。(21)/nn《密码学》课程多媒体课件132001001100110111011101010产生序列为：10011101001110……《密码学》课程多媒体课件三、线性移存器综合一条线性递归序列由:(1)线性递推式(包括级数n);(2)初始信号两个因素决定。这两个因素都可设置为密钥的一部分。因此,m序列的还原问题就是在已知m序列或仅已知其部分信号的条件下,求解未知因素的问题。《密码学》课程多媒体课件（一）解方程法已知序列a是由r级线性移存器产生的，且知a的连续2r位，可用解线性方程组的方法得到线性递推式。《密码学》课程多媒体课件例：设a=01111000是4级线性移存器产生的序列的8个连续信号，求该移存器的线性递推式。分析：序列信号必满足递推式所确定的关系，要得到4级移存器的递推式，只须确定4个系数即可，利用已知的8个信号，恰好得到4个方程，解方程组即可求解。《密码学》课程多媒体课件习题教材Ｐ140页,第5题、第6题