基于布尔网络的非线性反馈移位寄存器的串联结构研究

Cascade connections of nonlinear feedback shift registers (NFSRs) have been recently used as the main building blocks in many stream ciphers, such as Grain, Spout and Lizard. Compared to a single NFSR, a cascade connection of NFSRs has better information confusion and diffusion, and thus improves the security of stream ciphers, though they are equivalent. Due to lack of efficient tools, the theory of NFSRs has not yet well-understood, far from the requirements of analyses and designs of the stream ciphers. In the preliminary study, we found that the theory of Boolean networks based on the semi-tensor product of matrices in control theory is a powerful tool for solving the cryptography problems related to NFSRs. This project will apply the theory of Boolean networks to the analysis of a cascade connection of NFSRs, and mainly studies: (1)cascade connection decomposition of an NFSR, exploring the decomposability, decomposition uniqueness and decomposition types etc., for the decomposition of an NFSR into a cascade connection of NFSRs; (2)cycle structure of a cascade connection of NFSRs, investigating its cycle number, the feature of states on cycles, the existence of its sequences with minimum/maximum period, and the number of cascade connections of NFSRs that can generate sequences with minimum/maximum period, and so on. This project will reveal the cryptographic properties of the above two aspects, which provides some theoretical guides and technical support for the analyses and designs of stream ciphers.

非线性反馈移位寄存器(NFSR)的串联作为主要部件近年来广泛应用于各种序列密码中，如Grain、Sprout和Lizard。虽然NFSR的串联等价于单个NFSR，但相比单个NFSR，NFSR串联的信息混乱和扩散效果更好，提高了密码算法的安全性。因为缺乏有效工具，NFSR理论还很不成熟，远不能满足密码算法分析与设计的需求。在前期研究中，我们发现：控制论中基于矩阵半张量积的布尔网络理论是解决NFSR相关密码学问题的一个强有力工具。本项目将把布尔网络理论应用于NFSR串联结构的分析中，主要研究：(1)NFSR的串联分解：探索单个NFSR分解为NFSR串联的可分解性、分解唯一性、分解种数等；(2)NFSR串联的圈结构：探索圈个数、圈上状态的特点、最小/最大周期序列的存在性、可生成最小/最大周期序列的NFSR串联的个数等。本项目将揭示以上两方面的密码性质，为密码算法分析与设计提供理论指导和技术支持。

非线性反馈移位寄存器(NFSR)作为主要组件近年来广泛应用于各种流密码中，特别地，NFSR的串联应用于Grain类流密码算法中。虽然NFSR的串联等价于单个NFSR，但相比单个NFSR，NFSR串联的信息混乱和扩散效果更好，提高了密码算法的安全性。因为缺乏有效工具，NFSR理论还很不成熟，远不能满足密码算法分析与设计的需求。本项目把系统与控制领域近年来发展的布尔网络理论应用于NFSR的分析中，特别是NFSR串联结构的分析中，主要成果有：(1)NFSR的串联分解：给出了单个NFSR分解为NFSR串联的充要条件、分解的非唯一性、分解种数；(2)NFSR串联的圈结构：揭示了最小/最大周期序列的NFSR串联的存在性、圈个数、圈上状态的特点；(3)NFSR的可观测性：提出了新的可观测矩阵，给出了Galois型NFSR可观测的充分/必要条件；(4)NFSR的等价性：给出了等价于Fibonacci型的Galois型NFSR的特征，证实了现有Grain类流密码算法在等价串联中已优化了硬件实现代价。这些结果为密码算法分析与设计提供了理论指导和技术支持。