基于寄存器串联的de Bruijn序列构造

The Construction of de Bruijn Sequence Based on Cascade Connection

采用非线性反馈移位寄存器(NFSR)序列代替线性反馈移位寄存器(LFSR)序列作为驱动序列逐渐成为序列密码设计的主流趋势,因此NFSR也成为当前序列密码研究领域的一个热门课题.虽然研究历史已经有半个多世纪之久,但NFSR的研究成果依然相对匮乏,诸如圈结构等基本的密码性质尚不清楚.其中,如何构造大周期、密码性质良好的NFSR序列是序列密码设计者最关注的问题之一.极大周期NFSR序列,也称de Bruijn序列,具有良好的伪随机性质,而其构造问题一直是研究的热点.本文利用一类反馈移位寄存器串联结构,将生成k级de Bruijn序列的NFSR串联至生成n级m-序列的LFSR中,给出了构造(k+n)级de Bruijn序列的方法.此类串联结构共有两条平移不等价的输出序列,文章给出了其中周期较小的输出序列的求取算法,并分析了这条序列上共轭状态的判断与选取,进而通过一次并圈得到de Bruijn序列.文章进一步分析了对于给定的(k+n),令k尽量小,则可以有效降低利用此法构造所需要的复杂度.

It has become a new trend to replace linear feedback shift register(LFSR) sequences with nonlinear feedback shift register(NFSR) sequences as the driving sequences in stream cipher design. Therefore, the study of NFSR sequences gradually becomes a hot topic in stream ciphers. Although it has been studied for more than 50 years, the theory of NFSR is relatively scarce and many basic properties concerning NFSR sequences are not clear. One of the most attractive problems is that to construct NFSR sequences with long periods and good cryptographic properties. The maximum-length NFSR sequences, also known as de Bruijn sequences, have good randomness properties and the study of their constructions is still a hot research topic. In this paper, based on a cascade connection of an NFSR generating k-order de Bruijn sequence into an LFSR generating n-order m-sequence, we give a method of producing(k+n)-order de Bruijn sequences. Such a cascade connection generates only two cycles. We present an algorithm to compute the smaller cycle and analyse the conjugate states between the two cycles. Then a new de Bruijn sequence can be obtained through the cycle joining method. Besides, for a given(k+n), the smaller value of k can reduce the complexity effectively according to our method.