上n级线性反馈移位寄存器的一般结构-read.pptVIP

第4章对称密钥密码体制—流密码 流密码 一段待加密的消息明文被分成连续的符号 ，加密通过密钥流 以 的方式进行。其中， 是密钥流中的第i个元素 对消息明文中的第i个元素 进行加密所得的密文。 流密码的时变性 时变性：随时间而变化。 流密码内部状态随时间变化，通过加密器和解密器中的记忆元件得以保证； 密钥流中的元素的产生由i时刻的流密码内部状态（记作 ）和种子密钥（记作k）决定 ，即 ； 加密变换 与解密变换 也和i时刻的流密码内部状态有关。 流密码分类 用状态转移函数 描述流密码加密器中存储器的状态随时间变化的过程。 同步流密码 ：如果某个流密码中的状态转移函数 不依赖被输入加密器存储器的明文； 自同步流密码 ：状态转移函数 与输入明文有关。 同步流密码 同步流密码 两种基本工作方式： 输出-分组反馈模式（简称OFM）； 计数模式。 输出-分组反馈模式工作原理 计数模式工作原理 密码反馈模式工作原理 密钥流生成器 两部分功能： 驱动部分：负责控制存储器的状态并提供周期长、统计特性好的序列供非线性组合部分使用； 非线性组合部分：对这些序列进行非线性组合，以便得到理想的密钥流 。 反馈移位寄存器 两部分组成 ： 移位寄存器：移位寄存器是一个位序列（长度为n的移位寄存器被称为n位移位寄存器），新的最左端的位由其余各位计算得到，通过所有各位右移一位输出的结果通常为最低有效位； 反馈函数。 最简单的反馈移位寄存器 ：线性反馈移位寄存器（LFSR）。 上n级线性反馈移位寄存器的一般结构 反馈函数 LFSR的联结多项式 LFSR的特征多项式 其中， 为 的互反多项式。 LFSR的周期 对于 上的半无限序列 ，若存在正整数T和非正整数 满足：对于所有的 ， 均成立， 则称该序列为终归周期序列，称T为该序列的一个周期，称所有可能周期中的最小值为该序列的最小周期（记为 ）。若 ，则称该序列为周期序列。若 为 的最小终归周期，则称满足 对所有 成立的最小 为预周期。 我们称 上周期为 的n级LFSR序列a为n级最大LFSR序列（又称最长LFSR序列），简称m序列 。 针对LFSR考虑的主要问题 问题一：怎样利用级数尽可能小的LFSR来生成周期长、统计特性好的序列？ 问题二：如何在已知一个序列的情况下，构造能够生成该序列的级数尽可能小的LFSR ？ 问题一 定理： 设 上n级LFSR的联结多项式为 ，该LFSR生成的全部序列记为 ， 中所有非零序列全部为n级m序列的充分必要条件是： 为 上的n次本原多项式 。 上的m序列具有伪随机特性，具有周期长、统计特性与随机序列类似等优点。 问题二 解决的方法是著名的B-M算法。 B-M算法是一个多项式时间迭代算法。该算法有效解决了线性移位寄存器的综合问题（即问题二）。 B-M算法使序列的线性复杂度成为评价同步流密码强度的一个重要指标。 B-M算法 采用递归方法求出一系列移位寄存器 （其中， ，N为二元序列 的长度），而每一个 都是生成 的级数最小的线性反馈移位寄存器。 时间和空间复杂度分别为 和 。 B-M算法描述 （1）输入：N；二元序列 ： 。 （2）初始化： ， 。 （3）计算延迟算子 ： 若 ，则 ，转（4）； 若 且 ，则： ，转(4）； 若 且