非线性反馈移位寄存器密码应用的若干基础问题研究

Nowadays, the design of stream ciphers has entered the era of nonlinear driving sequences, and it is urgent to have a large number of nonlinear driving sequences with good cryptographic properties. The nonlinear feedback shift register (NFSR) is the most direct and effective way to produce nonlinear sequences, and is also an ideal component for building lightweight stream ciphers. However, due to the difficulty of NFSR research, NFSR sequences is still not well-understood by peoples, which severely restricts their cryptographic applications. In this project, we study some basic problems of NFSR cryptographic application. The research contents mainly included: the distribution law of the item in the characteristic functions of De Bruijn sequences; the construction of De Bruijn sequences based on cascade connection of NFSRs; cryptographic properties of ring-like cascade connection of NFSRs; further study on the sub-families of NFSR. The research above not only involve the basic theory of NFSR, but also focus on the NFSR sequences from the perspective of cryptographic applications. Through the above research, we hope to provide theoretical support and application guidance for the design and analysis of stream ciphers based on NFSRs.

当前序列密码算法设计已进入非线性驱动的时代，迫切需要大量具有优良密码性质的非线性驱动序列。非线性反馈移位寄存器(NFSR)是产生非线性序列的最直接有效的方式，也是构建轻量级密码的理想组件。然而由于NFSR研究的困难性，人们对NFSR序列的认识仍然非常有限，严重制约了其密码应用。本项目我们研究NFSR密码应用的若干基础问题，研究内容主要包括：De Bruijn特征函数中项的分布规律研究；基于串联NFSR的de Bruijn序列构造；环状串联NFSR的密码性质研究； NFSR子簇问题的进一步研究。这些问题不仅涉及NFSR的基础理论, 而且更侧重于从密码实用性的角度来研究NFSR序列。通过上述研究, 以期为基于NFSR的序列密码算法设计与分析提供理论支撑和应用指导。

密码技术与核技术、航天技术被并称为国家安全三大支撑技术，广泛应用于国防和国民经济各领域，在维护国家网络空间安全、促进经济和社会发展、保护公民合法权益等方面发挥着不可替换的作用。密码算法是构建密码技术的重要基石，当前密码算法设计迫切需要大量具有优良密码性质的非线性序列。本项目围绕非线性反馈移位寄存器(简称NFSR)密码应用的若干基础问题展开研究，取得多个原创性研究成果，在密码学著名期刊和会议上发表或录用论文16篇，其中SCI检索13篇，具体成果如下：.1.首次给出modified de Bruijn序列线性复杂度的非平凡下界，建立了modified de Bruijn序列线性复杂度与前馈函数之间的关系，完善了modified de Bruijn序列的极小多项式理论。.2. 提出构造de Bruijn序列特征函数的新方法，丰富了de Bruijn序列特征函数的构造理论。.3. 给出NFSR串联不可约的多个新充分条件，完善了NFSR串联不可约理论。.4. 提出“求偏导数+高低求导”的思想，彻底解决型如 h=g*g 的布尔函数星积分解问题，并给出高效的分解算法，基本解决型如 h=f*g 的布尔函数星积分解问题，完善了NFSR的串联分解理论，对基于NFSR的密码算法设计与分析均具有重要的理论意义和实用价值。.5. 给出Trivium型NFSR线性退化的充要条件及线性退化条件下输出序列的周期，充实了Trivium型环状串联NFSR的相关理论。.6. 给出NFSR仿射子簇的求取理论和求取算法，为设计和构造不含仿射子簇的NFSR提供了重要理论支撑。.7. 构造了一类同构NFSR，对设计具有优良密码性质的NFSR具有重要的实际意义。.8. 给出Grain型NFSR串联结构存在极小圈的一种构造性证明，并给出极大圈存在的两个必要条件及一类特殊NFSR的圈结构，丰富了NFSR的圈结构理论。.9. 给出基于置换多项式设计非线性序列的新理论，研究了这类非线性性质的密码性质，对设计周期可控非线性序列具有重要意义。.上述成果的取得对设计核心技术自主可控的密码算法，分析当前基于NFSR设计的密码算法的安全性具有重要理论和现实意义。