基于反馈移位寄存器的流密码相关问题研究

With the development of the theory and techniques of algebraic attacks and fast algebraic attacks, the security of the stream ciphers based on linear feedback shift registers has been seriously threatened. In recent years, nonlinear feedback shift registers have been important cryptographic primitives in the design of keystream generators, and that nonlinear sequences are used as driving sequences has been a new trend in the design of stream ciphers based on feedback shift registers.This project will focus on studying Boolean functions and nonlinear feedback shift registers used in stream ciphers based on feedback shift registers. Specifically, by applying the tools of algebra, coding theory, combinatorics and computer algebra, we will propose some constructions of Boolean functions having good behavior against algebraic attacks, fast algebraic attacks and possessing other desired cryptographic properties, investigate the cycle structure of Fibonacci nonlinear feedback shift registers, analyze the cryptographic properties of Galois nonlinear feedback shift registers coming from Grain and Trivium alogrithms, and study the nonlinear complexity and k-th order complexity of sequences over finite fields. These studies have important theoretical and practical value for developing methods and techniques in the design and analysis of stream ciphers based on feedback shift registers.

随着代数攻击和快速代数攻击等密码分析理论与技术的发展，基于线性反馈移位寄存器的流密码的安全受到了严重威胁。近年来，非线性反馈移位寄存器逐渐成为密钥流生成器的一种重要设计原件，非线性序列作为驱动已经成为基于反馈移位寄存器的流密码设计的新趋势。本项目将集中研究用于基于反馈移位寄存器流密码的布尔函数和非线性反馈移位寄存器。具体地，我们将运用代数学、编码学、组合学和计算机代数等工具，构造具有较好抗代数攻击、快速代数攻击和其它优良密码学性质的布尔函数，研究Fibonacci型非线性反馈移位寄存器的圈结构，探讨以Grain和Trivium算法中的非线性反馈移位寄存器为原型的Galois型非线性反馈移位寄存器的密码学性质，并讨论有限域上序列的非线性复杂度和k次复杂度等问题。这些研究对发展基于反馈移位寄存器的流密码设计与分析的方法和技术具有重要的理论意义和应用价值。

流密码是密码学的一个重要研究内容。反馈移位寄存器是设计流密码密钥流生成器的重要工具。随着代数攻击和快速代数攻击等密码分析理论和技术的发展，基于线性反馈移位寄存器的流密码的安全受到了严重威胁。近年来，人们积极尝试使用非线性反馈移位寄存器来设计密钥流生成器。本项目主要研究具有良好密码学性质的密码函数和非线性反馈移位寄存器的密码学性质。对于密码函数的研究，通过修改Tu-Deng函数和Tang-Carlet-Tang函数给出了构造1-弹性布尔函数的一般方法，在某些情况下，所构造的函数有较好的抗差分攻击、抗相关攻击以及抗代数攻击的能力。布尔函数的研究工作也扩展到多输出情形：利用经典的分组密码Festel结构和MISTY结构构造了大量的完全置换多项式；利用极坐标表示法和处理方程解数技巧构造了几类Niho型指数置换多项式；探讨了有限域上的三循环置换多项式。对于非线性反馈移位寄存器的研究，利用代数学的知识，刻画了一些具有对称反馈函数的非线性反馈移位寄存器生成序列的最小周期；通过分析一类具有可约特征多项式的线性反馈移位寄存器的圈结构和邻接图，给出了由这些线性反馈移位寄存器产生最大长度非线性反馈移位寄存器的算法，得到了一批de Bruijn序列；利用符号计算和Grobner基理论，得到了一类非线性反馈移位寄存器的子簇性质；利用级联运算的相关规律，确定了两类级联序列的周期上界；构造了两类Grain-like非线性反馈移位寄存器，部分地解决了Hu和Gong所提出的公开问题；探讨了研究非线性反馈移位寄存器圈结构的新方法。对于序列复杂度的研究，采用递归的方法，给出了所有非线性复杂度达到最大值和次大值的周期序列，并讨论了这些序列的随机性；利用组合方法，构造了非线性复杂度接近最大值的有限长序列，并确定了这些序列的条数；设计了新的广义分圆二元序列并确定了其线性复杂度；考虑了Thue-Morse序列，Rudin-Shapiro序列以及Rudin-Shapiro-like序列等自动序列的复杂度。这些研究为发展基于反馈移位寄存器流密码的设计和分析的方法与技术具有重要的理论意义和应用价值。