密码学教程 课件 -2-序列密码

第二章序列密码

2．1概述

2．2线性反馈移位寄存器

2．3m序列及其性质2．4对偶移位寄存器2．5

B-M算法2．6非线性组合与算法举例

2.1概述序列密码将明文编码为比特串:

同时产生与明文相同长度的密钥流:

或者GF(p)效仿一次一密加密方式：

（1）密钥和明文长度相同；

（2）每次加密采用不同的密钥；

（3）密钥是随机的。古典密码中的

Vernam密码（1917年）：

但密钥如何实现？伪随机数发生器：产生性能接近随机的二进制序列。种子密钥序列密码主要任务：设计安全的伪随机密钥产生器。对KG（KeyGenerator）的基本要求：（1）密钥量大；（2）极大周期；（3）理想分布；（4）非线性度大；（5）推测K是计算不可行的。KG非线性移位寄存器（NFSR：Non-linearFeedbackShiftRegister）

－－－－M序列（周期最大）线性反馈移位寄存器（LFSR：Linear

FeedbackShiftRegister）

－－－－m序列（周期最大）线性移位寄存器的非线性组合（实用的）序列密码与分组密码的比较：（1）序列密码：

处理速度快，实时性好；

适用于军事、外交等保密系统。

但是适应性差，需要密钥同步。（2）分组密码：

不需密钥同步，较强的适应性；适宜作为加密标准。

但是加密速度稍慢，错误易扩散和传播。

(但比公钥密码快得多，软件上约100倍。)2．2线性反馈移位寄存器1.反馈移位寄存器KG！

例题-1：初始状态：s0＝101f10110111111011011011移位寄存器的一个状态（开始时为初始状态）：反馈函数

反馈寄存器的状态序列：必然是周期的！因为状态有限，进入一个相同状态后则重复。当触发脉冲到来时，寄存器状态移位更新为一个新状态。

例题-1的输出序列：10111011…..完整的状态图：如何使状态都在一个圈里？这样周期最大。2.线性移位寄存器-LFSR(Fibonacci-LFSRs)反馈函数为线性函数（否则为非线性反馈移位寄存器）

称为结构常数。

结构常数反序是为了将来有理表示方便（不必求互反多项式）。例题-2：

这是一个4阶线性反馈移位寄存器：4-LFSR。

布尔函数！f110001000011000110001101111010110100001000

初始状态记为：

最重要的关系！结构常数不动

可以划出相应的状态转移图。

图形和公式是对应的

上例中：反馈函数为,

初始状态:(1000)，输出序列:(1000110)

，周期为7初始状态:(0010)，输出序列:(0010111)

，周期为7

初始状态:(0110)，输出序列:(0110100)

，周期为7

第三个初态！第一个初态！第二个初态！

反馈函数为：初始状态:(1000)，输出序列:(100010011010111)

，周期为

初始状态:(0110)，输出序列:(011010111100010)

，周期为

的序列称为n阶m序列。另一：f110001000010000100001001110011000110001101111010f111010110101001011110111001111111110111100111000110001续前：第二个初态！第一个初态！只要进入，就得循环！

结论：（1）n-LFSR的结构由其结构常数唯一确定；（2）n-LFSR的结构常数与反馈函数互相唯一确定；（3）n-LFSR序列由其结构常数和初态唯一确定；（4）一个n-LFSR可以产生个不同序列；（5）一个n-LFSR的序列的最大周期是。关键问题：如何产生m序列？LFSR的联接多项式为本原多项式。f(x)称为线性移位寄存器的联接多项式或生成多项式。

3.LFSR的有理表示

a(x)称为序列的形式幂级数或生成函数。--S(f(x))LFSR的有理表示：其中g(x)是次数小于n的多项式：a(x):表示输出序列f(x)：表示结构常数g(x)：与初态、结构常数相关

序列空间定理-1：n-LFSR有理表示中g(x)的次数小于n。证明：因为迭代关系：

LFSR:g(x)的系数和结构常数与初态都有关系。DSR

：g(x)的系数就是初态。（后面讲）

当初结构常数序号与寄存器序号反向，就是为了此处。

另一简单方法求g(x)：

消最低项的长除法可求a(x)：2.3、m序列及其性质1.如何构造m序列例题-4：

设的有理表示为，求其序列表示。解：通过消最低项的多项式除法，得到：

升幂排列消最低项另一种方法：定理-2：周期为p的序列的（非最简）有理表示为：证明：

所以：分子多项式的系数（含常数项）为一个周期；分母二项式的次数为周期。

例题-5：求产生序列（100111）∞的最短的LFSR。

多项式的辗转相除法阶数最少！最简有理表示

任何一个（周期）序列都可以表示为：

此即研究多项式形式的原因

定理-3：当f(x)为本原多项式，产生的序列为m序列。

nFeedbackpolynomialPeriod23374155316637127不止一个！是一个本原多项式。初态为(10101)，求序列的表示。例题-6：两种基本方法：（1）画出结构图，进行迭代，得到状态图。（2）求出有理表示，进行长除法，得到一个周期。（1010111011000111110011010010000）∞设一个序列的联接多项式为

随机性如何？m序列的取样:设

是Fq上的一个周期序列s

是一个正整数，令：称为序列的s采样。定理-4：若是周期为p的m序列，则

2.m序列的伪随机性形如的子序列段称为一个长为k的1游程；形如的子序列段称为一个长为k的0游程。

（1）分布特性：（2）相关特性：随机性的三个特性：s是序列的长度

（3）游程特性：0游程

证明：将游程数目转化为状态的数目。

状态最终都会出现在序列中！一个周期序列圈m序列特点：每个非零状态都出现，且只

出现一次！状态都在序列中！

序列圈中，长为i的1游程总会体现为：存在以下形式的状态(一一对应！)在序列圈上数游程个数，都是从011…10开始。即使在******中也有，以后也会被数到，没有遗漏。输出序列的圈

看序列图上的状态，游程最终要显示在序列圈上。输出序列的圈所以当游程个数为现在只剩下的游程个数：n长的1游程有1个，

因为在状态圈中，有一个全1状态：111….1；没有n长的0游程，因为没有全0状态；n-1长的0游程有1个；所以共有游程：不可能有n+1的1游程：不会有n-1长的1游程：因为不可能有两个全1状态，且相连；因为以下三个状态是相连的：（否则全1状态不会出现。）且每个状态在状态圈中，只出现一次；所以011..11与11..110不会连着出现（连着才会出现n-1长的1游程）。m序列特点：一个周期内,每个非零状态都出现，且只

出现一次！（3）相关系数的证明:

任意5级m序列的周期环上，有个0，有16个1。

＝1111100110’1001000010’1011101100’0……，是由本原多项式产生，所以是5级m序列。其周期中，15个0，16个1。游程总数：长为1的1/0游程：长为2的1/0游程：长为3的1/0游程：长为4的0游程一个，长为5的1游程一个。算游程时首尾相接例题-7：

LFSR（DSR:DualShiftRegisters）DSR2．4对偶移位寄存器LFSR：也称FibonacciLFSRsDSR：也称GaloisLFSRs

DSR的特点：DSR也是LFSR，这样称呼只是为了区别开1.DSR的状态转换（或称迭代过程）

例题-8：4－DSR

序列为：（1101000）

开始循环11000111010011111110000010001000100状态不是每位都输出初态为（1110）时，序列为（1000110）

相同的联接多项式4-LFSR

但是：如果上例的LFSR的初态是1101，

输出序列为：（1101000）

，

与初态为1000的DSR输出序列相同。因此相同的结构常数，DSR和LFSR可产生相同序列。2.DSR的有理表示a(x):表示输出序列f(x)：表示结构常数g(x)：表示初态！DSR也具有有理表示：一方面：利用DSR的递推公式所以输出序列为

定理-6：DSR序列的有理表示中：证明：其系数就是DSR的初态：另一方面：利用消最低项方法有理表示等式的两边相同，得证。

由此可得到DSR的设计思路

例题-9：解：（1）LFSR的结构常数为（0,1,0,1）

初态为（0,1,0,0）。（2）DSR的结构常数为(0,1,0,1)，结构图即

或者：所以DSR和LFSR是等效的。

总结：4.当链接多项式f(x)为本原多项式时，产生m序列。

2.对于LFSR，g(x)的系数由初态和结构常数确定；

对于DSR，g(x)的系数即为初态；产生同一序列（具有相同有理表示），LFSR和DSR

的初态不同；另外：有理表示还可以扩展为假分式的情况，例如：

对应的LFSR的图示为：(退化的7-LFSR)

非周期部分的位数有3位，对应的退化寄存器个数为3。线性复杂度：生成序列所需最小的LFSR寄存器个数。本例中，序列的线性复杂度=4+3。2.5B-M算法线性反馈移位寄存器虽然易于实现，但是不安全的，如果知道两个周期，就能通过B-M算法解出生成多项式。已知阶数B-M算法不需任何前提，求出序列段的线性综合解：是一种迭代算法：阶数对于n阶线性移位寄存器，已知2n序列段，通过解方程组，可以求得对应的结构常数还可用于循环码译码等。还有Berlekamp算法：用于分解多项式。B-M（Berlekamp–Massey）算法：

迭代型求解序列生成多项式的算法。（且不必事先知道寄存器阶数）未知阶数规定：f(x)=1表示0阶线性移位寄存器的联接多项式，（长度为n的全零序列由0阶线性移位寄存器产生。）

且记计算对于，重复第二步和第三步N次，即可求出若（a）如果（b）否则，存在（3）若，取逐次试验联接多项式的方法！输出：<1+x3+x4,4>同一行中最后才算dn！d=1才算m！写在fn+1的上一行例10：输入S8=10101111

当前结构常数：当前状态

逐一试验上题的解释：（上述过程熟练以后，仅用表格形式做即可！）

例题-11：输入：S10=0001101111

注意：