A New Method for Finding Affine Sub-Families of NFSR Sequences.

In this paper, a new and efficient method for solving affine sub-families included in a family of nonlinear feedback shift register (NFSR) sequences is proposed. The linear case is focused on since the affine case is an analogy. Let f(x₀, x₁,...,x_n) = x₀⊕f₁(x₁,...,x_n-1)⊕x_n be a characteristic function of an n-stage NFSR, where n is a positive integer. Let deg(f) = d > 1 and f_[d] be the summation of all terms in the algebraic normal form of f whose degrees attain the maximum d. First, it is proved that every linear sub-family of G(f) is a sub-family of linear feedback shift register sequences generated by a characteristic polynomial of the form Σ_i∈Sc_i xⁱ, where c_i ∈ F₂ and S consists of all subscripts of variables appearing in f_[d]. That is to say, every linear sub-family of G(f) is a factor of some polynomial Σ_i∈Sc _ixⁱ over the finite field F₂. This result is a well generalization of linear recurring sequences theory since it also holds if d = 1. Based on this result, a candidate set of linear sub-families could be obtained by polynomial factorizations over F₂. Second, we propose a new method to verify a linear sub-family whose memory requirement and time complexity are clearer than the previous method. For instance, all affine sub-families of the 160-bit main register used in Grain v1 could be determined within two seconds by a PC using the new method in this paper, which is unobtainable for previous algorithms. [ABSTRACT FROM AUTHOR]