Research On Non-linear Feedback Shift Registers Via Semi-Tensor Product

Nonlinear feedback shift registers(NFSRs)are the most popular building blocks applied to design stream ciphers,because of their efficient implements in both hardware and software.In the last decades,many ciphers have used NFSRs as their driving structures,such as Triviumn,Mickey and Grain.However,NFSRs is not well-understood for lacking of efficient tools.By using semi-tensor product(STP),NFSRs can be transformed into algebra-ic expressions,which can be better investigated.Under this algebraic framework,some important questions of NFSRs have been investigated,such as the non-singularity and stability.As known to all,observability is an important theme in the control theory.In this paper,we investigate the observability of NFSRs by using the STP,and give the corresponding observability matrix,which is an important tool in researching the problems of transformation and degeneracy of NFSRs.The main contents of this thesis are listed as follows:In chapter 1,two types of NFSRs have been introduced:Fibonacci NFSR's and Galois NFSRs.Also,the backgrounds of NFSRs and the STP of matrices are provided.At last,the main research results and organizations of this thesis are given.In chapter 2,the definition and operation methods of the STP of matrices are presented.Then,the algebraic expression of NFSRs are introduced by using the STP.Based on the above and corresponding structure matrices,the definitions of observability and observability matrices of NFSRs are proposed.In chapter 3,the definition of degeneracy of NFSRs is introduced.Necessary and sufficient conditions for the degeneracy of NFSRs are obtained via its observ-ability matrix.For degenerated NFSRs,the equivalent NFSRs with smaller order are obtained by constructing its structure matrices,and one example is shown.In chapter 4,the definition of the equivalence between two NFSRs is present-ed,and the importance of investigating the equivalent transformation between Fibonacci NFSRs and Galois NFSRs are introduced.Then,by utilizing the ob-servability matrix of a given Galois NFSR,necessary and sufficient conditions for transforming a Galois NFSR into a Fibonacci NFSR are obtained.Two examples are shown to illustrate the effectiveness of the obtained results.In chapter 5,we give the summary of this dissertation and the future research work prospects.