周期序列的K-错线性复杂度分析和研究
Analyse and Research of the k-error Linear Complexity
of Periodic Sequences
作 者 姓 学 位 类 学 科、专 研 究 方 导 师 及 职
名 王菊香 型 学 历 硕 士 业 应 用 数 学 向 代数编码和序列密码 称 朱士信 教授
2009年3月
目录
第一章 绪论 ........................................................ 1
1.1 研究背景 ................................................... 1 1.2 论文研究的内容及主要结果 ................................... 3 第二章 基础知识 .................................................... 5
2.1 密码学基础知识 ............................................. 5 2.2 线性反馈移位寄存器序列 ...................................... 7 第三章 周期单序列及其对偶序列的线性复杂度 ........................... 8
3.1 周期单序列线性复杂度基础知识 ............................... 8 3.2 二元周期单序列及其对偶序列线性复杂度 ....................... 9 3.3 P元周期单序列及其对偶序列线性复杂度 ...................... 10 第四章 2n?周期二元序列的4-错线性复杂度 ........................... 14
4.1 周期单序列k-错线性复杂度基础知识 ......................... 14
n4.2 线性复杂度为2n?1的2?周期二元序列的2-错（或3-错）线性复杂
度 ............................................................. 16
n4.3 线性复杂度为2n?1的2?周期二元序列的4-错（或5-错）线性复杂
度 ............................................................. 16 第五章 周期多序列及其广义对偶多序列的线性复杂度 .................... 22
5.1 周期多序列联合线性复杂度基础知识 ........................... 22 5.2 二元周期多序列及其广义对偶序列的联合线性复杂度 ............. 23 5.3 p元周期多序列及其广义对偶序列的联合线性复杂度 ............ 26 第六章 总结 ........................................................ 30
6.1 论文工作总结 .............................................. 30 6.2 结束寄语 .................................................. 30 参考文献 ........................................... 错误！未定义书签。 本文作者在攻读硕士期间的研究成果 ................... 错误！未定义书签。
第一章 绪论
1.1 研究背景
随着信息化时代的到来，信息安全越来越成为人们关注的焦点。密码技术是保障信息安全的核心技术。密码技术在古代的应用已经有四千多年的历史，但是主要应用于外交通信和军事保护，密码学还没有系统的理论基础。直到1949年Shannon（美国数学家）发表了论文《保密系统的信息理论》[1]，这为单钥密码系统奠定了理论基础，从此，密码才成为一门科学。但是从1949年到1975年这段时间，密码学理论研究工作进展不大。一直到70年代中期，在密码学的研究中出现了两件非常重要的事件:一件事是1976年Diffie和Hellman (美国学者)发表了《密码学的新方向》[2]一文，提出的公钥密码体制，引起了密码学史上的一场革命，为解决通信网络中的信息安全提供了新的理论支持和技术基础；另一事件是美国国家标准局NBS( National Bureau of Standards)公开征集，并于1977年正式公布实施的美国数据加密标准(DES)(Data Encryption Standard)。这两个事件标志着现代密码学的诞生。从此，现代密码学无论在理论上，还是在应用上都得到了空前的发展，逐渐形成了集数学、计算机科学、电子与通信等诸多学科于一身的综合学科。
自从密码理论和技术诞生以来，密码体制的强度问题就一直成为密码设计者和分析者研究的核心内容。 流密码是保密通信中的一个重要的密码体制。流密码体制的强度完全依赖于密钥流产生器所生成的伪随机序列的随机性(Randomness)和不可预测性(Unpredictability)。Shannon在1949年就从理论上严格证明了如果密钥流序列是一个真随机序列，那么相应的流密码是绝对安全的
[3]
。但是实际上，由于人们无法完全重复地产生同一个随机序列，只能用伪随
机序列代替随机序列。很多密码学研究者开始寻找评价伪随机序列随机性和不可预测性的度量指标。密钥流序列的随机性度量指标主要有：串分布、自相关值、周期和线性复杂度等。特别是六十年代末Berlekamp-Massey提出的线性反馈移位寄存器序列的B-M综合算法[4]使得线性复杂度成为一些流密码系统强度的重要指标，随之很多相关研究成果相继提出。如果序列S??(s0,s1,?,sN?1,?)的线性复杂度为LC(s?)，则只要知道该序列的任意LC(s?)个连续比特，就可通过解线性方程组或用B-M算法找到该序列所满足的齐次线性递归关系式，从而确定整个序列。因此要求密钥流序列的线性复杂度必须足够大。对于一般序列的综合，B-M算法目前仍然是最优的。1983年Games和Chan提出了周期为2n的二元序列线性复杂度的快速算法[5]，进一步推进了线性复杂度算法的研究。
但是线性复杂度高的序列并不一定是安全稳定的序列。例如一个周期为N的二元序列S?的第一个周期为SN?(0,?,0,1)，其线性复杂度LC(S?)?N达到了最大值 ，只要把最后的一位的1变为0，则该序列的线性复杂度降低为0，这样的序列的线性复杂度是不稳定的，用来作为密钥序列是不安全的，可见，序列
1
的线性复杂度的稳定性与序列的不可预测性是密切相关的。因此，密钥流序列的线性复杂度不仅要足够大而且必须有很好的稳定性。八十年代末期，中国学者丁-肖-单在此基础上首先提出了重量复杂度、球体复杂度、球面周期、球体周期、函数稳定性等流密码系统稳定性的新的度量指标，并且建立了各种指标之间的相互关系，给出了对于某些序列改变k位元素后序列线性复杂度的下界，建立了流密码稳定性的基础理论，使得流密码强度问题研究得到了重大突破[6]，引起了国际密码学界的广泛关注。1993年Stamp和Martin提出了类似‘球体复杂度’的线性复杂度稳定性度量指标‘k-错线性复杂度’，并且提出了一个计算周期为2n的二元序列k-错线性复杂度的快速算法[7，8]，使得线性复杂度的稳定性研究有了新的重要推进，很快k-错线性复杂度就被广大学者进行了大量的应用和推广。2003年Lauder和Paterson将Games-Chan算法和Stamp-Martin算法同时推广，提出了一个计算周期为2n的二元序列线性复杂度曲线的算法，该算法可以同时计算周期为2n的二元序列的线性复杂度和k-错线性复杂度，随后也得到了一些推广算法[9，10，11]。现在，周期和线性复杂度仍然是度量密钥流序列安全强度的两个最为重要的指标。
在分析密钥流序列的这两个指标的同时，必须考察它们的稳定性.对于线性复杂度及其稳定性的研究，一方面是设计线性复杂度和k-错线性复杂度的快速算法，另一个重要的热门话题是对周期序列的线性复杂度及其稳定性进行理论分析.研究线性复杂度的稳定性是因为少量比特发生变化可能会引起线性复杂度的急剧下降，那么，究竟多少比特发生变化会引起线性复杂度的下降?在文献[12]中提出了最小错误minerror(S)的概念来描述这个问题，将最小错误minerror(S)定义为使得线性复杂度下降时至少要改变的比特数.那么，具体是哪些位置发生变化会引起线性复杂度的下降?文献[12]引入错误序列来阐述这个问题.下降后的线性复杂度又会是多少呢?即当k = minerror(S)时，k-错线性复杂度的值是多少，针对这些问题，文献[12]研究了2n?周期二元序列线性复杂度与k-错线性复杂度的关系，给出了用线性复杂度的Hamming重量表示的最小错误minerror(S)的值，并给出了k = minerror(S)时k一错线性复杂度的上界.这一结果的提出引起了很多研究者的关注[9，13，14，15，16] 。随之，研究学者开始考虑线性复杂度的稳定性及线性复杂度之间可能存在的某种内在联系.找出线性复杂度及其稳定性的关系不仅有利于指导设计计算周期序列线性复杂度和k-错线性复杂度的快速算法，而且可以直接通过对线性复杂度的分析，从而进一步分析其稳定性。
对于周期序列的线性复杂度及其稳定性的理论分析的另一个重要方面是分析周期序列线性复杂度和k-错线性复杂度的统计特性，如分布、数学期望、方差等[17，18，19，20，21，22，23，24],Rueppel对二元序列线性复杂度的随机性进行了研究
[25]
，并猜测周期二元序列的线性复杂度的期望值接近它的周期N，文献[26]利
2