本原σ-LFSR的若干密码学性质研究

论文摘要

随着NESSIE计划和eSTREAM计划的开展,流密码成为近几年密码学研究的热点课题。σ-LFSR利用少量的计算机基本指令就可以生成具有良好密码学性质的序列,其实现效率高和占用资源少的特点适用于流密码源序列发生器的设计。本原σ-LFSR序列具有最大周期以及良好的伪随机性,有着重要的应用价值。本文综合利用有限域、LFSR和矩阵多项式的相关知识,对本原σ-LFSR的距离向量、线性复杂度和采样序列三方面进行了研究,主要结果如下:第一部分研究本原σ-LFSR的距离向量。通过证明平移等价序列具有相同的距离向量,指出距离向量是本原σ-LFSR的一个特征量;对本原LFSR的距离向量进行分析,得到一个根据距离向量判断本原LFSR的充要条件;进而研究了本原σ-LFSR距离向量的特性,据此给出一个本原σ-LFSR序列的搜索算法。第二部分讨论本原σ-LFSR的线性复杂度。首先指出有限域2mF上n级本原σ-LFSR的线性复杂度为kn,其中1≤k≤m。然后从序列和的角度出发对本原σ-LFSR线性复杂度的分布情况进行研究:分析了2mF上n级本原σ-LFSR线性复杂度上界的紧致性,并构造出一类线性复杂度为上界的本原σ-LFSR序列;利用分位序列的迹表示,证明了上述k可以遍历1到m的所有值;在此基础上给出本原σ-LFSR线性复杂度期望值的下界和方差的上界,特别地,当m = 8, n= 16时,其值分别为0.99999mn和0.1,从而本原σ-LFSR序列的线性复杂度集中于上界mn;随之用迹表示方法得到本原σ-LFSR计数的一个下界。最后利用根表示和循环矩阵给出两种计算本原σ-LFSR线性复杂度的方法。第三部分分析本原σ-LFSR采样序列的性质。考察了本原σ-LFSR采样序列的距离向量,给出了其具体表达式;与本原LFSR采样序列相比,本原σ-LFSR的采样有着显著的区别:它存在非本原的t（t与周期互素）采样序列,进而得到两个关于采样序列本原性的结果;最后证明了本原σ-LFSR采样序列的线性复杂度保持不变。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景
• 1.2 基础知识
• 1.2.1 线性反馈移位寄存器
• 1.2.2 有限域上的矩阵多项式
• 1.3 σ-LFSR 概述
• 1.3.1 σ-LFSR 模型
• 1.3.2 σ-LFSR 研究现状
• 1.4 论文内容安排
• 第二章 本原σ-LFSR 序列的距离向量
• 2.1 距离向量的定义
• 2.2 本原LFSR 的距离向量
• 2.3 本原σ-LFSR 的距离向量
• 2.3.1 距离向量的特性
• 2.3.2 基于距离向量的本原σ-LFSR 搜索算法
• 第三章 本原σ-LFSR 序列的线性复杂度
• 3.1 线性复杂度的特性
• 3.2 线性复杂度的分布
• 3.2.1 上界的紧致性
• 3.2.2 遍历性
• 3.2.3 数字特征
• 3.3 线性复杂度的计算
• 3.3.1 根表示方法
• 3.3.2 循环矩阵方法
• 第四章 本原σ-LFSR 序列的采样性质
• 4.1 采样序列的距离向量
• 4.2 采样序列的本原性
• 4.3 采样序列的线性复杂度
• 结束语
• 参考文献
• 附录 本原σ-LFSR 线性复杂度的部分结果
• 作者简历 攻读硕士学位期间完成的主要工作
• 致谢