De Bruijn Sequences From Nonlinear Feedback Shift Registers

Among shift register sequences,M sequences also called de Bruijn sequences play an essen-tial part in secure communications due to their perfect random properties,large key schedule,and resistance to attacks.In recent years,cryptanalysis,such as correlation attack and alge-braic attack,has developed rapidly.Nonlinear feedback shift registers hold the potential to take the place of linear feedback shift registers and predominate in related fields.The main research of this thesis focuses on the geometric structure of feedback shift reg-isters.State diagrams are analyzed with the purpose of constructing de Bruijn sequences.Results are listed as follows:(1)Some codes are developed on MATLAB to describe the state diagram of any feedback shift register according to its feedback function.The codes also calculate corresponding properties,including the sum of cycles as well as that of connected components,the respec-tive total number of triple junctions and leaves.It is shown that an output could be obtained very quickly for feedback shift registers with order less than 17.(2)Based on the formulas of each sum of cycles on PSR and CSR provided by Golomb,the formulas of the distributions of cycle length on PSR and CSR are provided and proved strictly.Thus,the geometric structure of these two classical feedback shift registers is com-pletely decided.(3)The cycle structure of CSR is discussed with the concept of cycle extended represen-tation introduced by Etzion and Lempel.With several special properties of CSR provided,an algorithm is proposed to generate as many as(?)de Bruijn sequences from a CSR_n.The storage is around n~2/2.It needs n cyclic shift operations as well as n-bit comparison operations to output next bit.It is also proved by methods in graph theory that cycle extended representation could limitedly be applied to only two shift registers,namely PSR and CSR.(4)With the codes mentioned above,two singular feedback shift registers are discussed.Strict mathematical proofs of the geometric structure of their state diagrams are given.This work could inspire future researchers how to analyze this kind of singular feedback shift reg-isters with state diagrams consisting of some full binary trees.