（推荐）6-m序列特性

1、密码学密码学课程多媒体课件课程多媒体课件 移位寄存器基础移位寄存器基础 m序列特性序列特性 序列密码编码技术序列密码编码技术 前馈函数设计准则前馈函数设计准则 快速相关攻击快速相关攻击 第三章第三章 序列密码序列密码 密码学密码学课程多媒体课件课程多媒体课件 n主要内容：主要内容：随机性的描述、随机性的描述、m序列特性序列特性 n重点：重点：m序列特性序列特性 n难点：难点：m序列的采样特性序列的采样特性 m序列特性序列特性 密码学密码学课程多媒体课件课程多媒体课件 一、随机性的描述一、随机性的描述 1、Golomb随机性假设随机性假设 为了度量周期序列的随机性，为了度量周期序列的随机性，Go

2、lomb提出了下提出了下 列三条标准：列三条标准： （1）一个周期中）一个周期中0、1的个数相差不超过的个数相差不超过1个；个； （2）一个周期段中，长度为）一个周期段中，长度为i的游程占游程总数的的游程占游程总数的 这里假定至少有两个长为这里假定至少有两个长为i的游程；的游程； （3）周期自相关函数是二值函数。）周期自相关函数是二值函数。 i 2/1 密码学密码学课程多媒体课件课程多媒体课件 二、二、m序列特性序列特性 （一）统计特性（一）统计特性 1 1、“0 0、1 1”信号频次信号频次 性质性质1 ：r级级m序列的一个周期中，序列的一个周期中，1出现出现 个，个， 0出现出现 个。个。

3、 1 2 r 12 1 r 密码学密码学课程多媒体课件课程多媒体课件 132 0 0 10 0 1 0 0 10 0 1 1 0 01 0 0 1 1 01 1 0 1 1 11 1 1 0 1 10 1 1 1 0 11 0 1 0 1 00 1 0 产生序列为：产生序列为：1001110 密码学密码学课程多媒体课件课程多媒体课件 2、游程分布、游程分布 性质性质2：在在r级级m序列的一个周期中，序列的一个周期中， （1）长度为）长度为r的的1游程有游程有1个；个； （2）长度为）长度为r-1的的0游程有游程有1个；个； （3）长度为）长度为 的的0、1游程各有游程各有 个；个； （4）游程

4、总数为）游程总数为 个，且个，且0、1游程各占一半。游程各占一半。 )21 (rkk kr2 2 1 2 r 密码学密码学课程多媒体课件课程多媒体课件 132 0 0 10 0 1 0 0 10 0 1 1 0 01 0 0 1 1 01 1 0 1 1 11 1 1 0 1 10 1 1 1 0 11 0 1 0 1 00 1 0 产生序列为：产生序列为：1001110 密码学密码学课程多媒体课件课程多媒体课件 （二）移加特性（二）移加特性 性质性质3：若若 是由是由r级本原线性移存器产生的级本原线性移存器产生的m序列序列, 则则 是与是与 平移等价的平移等价的m序列。序列。 a a) 12

5、mod0()( )( rt taLa 注：注：其中其中L(t)(a)表示序列表示序列a左移左移t位所得序列。位所得序列。 密码学密码学课程多媒体课件课程多媒体课件 132 0 0 10 0 1 0 0 10 0 1 1 0 01 0 0 1 1 01 1 0 1 1 11 1 1 0 1 10 1 1 1 0 11 0 1 0 1 00 1 0 产生序列为：产生序列为：10011101001110 密码学密码学课程多媒体课件课程多媒体课件 性质性质4：周期为周期为p的的m序列序列a，左移，左移 t 位位 得到序列得到序列b，将，将a与与 b按位对齐，按位对齐， 则在一个周期段中，序列则在一个周

6、期段中，序列a与序列与序列b （0，0）的对有）的对有(p-3)/4对；对； （1，1）的对有）的对有(p+1)/4对；对； （1、0）的对有）的对有(p+1)/4对；对； （0、1）的对有）的对有(p+1)/4对。对。 ) 12mod0( r t 密码学密码学课程多媒体课件课程多媒体课件 （三）自相关特性（三）自相关特性 若若 是一个周期为是一个周期为p的的0 0、1 1序列，序列， 定义定义0 10 1上的映射上的映射为：为： ，定义序，定义序 列列 的自相关函数为的自相关函数为 )( 210 aaaa 1) 1 (, 1)0( )()()( 1 0 ti p i i aatC )( 21

7、0 aaaa 性质性质5：若若 是一个是一个r级级m序列，那么序列，那么 120, 1 0, 12 )()()( 22 0 r r ti i i t t aatC r )( 210 aaaa 密码学密码学课程多媒体课件课程多媒体课件 （四）（四）m序列的采样特性序列的采样特性 为序列为序列a的以的以t为起点的为起点的k采样序列，并称采样序列，并称k为采为采 样距。样距。 设设 是周期为是周期为2n1的的m序列，序列，k为正整为正整 数，数，t为非负整数，则称序列为非负整数，则称序列 0 ii aa ( , ) 0 k t ik ti aa 密码学密码学课程多媒体课件课程多媒体课件 定理：定理：

8、设设a是周期为是周期为2n1的的m序列，序列，k为正整数。则为正整数。则 (1) 当当gcd(k,2n1)1时，序列时，序列a的的k采样序列都是周采样序列都是周 期为期为2n1的的m序列序列; (2) 当存在非负整数当存在非负整数d：0dn,使使k2d时，序列时，序列a的的k 采样序列都与序列采样序列都与序列a平移等价。平移等价。 (3) 当当gcd(k,2n1)1时，序列时，序列a的的k采样序列仍是线采样序列仍是线 性递归序列，但周期可能性递归序列，但周期可能2n1。 推论：推论：利用采样方法可采出所有的利用采样方法可采出所有的n次本原多项式次本原多项式, 共共 个。个。 (21)/ n n

9、 密码学密码学课程多媒体课件课程多媒体课件 132 0 0 10 0 1 0 0 10 0 1 1 0 01 0 0 1 1 01 1 0 1 1 11 1 1 0 1 10 1 1 1 0 11 0 1 0 1 00 1 0 产生序列为：产生序列为：10011101001110 密码学密码学课程多媒体课件课程多媒体课件 三、线性移存器综合三、线性移存器综合 一条线性递归序列由一条线性递归序列由: : (1) (1) 线性递推式线性递推式( (包括级数包括级数n)n); (2) (2) 初始信号初始信号 两个因素决定。两个因素决定。 这两个因素都可设置为密钥的一部分。这两个因素都可设置为密钥的

10、一部分。 因此因此, ,m序列的还原问题就是在已知序列的还原问题就是在已知m序列或仅序列或仅 已知其部分信号的条件下已知其部分信号的条件下, ,求解未知因素的问题。求解未知因素的问题。 密码学密码学课程多媒体课件课程多媒体课件 （一）解方程法（一）解方程法 已知序列已知序列a是由是由r级线性移存器产生的，且知级线性移存器产生的，且知a 的连续的连续2 2r位，可用解线性方程组的方法得到线性递位，可用解线性方程组的方法得到线性递 推式。推式。 密码学密码学课程多媒体课件课程多媒体课件 例：设例：设a=01111000=01111000是是4 4级线性移存器产生的序列的级线性移存器产生的序列的8 8 个连续信号，求该移存器的线性递推式。个连续信号，求该移存器的线性递推式。 分析：序列信号必满足递推式所确定的关系，要得到分析：序列信号必满足递推式所确