De Bruijn序列的构造方法与密码学性质研究

De Bruijn sequences are maximum period sequences that generated by nonlinear feedback shift registers. These sequences have wide applications in computer theory, communication theory and cryptography. In stream ciphers, De Bruijn sequences are believed to be good candidates of drive sequences because of their attractive cryptographic properties, such as large periods, nonlinear structure and high linear complexities. However, constructing De Bruijn sequences has long been an open problem. The existing methods are relatively complicated and their efficiencies are low, which makes the applications of De Bruijn sequences inconvenient. In this project, we will focus on the application of De Bruijn sequences in cryptography. We will study deeply the existing construction methods, further improve their efficiencies, and finally construct De Bruijn sequences that suitable for cryptographic applications. In addition, we will also study the cryptographic properties of De Bruijn sequences and calculate their security indexes to provide more security foundations. The results of this project will further enrich the theory of nonlinear recursive sequences and provide new theories and techniques for stream cipher design.

De Bruijn序列是由非线性反馈移位寄存器生成的极大周期序列，它们在计算机、通信和密码学中有着广泛的应用。在序列密码中，De Bruijn序列因具有大周期、非线性结构、高线性复杂度等密码学性质被认为是性能良好的驱动序列。然而构造De Bruijn序列却是长久以来的公开困难问题，目前已知的构造方法比较复杂且生成序列的效率较低，这给De Bruijn序列的应用带来了极大不便。本课题围绕De Bruijn序列在密码学中的应用开展研究，我们将深入研究已有的构造方法，进一步提高它们的生成效率，最终构造出适合于密码学应用的De Bruijn序列。另外，我们还将研究De Bruijn序列的密码学性质，计算它们的安全性指标，以给出更多的安全依据。本课题的研究结果将进一步推进非线性递归序列理论的发展，为序列密码设计提供新的理论和技术支持。

De Bruijn序列具有大周期、高线性复杂度、均匀游程分布等良好的密码学性质，被认为是构造流密码算法的一类理想驱动序列。然而，由于De Bruijn序列内在的非线性结构，使得研究De Bruijn序列极其困难。本项目围绕De Bruijn的构造方法和密码学性质两方面内容展开研究，主要的研究成果包括：（1）系统给出了从线性/仿射移位寄存器构造De Bruijn序列的方法，提出了一类新的具有固定边界的仿射邻接图；（2）分析了De Bruijn序列特征函数的重量分布，解决了Fredricksen在1982年提出的有关重量分布的猜想；（3）分析了De Bruijn序列的k错复杂度；（4）给出了本原乘积型特征函数中交叉共轭对的快速计算方法；（5）分析了l序列与De Bruijn序列之间的关系，并设计了从l序列构造De Bruijn序列的快速算法；（6）研究了De Bruijn序列特征函数的性质，设计了搜索De Bruijn序列特征函数快速算法。这些结果为流密码算法设计提供新的理论和技术支持。