Research On Some Problems Of Nonlinear Feedback Shift Register Sequences

It is a new trend that replacing linear feedback shift register(LFSR) sequences with nonlinear feedback shift register(NFSR) sequences as the driving sequences in stream cipher design. Therefore, studies of NFSR sequences gradually become a hot topic in stream cipher. Although it has been studied for more than 50 years, noting the difficulty of nonlinear problems, many basic properties concerning NFSR sequences are not clear. For example, the cycle structure, decomposing an NFSR as a cascade connection of smaller NFSRs and determing the subfamilies for a given NFSR. Considering the above questions, this thesis gains the following main results.1. If an n-stage NFSR sequence reaches the maximum period 2n, then we call it an n-stage de Bruijn sequence which has ideal pseudorandom properties. In this thesis, a new necessary condition for NFSRs to generated de Bruijn sequences is presented. The number of NFSRs which can be covered by this new necessary condition is estimated. The result shows that this number is very large. Furthermore, based on BDD representations of Boolean functions, a verification algorithm is presented and its computation complexity is analyzed.2. The cycle structure of an NFSR means that how many cycles of each period it can generate. In 1976, based on abstract algebraic theory, K. Kjeldsen proved the cycle structure of a class of symmetric NFSRs. In this thesis, we first determine the periods of some cycles for two classes of NFSRs. Applying this result, the cycle structure of a larger class of symmetric NFSRs can be completely determined. This result covers the known results and our method is straightforward. Furthermore, the evaluation of the number of symmetric NFSRs covered by our results shows that more than half of them have the cycle structure proven in this thesis.3. For the case that an NFSR can be decomposed as a cascade connection of smaller NFSRs, this thesis discusses the uniqueness of decompositions. Concretely, if an NFSR can be decomposed as a cascade connection of a smaller NFSR into an LFSR, then it shows that during all of such decompositions, the largest LFSR is unique. For the general cases, we construct a class of counterexamples to show that the decomposition is not unique.4. Denote NFSR( f) the NFSR with characteristic function f, and denote G( f) all the sequences generated by NFSR( f). Given NFSR( f) and NFSR(h), if G(h) ? G( f), then we say G(h) a subfamily of G( f). When G( f) contains a subfamily G(h), some of its output sequences can be generated by a smaller NFSR. This is a kind of degenerated property. It is a very interesting work to determine all the subfamilies for a given NFSR. However, it is also a very difficult problem. Given NFSR( f) and NFSR( g), this thesis discusses the greatest commo n subfamily of G( f) and G( g). Different from the cases of LFSRs, the greatest common subfamily of G( f) and G( g) may not be unique. Given NFSR( f) and NFSR( g), suppose that their greatest common subfamily G(h) exists and is unique. If G(h) ? G( f) ? G( g), then based on the Gr?bner theory, a method which can determine G(h) is presented. Otherwise, if G(h) ? G( f) ? G( g) and G(h) ? G( f) ? G( g), then the greatest common subfamily G(h) can also be determined by Gr?bner theory under some conditions.