Research On The Period And Subfamily Of Feedback Shift Registers

Information has become an important resource in our society and people pay more and more attentions on its safety.As the fundamental elements in keystream generators in stream ciphers,feedback shift registers(FSRs)have many applications in crypto-graph,coding theory and modern communication systems.In early ages,linear feed-back shift registers(LFSRs)are widely used for they can be fast and easy to implement in hardware and software,such as combiner,filter and clock-control models.LFSRs can generate some sequences with large periods and good pseudo-randomness,howev-er,these sequences also have some weaknesses,such as,low linear complexities.With the developments of cryptanalysis and computer technology,many attacks are found,for example,algebraic attack and correlation attack,which make LFSR sequences vul-nerable.To keep the information safe,people prefer to use nonlinear feedback shift registers(NFSRs).In 2004,many finalists in the ECRYPT Stream Cipher Project use NFSRs as the main building blocks,such as Grain,Trivium.Although NFSRs are more and more popular in practice,many properties are still unknown.Therefor,it's quite necessary to study NFSRs.A basic problem about NFSRs is the periods of the generated sequences.The dis-cussion of a general NFSR is quite difficult and complex,thus,many investigations are focused on some special types,such as,symmetric NFSRs.Kjeldsen firstly proposed a method to describe the periods of the generated sequences with a transformation and determined the periods for a class of symmetric NFSRs.Based on the previous the-ory,this paper continues to study the periods of a class of NFSRs,which is partially symmetric.Applying the knowledge of algebra,Boolean functions and finite fields,the periods of these NFSRs sequences are determined and we get more general results.An FSR is called reducible if the family of output sequences of this FSR contains a family of output sequences of a shorter FSR,moreover,this shorter FSR is called a sub-family.The reducible FSR can generate some sequences with low complexities,which make some attacks so effective that the information encrypted by these sequences is un-safe.Therefore,irreducible FSRs are needed.An n-stage FSR may have(?)22m-2-1 i=2 subfamilies,which is a huge number,thus,this it is difficult to check them one by one.To find a more efficient method,many experts try to investigate possible subfamilies of a given FSR.In recent years,Qi Wenfeng team has proposed a series of results to describe the possible subfamilies and estimated the number of irreducible NFSRs.This paper discusses the subfamilies of a certain type of NFSRs,that is,all nonlinear terms of its characteristic function have at least two common subscripts.By the Grobner basis theory,some necessary conditions are proposed and a set of LFSRs,which are not the linear subfamilies of the given NFSR,is found in certain cases.This narrows down the range of possible subfamilies and makes us know NFSRs better.