非线性反馈移位寄存器圈结构研究

With nonlinear feedback shift registers replacing linear feedback shift registers to be the main building block in the stream cipher design, the theory of nonlinear feedback shift registers becomes a hot topic in the study of stream cipher. This project focuses on the period of sequences generated by nonlinear feedback shift registers, also known as the cycle structure of nonlinear feedback shift registers, that is, how many cycles of each minmal period it can generate? The detailed research of this project is as follows: the cycle structure of a class of nonlinear feedback shift registers; necessary conditions of de Bruijn sequences and their validation; construction of nonlinear feedback shift registers with guaranteed period of output sequences. The significance of this project is to give insight to the cycle structure of nonlinear feedback shift registers and to provide theoretical supportment for the future choice and construction of nonlinear sequences.

随着非线性反馈移位寄存器取代线性反馈移位寄存器成为序列密码设计的主要部件，非线性反馈移位寄存器的理论研究已成为当前序列密码研究领域的一个热点问题。本项目主要研究非线性反馈移位寄存器生成序列的周期，也称之为圈结构问题，即：其可以生成多少个圈以及每个圈的圈长是多少。具体内容有：一类非线性反馈移位寄存器的圈结构；de Bruijn序列必要条件及其验证；保证周期非线性反馈移位寄存器的构造。通过本项目的研究，可以深化对非线性反馈移位寄存器序列圈结构的认识，同时也为未来非线性序列源的选取与构造提供理论基础。

随着相关攻击和代数攻击等攻击方法的不断发展, 传统的基于线性反馈移位寄存器(LFSR)的“线性驱动+非线性改造”的设计思想, 日益引发人们对其安全性的忧虑. 为此，直接采用非线性迭代序列直接作为驱动序列, 则日益成为当前序列密码设计思想的主流选择. 这一点，在欧洲序列密码计划eSTREAM(2004-2008)和CAESAR竞赛(2013-2017)所提交的算法中体现的尤为明显. 然而, 与其快速应用不匹配的是, 非线性迭代序列的理论研究进展地十分缓慢. 例如, 周期性质是序列的一个基本性质, 然而对于一般的非线性反馈移位寄存器(NFSR), 其输出序列的周期仍然是一个公开问题.. 本项目着眼于NFSR输出序列的周期研究, 主要取得了以下两个方面的研究成果: 一是刻画了一类NFSR输出序列的周期. 具体为, 假设n级NFSR的特征函数为布尔函数f(x_0, x_1, ..., x_n), 并记此非线性反馈移位寄存器为NFSR(f). 若NFSR(f)的输出序列周期已知, 那么dn级NFSR(f^d)的输出序列周期可以清晰刻画, 其中f^d= f(x_0, x_d, ..., x_dn)也即将f(x_0, x_1, ..., x_n)的所有下标乘以整数d. 这一结果表明, 由已知的较小级数的NFSR的输出序列的周期, 可以确定一类较大级数NFSR的输出序列的周期, 因而刻画了一类特殊的NFSR的输出序列的周期问题. 二是给出了构造周期达到极大的NFSR的输出序列, 也即de Bruijn序列的两种方法. 方法一为, 给定一条n级de Bruijn序列, 基于已有的编织序列的方法, 可以构造出2条不平移等价的2n级de Bruijn序列. 反复使用该算法, 可以由低级数的de Bruijn序列, 快速的构造得到指数量级的高级数的de Bruijn序列。方法二为, 基于一个新的de Bruijn序列的必要条件, 在预计算出一条具有特殊圈结构的序列的前提下, 可以快速构造出双指数量级的de Bruijn序列.. 由于非线性问题的困难性, 对一般性问题进行研究是极其困难的, 我们的研究成果丰富了NFSR输出序列周期的研究理论, 为非线性迭代序列的设计与分析提供了理论依据.