伪随机序列的设计与分析研究

论文摘要

本文首先应用错误攻击对两种流密码体制：广义自缩生成器和均衡互缩生成器的安全性进行了分析，为抵抗这种攻击，我们对广义自缩生成器进行了改进，给出了一种新型的广义自缩生成器，并对该生成器的各种伪随机性进行了分析，最后讨论了自相关函数和线性复杂度之间的一个关系，得到如下主要结果： ● 利用错误攻击对广义自缩生成器和均衡互缩生成器这两种流密码体制进行了密码分析，结果表明：对于由60级的线性反馈移位寄存器构成的广义自缩生成器，在反馈多项式已知的条件下，攻击者仅需要4个错误密钥流，结合平均约28个密钥流比特就可以获得生成器的密钥种子；对于均衡互缩生成器，攻击者可以通过改变LFSR若干个时钟来得到错误的输出流，并利用这些输出流得到生成器的密钥种子。 ● 为抵抗错误攻击，设计了一类新型的广义自缩生成器。讨论了该新型序列的各种伪随机性质，包括最小周期，游程长度和序列族的性质，给出了使最小周期达到最大的方法。由我们的方法可以找到2n-3个周期达到2n-1的序列。同时证明序列的最大游程长度不超过n2-2.5n+3。 ● 讨论了新型广义自缩生成器的安全性，主要讨论了新型生成器抵抗猜测攻击和相关攻击的能力。关于安全性得到如下结论：当攻击者已知生成器的一个密钥向量G时，攻击的复杂度为O(12n420.694n)；当攻击者不知道密钥向量G但已知集合C1={01，10}时，攻击者可以得到序列的一个相关弱点，利用该弱点可以攻击新型广义自缩序列，但当集合C1发生变化时，该弱点不存在。 ● 研究了新型广义自缩序列线性复杂度的稳定性：当改变序列的奇数个比特时，序列的线性复杂度会增加到最大，即等于序列的最小周期2n-1；在改变序列偶数个比特且满足一定条件时，序列的线性复杂度会下降，其余情况下，序列的线性复杂度不会下降。 ● 首次指出周期为2n的伪随机序列的自相关函数和线性复杂度之间存在的一个关系，并讨论了该关系在以下三个方面的应用：1)由序列的线性复杂度来估计／确定序列的自相关函数值；2)通过序列的自相关函数来证明Games-Chan算法；3)由序列的线性复杂度来检验一个序列族的互相关函数值。 ● 针对一类周期为2n的伪随机序列，指出这类序列的自相关函数值和线性复杂度以及k错线性复杂度存在着关系，即该类序列的自相关函数可以同国线性复杂度和k-错线性复杂度来衡量。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 伪随机序列的研究现状
• 1.2 伪随机指标
• 1.3 本文的主要研究内容和结构安排
• 第二章 对两种流密码的错误攻击
• 2.1 对广义自缩生成器的错误攻击
• 2.1.1 广义自缩生成器
• 2.1.2 攻击方法的基本假设
• 2.1.3 具体的攻击方法
• 2.1.4 一个简单的例子
• 2.2 对均衡互缩生成器的错误攻击
• 2.2.1 互缩生成器和均衡互缩生成器
• 2.2.2 对均衡互缩生成器的错误攻击
• 2.2.3 一个简单的例子
• 2.3 小结
• 第三章 新型广义自缩生成器
• 3.1 新型广义自缩生成器的定义和序列族的性质
• 3.2 新型广义自缩序列的最小周期
• 3.2.1 选择向量G的基本思想
• 3.2.2 选择向量G的具体方法
• 3.3 新型广义自缩序列的游程长度
• 3.4 小结
• 第四章 新型广义自缩序列的安全性和稳定性
• 4.1、引言
• 4.2、向量G已知情况下的时钟猜测攻击
• 4.3 向量G未知情况下的相关攻击
• 4.4 新型广义自缩序列线性复杂度的稳定性
• 4.5 小结
• 第五章 自相关函数和线性复杂度的关系
• 5.1 引言
• 5.2 自相关函数和线性复杂度的关系
• 5.3 关系的应用
• 5.3.1 由线性复杂度来估计/确定自相关函数值
• 5.3.2 利用自相关函数证明GAMES-CHAN算法
• 5.3.3 由序列的线性复杂度来检验一个序列族的互相关函数值。
• 5.4 进一步结果
• 5.5 小结
• 结束语
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果