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(x0,x1,...,xn) = x0⊕f1(x1,...,xn-1)⊕xnbe 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∈Scixi, where ci∈ F2and 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∈Scixiover the finite field F2. 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 F2. 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.

Grain-128 is a hardware oriented stream cipher based on the cascade connection of a 128-bit linear feedback shift register into a 128-bit quadratic nonlinear feedback shift register (NFSR). Its main register is in essence a quadratic NFSR, however its affine sub-families could not be solved by the previous methods. In this paper, it is shown that the family of sequences generated by the main register of Grain-128 includes no affine sub-families except a small one of order three. To achieve this goal, a new method is proposed for solving affine sub-families of general quadratic NFSRs. Let NFSR(f) be an NFSR with a quadratic characteristic function f . It is proved that the characteristic function of a linear sub-family of the NFSR(f) divides a linear combination of variables appearing in the quadratic terms of f , where the division can be seen as the univariate polynomial division over the finite field F2. This facilitates picking up a candidate set of linear sub-families through univariate polynomial factorization over F2. The affine case is an analogy. Besides, a useful new upper bound on the orders of affine sub-families of a quadratic NFSR is given.

Nonlinear feedback shift registers (NFSRs) are widely used in stream cipher design as building blocks. In this paper, we study the problem of decomposing an NFSR into the cascade connection of an NFSR into a linear feedback shift register (LFSR), which is a kind of concatenation of an NFSR and LFSR. A necessary and sufficient condition for such decomposition is provided and other algebraic properties about such decomposition are also studied. Based on these theoretical results, a binary decision diagram (BDD)-based algorithm for such decomposition is proposed. Compared with the previous algorithm proposed by Ma et al., our algorithm can find more accurate candidate LFSR and the algebraic properties presented in this paper guarantee that the memory requirement during our verification is linear in the size of the BDD of the NFSRs characteristic function.