非线性反馈移位寄存器序列的研究

作     者：李超云 

作者单位：湖北大学 

学位级别：硕士

导师姓名：曾祥勇

授予年度：2015年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：反馈移位寄存器 de Bruijn序列 D-同态 m序列 并圈法 圈结构 邻接图 

摘      要：反馈移位寄存器在现代通信系统、编码理论和密码学中有着广泛的应用.在密码学中,线性反馈移位寄存器是设计流密码密钥流生成器的重要组件.极大长度线性反馈移位寄存器序列,即m序列,具有长的周期和优良的伪随机性质,但它的线性复杂度却很小.为了设计大线性复杂度的密钥流序列,人们对m序列进行非线性改造,从而提出了流密码的组合、滤波和钟控等模式.随着相关攻击和代数攻击等密码分析技术的发展,基于线性反馈移位寄存器流密码的安全受到严重威胁.2004年欧洲启动的eSTREAM计划极大推动了流密码算法设计与分析的发展,以Trivium和Grain为代表的基于硬件算法的胜出标志着非线性反馈移位寄存器逐渐成为密钥流生成器的一种重要设计原件,非线性序列作为驱动已经成为基于反馈移位寄存器的流密码设计的新趋势.基于非线性反馈移位寄存器流密码越来越受到人们的重视.然而,非线性反馈移位寄存器的基础理论研究相对实际应用而言比较滞后,许多问题仍待解决.非线性反馈移位寄存器理论中的一个基本问题是构造极大长度的非线性反馈移位寄存器序列.极大长度非线性反馈移位寄存器序列,也称为de Bruijn序列,有着很好的密码学性质：长的周期,大线性复杂度和优良的伪随机性质,因而有着很好的应用前景.目前最常用的构造方法之一是Golomb提出的并圈法,通过依次合并给定移位寄存器状态图中的所有圈得到只含一个大圈的极大长度非线性反馈移位寄存器,从而生成de Bruijn序列.人们已经利用极大长度线性反馈移位寄存器,纯轮换移位寄存器以及纯和寄存器等的特殊圈结构通过并圈法构造deBruijn序列.本文将构造几类新的de Bruijn序列.本文将综合使用组合方法和代数方法确定几类线性反馈移位寄存器的圈结构和状态图中共轭圈的分布,从而利用并圈法构造de Bruijn序列.本文还将给出构造的极大长度非线性反馈移位寄存器反馈函数代数表达式和快速生成反馈函数的算法.这些研究对发展基于反馈移位寄存器的流密码设计与分析的方法和技术具有重要的理论意义和应用价值.