非线性反馈移位寄存器仿射子簇和串联结构的研究

Nonlinear feedback shift registers (NFSRs) is an important class of nonlinear sequence generators used for stream cipher designs. However, because of NFSR sequences are extremely resistant to analysis, many cryptographical properties of NFSR sequences remains to be solved. Based on the progress achived by our research group on NFSRs, this project further studies the affine subfamilies of NFSRs and the casade connection of NFSRs. In specific, the main content of the project includes: estimation of the order of an affine subfamily of NFSR sequences, solving an affine subfamily of NFSR sequences, decomposing an NFSR into casade connection of two NFSRs, and the uniquess of such decomposition. The completion of the project will be good for the design and analysis of stream ciphers based on NFSRs.

非线性反馈移位寄存器(简称NFSR)是用于序列密码设计的一类重要的非线性序列生成器。然而，NFSR序列理论的研究难度很大，许多基本的密码性质仍不清楚。基于团队前期的研究成果，本项目拟进一步开展非线性反馈移位寄存器仿射子簇和串联结构的研究，包括仿射子簇阶数的估计、仿射子簇的求取、串联结构的分解、串联结构分解的唯一性。 通过本项目的研究工作，可以提高对NFSR序列的认识，丰富NFSR序列的基础理论，这对基于NFSR的序列密码设计与分析都十分有意义。

非线性反馈移位寄存器(NFSR)广泛应用于序列密码算法设计，是一类非常重要的非线性序列生成器。本项目主要研究NFSR基础理论，包括仿射子簇理论、串联结构、圈结构、de Bruijn序列的构造，取得一批优秀的研究成果。具体地, 完全解决了NFSR仿射子簇的判断和求取；给出并证明了一类串联结构表示唯一的充要条件；提出环状串联NFSR结构并应用于SPRING分组密码算法的设计；通过研究两类NFSR结构共轭对分布以及交织de Bruijn序列共轭对分布，给出三种构造de Bruijn序列的新方法。在对NFSR基础理论研究的同时，我们也关注基于NFSR的序列密码算法的安全性分析。针对国际序列密码算法标准Trivium，对立方攻击进行了研究，给出恢复超多项式的代数方法和提出基于MILP的条件差分攻击，其中在弱密钥条件下，对Trivium非随机性分析轮数达到1108轮，目前仍是国际最高轮数的非随机性结果。