流密码复杂性研究

论文摘要

在信息时代的今天,随着通信技术和网络技术的高速发展和广泛应用,越来越多的信息在网络上传输,信息的安全与保护显得愈发重要。密码学理论与技术也逐渐成为信息科学与技术中的一个重要研究领域。流密码是现代密码学中的一个重要的研究分支,并且随着移位寄存器理论的飞速发展,加上有效的数学工具,使得流密码理论得到了长足的发展。本文主要研究基于反馈移位寄存器的流密码安全性的重要度量指标—线性复杂度、k-错线性复杂度和周期,得到如下主要结果:首先,本文对基于反馈移位寄存器的二进周期序列的非线性复杂度进行分析,考虑了对给定非线性复杂度的值的二进周期序列的设计,并通过计算机搜索给出了一些具有最小非线性复杂度的二进周期序列的形式。此外还给出一类特殊的序列的非线性复杂度和线性复杂度;其次,对基于线性反馈移位寄存器的周期序列的线性复杂度进行分析,阅读了目前的周期序列的线性复杂度的一些快速算法。在此基础上,提出了Fp上满足条件gcd（u , p ） = 1的周期为upv的序列S = ( S1 , S2,Supv-1∞的线性复杂度的快速算法,并且给出如何将周期为upv的序列的线性复杂度的计算转化为周期为pv的序列的线性复杂度的计算的详细方法。由于本算法中u个周期为pv的序列的线性复杂度的计算可以利用并行算法,因此大大降低了Fp上周期为upv的序列的线性复杂度的计算。最后,利用将周期N = upv的序列S的线性复杂度转化为u个周期为pv的子序列的线性复杂度的思想,得到了序列S的线性复杂度和k错线性复杂度的关系,并给出了周期为pv的序列的k错线性复杂度严格小于线性复杂度的一个充要条件。

论文目录

• 摘要
• ABSTRACT
• 符号说明
• 引言
• 1 流密码体制
• 1.1 流密码的定义
• 1.2 流密码的分类
• 1.3 密钥流生成器的设计准则
• 1.4 移位寄存器
• 1.5 线性反馈移位寄存器
• 2 二进周期序列的复杂度分析
• 2.1 周期序列的线性复杂度和极小多项式
• N的复杂度'>2.2 周期序列S^N的复杂度
• 2.3 一类特殊序列的复杂性分析
• 2.4 结论
• 3 周期序列线性复杂度的快速算法
• 3.1 有限域中的主要结果
• 3.2 Berlekamp-Massey 算法（简称B-M 算法）
• 3.3 Games-Chan 算法及其推广算法
• 3.4 Xiao-Wei-Lam-Imamura 算法
• p上的周期为up^v的序列线性复杂度的快速算法'>3.5 F_p上的周期为up^v的序列线性复杂度的快速算法
• 3.6 结论
• p^m上周期为up^v 的序列S 的线性复杂度与k 错复杂度的关系'>4 F_p^m上周期为up^v 的序列S 的线性复杂度与k 错复杂度的关系
• 4.1 k 错复杂度的定义和背景
• p^m上周期为up^v 的序列S 的线性复杂度与k 错复杂度的关系'>4.2 F_p^m上周期为up^v 的序列S 的线性复杂度与k 错复杂度的关系
• 4.3 结论
• 参考文献
• 附录
• 致谢
• 攻读学位期间发表的学术论文目录