三类向量深度的性质

论文摘要

本文的主要研究对象是流密码学中伪随机周期序列的三类向量深度的性质。流密码的安全性主要由密钥流序列的随机性来决定,序列的线性复杂度是度量序列随机性的一个重要指标。许多学者从序列多项间关系（如:线性移位寄存器）的角度对其进行了深入的研究。Etzion则从序列二项间关系（差分）的角度研究了序列的线性复杂度,开创性地提出了向量深度的概念,认为一个长度为2r的二元向量的深度等于其对应周期序列线性复杂度,并证明了任何一个k维线性码的深度分布有k项。Roth从序列生成多项式的因式角度也研究了序列的线性复杂度,对于长度为2r的二元向量的深度提出了一个与Etzion的深度概念等价的描述。随后,Mitchell指出具有有限深度的无限长二元序列之集等于周期形如2i（i为任意非负整数）的序列之集,并给出了循环码的深度分布。本文的主要工作是将Etzion和Roth提出的向量深度归纳为三类向量深度,并通过向量算子的矩阵描述来研究任意长度向量的深度的性质。第一章到第五章表述流密码体制以及密钥流序列的基础理论。其中在第三章,比较了多篇文献中有关LFSR（线性反馈移位寄存器）的特征多项式、反馈多项式、联接多项式以及极小多项式等概念上的差异,并对计算序列线性复杂度的Massey算法做了较为详细的讨论（参见程序LFSR.C）,为今后进一步的学习打下了一定的基础。第六章在GF（2）上讨论三类向量深度的性质。首先给出了五种向量算子的定义及其矩阵描述,并在此基础上给出了三类向量深度的定义。其次,对于长度为2r的向量,利用向量算子的矩阵描述简洁证明了这一类向量的三类向量深度与其对应周期序列的线性复杂度等价。第三,先讨论所有长为2r-1向量的第三类向量深度分布,然后在Mitchell工作的基础上,给出了F2上任意n维向量空间的第三类向量深度分布的完整结果。并首次研究了第三类向量深度为∞时,序列{（ E ?1） m （ s ）}m≥0的周期。第四,针对长度为2r-1的向量,讨论了第二类向量深度定义的适用范围。第二类深度由Roth提出后,很少再见到相关的讨论。本文利用F2 [ x]上多项式的唯一分解定理,给出了任意n维向量空间的第二类向量深度分布的一个表达形式。最后,讨论了长为2r-1向量的第一类深度与线性复杂度的关系,并给出了一个在此情况下求第一类向量深度的简单算法,作为Etizon算法的补充。第七章在GF（q）上讨论三类向量深度的性质。将GF（2）上的相关讨论在GF（q）上进行了部分推广。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1. 研究背景和研究意义
• 2. 论文的组织结构
• 第二章 流密码体制
• 1. 保密系统的Shannon 模型
• 2. 流密码
• 3. 二元加法流密码
• 第三章 密钥流序列的基础理论
• 1. 序列
• 2. LFSR 的几种多项式
• 3. LFSR 序列的周期
• 4. G（f）的结构及其分解
• 5. 周期序列的几种表示法
• 6. 序列的线性复杂度
• 第四章 M-序列的密码学特性
• 1. M 序列的定义
• 2. M 序列的伪随机性
• 3. M 序列的线性复杂度L
• 第五章 m 序列的密码特性
• 1. m 序列的定义
• 2. m 序列的生成
• 3. m 序列伪随机性
• 4. m 序列的复杂度
• 第六章 GF（2）上三类向量深度的性质
• 1. 三类向量深度的定义
• r时，讨论l₁=l₂=l₃=C（s）'>2. 当n=2^r时，讨论l₁=l₂=l₃=C（s）
• 3深度分布及序列{（E-1）^m（s） }_m≥0 的周期'>3. 任意n 长向量的l₃深度分布及序列{（E-1）^m（s） }_m≥0的周期
• 2深度分布'>4. 讨论l₂深度分布
• r-1 时，给出求l₁深度的一个算法'>5. 当n=2^r-1 时，给出求l₁深度的一个算法
• 第七章 GF（q）上三类向量深度的性质
• 1. 三类向量深度的定义
• r时，l₁=l₂=l₃'>2. 讨论当n=p^r时，l₁=l₂=l₃
• r-1 时，l₁、l₂、l₃的意义'>3. 讨论当n=p^r-1 时，l₁、l₂、l₃的意义
• 总结
• 致谢
• 参考文献
• 攻读学位期间发表的学术论文
• 学位论文答辩决议书