非线性反馈移位寄存器的乘除法及应用

We study the star product and generalized division algorithm of nonlinear feedback shift registers. These two operations were first proposed in 1970s. These years, because of the popularity of nonlinear feedback shift registers in stream cipher designs, star product and generalized division algorithm have drawn much attention. They are useful in the research of cascade connection and sub-families. In this project, we study the congruent equations of generalized division algorithm. This problem is not only interesting in theory, but can also be used to solve cryptographic problems in the study of nonlinear feedback shift registers. Especially, we turn the famous open problem, the smallest period of cascade connection sequences, to congruent equations of generalized division algorithm. This is very significant and gives us a unique perspective to treat this problem, and may finally solve it.

本项目研究非线性反馈移位寄存器的星积和广义除法，这两个运算在上世纪70年代引入。近年来，由于序列密码设计广泛采用非线性反馈移位寄存器，星积和广义除法得到大量的关注，被用来研究串联结构的性质以及子簇的求取。本项目研究广义除法同余方程的求解问题，这个问题不仅在理论上有意思，并且能够解决非线性反馈移位寄存器研究中的密码学问题。特别是，著名公开问题——串联结构的最小周期可以化为特定广义除法同余方程的求解。这是非常有意义的，为我们解决这两个问题提供一个独特的角度，并有可能使这个问题最终被解决。

本项目研究广义除法同余方程求解问题和串联结构最小周期问题。其中广义除法同余方程求解问题是本项目首次提出的问题，串联结构最小周期问题是密码设计中非常重要的一个问题。我们提出两类广义除法同余方程，对第一类方程的研究中，我们给出了方程有解的等价条件，并提出一个求解的方法。在串联结构最小周期问题研究中，我们将其等价为一个第二类同余方程的求解问题，从而将这两个问题联系起来。这说明了同余方程求解不只是一个理论上的问题，还可以用来解决密码设计中的重要问题，具有重要的意义。另外，我们用计算机程序统计能生成最小周期序列的串联结构个数，数据显示能够生成最小周期序列的串联结构占有一个较大的固定的比例，说明生成最小周期序列的串联结构是普遍存在的。