基于全体圈个数为4的LFSR 构造de Bruijn 序列的研究

周琮伟，胡斌，关杰

（信息工程大学密码工程学院，河南 郑州 450001）

0 引言

近几十年来，线性反馈移位寄存器（LFSR,linear feedback shift register）序列被广泛应用于通信编码和密码算法中，例如众所周知的m序列。然而由于LFSR固有的线性制约性及输入的多条乱源序列存在时间差，可以对其经过非线性改造产生的密钥流的序列周期与线性复杂度进行深刻的代数刻画[1]，并且在此基础上提出的相关攻击[2]、最佳仿射线性攻击[3]与代数攻击[4]等分析方法均有对应的算法攻击实例，因此逐渐将研究对象从LFSR 转向非线性反馈移位寄存器序列。其中n级de Bruijn 序列是一类重要的非线性反馈移位寄存器序列，其圈结构中圈长达到最大周期2n，同时其伪随机性质与线性复杂度[5]均优于m序列。此外，de Bruijn 序列在卫星通信[6]、电网技术[7]和基因测序[8]中均有广泛应用。

构造de Bruijn序列一直以来都是研究de Bruijn序列的核心问题，其构造思路主要是基于反馈移位寄存器圈结构中各圈的合并，其难点在于研究各圈上的共轭状态分布。在20 世纪70 年代至90 年代，国际上掀起了研究构造de Bruijn 序列的热潮，各种算法和结果层出不穷[9-17]，其中文献[12]比较全面地介绍了de Bruijn 序列构造的经典算法。近期国内学者也给出了一些构造算法[18-19]，但快速构造密码学性质良好和实用性强的de Bruijn 序列特征函数仍然是一个长期亟待解决的问题。

从20 世纪70 年代起，Lempel[20]引入D-同态的概念，利用n级de Bruijn 序列在D-同态下的原像是2 个n+1级的等长圈，并结合2 个等长圈上共轭状态的分布特点，给出了一个由n级到n+1级de Bruijn 序列特征函数的递归构造方法，且可以进一步拓展到n+2级[21]。……