二元周期序列复杂度的分析

摘要

在通信系统中，流密码是保证通信安全最重要的一种手段，大量应用于军事、政治和电子商务中。其安全性得到研究学者的大量关注，特别是衡量密钥流安全性强度的度量。
　　 线性复杂度是衡量密钥流安全强度的一个重要指标，如何提高线性复杂度的计算效率是流密码学中一直研究的问题。此外，在各种编码（如Reed-Muller码）中，线性复杂度也可作为基本的度量。然而，高线性复杂度并不意味着难以预测。若改变序列若干位，线性复杂度马上降下来，加密信息很容易遭到已知明文攻击。为了解决上面的问题，Stamp-Martin引入周期序列线性复杂度稳定性的概念以衡量序列的稳定性，定义序列在较大干扰的情况下，仍然能够保持较为理想的线性复杂度。
　　 本文首先介绍了随机序列的生成过程，序列随机性的描述，线性移位寄存器的特性。然后引入线性复杂度算法，包括求任意长度序列线性复杂度的B-M算法，以及求周期为2n序列的线性复杂度的算法，以及给出了在CUDA(ComputeUnified Device Architecture)平台下，并行加速2n序列线性复杂度的算法，实验结果得到比较理想的加速比，能够在足够短的时间内求得序列线性复杂度。
　　 序列线性复杂度即使达到最大，而序列复杂度却可能很不稳定，理想中的随机序列不仅要线性复杂度最大，稳定性需要保证，希望在一定的扰动下，序列仍能够保持较大的线性复杂度。为了衡量序列的稳定性，本文介绍k错线性复杂度的定义，表示扰动k位序列后序列的最小线性复杂度，因为k错(k-error)线性复杂度是在序列线性复杂度基础上引入的概念，所以求k错线性复杂度的算法也是由求线性复杂度的算法扩展而来，并且由于数据的相互依赖性更小，适合CUDA并行化计算。
　　 针对周期为2n的二元序列，若线性复杂度错误谱具有较多的关键点(critica] point)，表明序列具有很好的稳定性。本文中，给出n=7时存在最多关键点个数为34（2n(∶)2(G)2）的周期序列。在筛选稳定序列的过程中，发现了一些序列的相似特性，进而把这部分序列归为等价类，从而方便序列稳定性的研究。最后文中提出序列关键点数目最大值的最低界限。

目录

声明

摘要

第一章 绪论

第一节 研究背景

1．1．1 序列的发展及应用

1．1．2 序列密码

1．1．3 线性复杂度

第二节 研究现状

第三节 本文主要工作

第四节 本文组织结构

第二章 背景知识介绍

第一节 序列密码和周期序列

第二节 线性反馈移位寄存器

第三节 序列线性复杂度及稳定性

第四节 线性复杂度计算算法

2．4．1 Berlekamp-Massey综合算法

2．4．2 Games-Chan快速算法

2．4．3 对于周期为N(u2v)的二元序列

第五节 PC机群系统

第六节 GPU架构

2．6．1 GPU架构的优势

2．6．2 GPU计算模型

2．6．3 存储器层次结构

第三章 二元周期序列线性复杂度的计算

第一节 周期为2n的二元序列

3．1．1 线性复杂度的串行计算

3．1．2 序列线性复杂度GPU并行化算法

3．1．3 序列线性复杂度机群并行算法

3．1．4 实验结果的分析和比较

第二节 周期为3*2v的二元序列

3．2．1 线性复杂度的串行计算

3．2．2 序列线性复杂度GPU并行化算法

3．2．3 序列线性复杂度机群并行算法

3．2．4 实验结果的分析和比较

第四章 二元周期序列线性复杂度的稳定性分析

第一节 k错线性复杂度的引入

第二节 k错线性复杂度的计算

第三节 k错线性复杂度的并行算法

第四节 实验结果的分析和比较

第五节 周期序列错误谱算法

第五章 构造关键点多的二元周期序列

第一节 序列错误谱和关键点

第二节 两个映射的定义

第三节 周期序列模式分析

第四节 寻找CP较多的序列模式

第五节 错误谱分析

第六节 关键点数目多的序列

第六章 总结和展望

第一节 总结

第二节 展望

参考文献

致谢

个人简历