Boolean-network-based Analysis And Synthesis Of Pseudo-random Sequence Generators

With the coming of the era of big data,the data leakage is one of the main threats in the field of information security,and the encryption of information is a fundamental method to strengthen information security.The stream cipher is one of the most important crypto-graphic systems,among which the pseudo-random sequence generators including feedback shift register(FSR),filter generator and binary machine are one of the main devices to generate stream cipher.In this paper,based on the latest research results,the pseudo-random sequence generators are analyzed and constructed by the relevant research methods of Boolean networks.Additionally,the problem of reducing computational complexity and fault diagnosis problem are also addressed.The main work of this paper is summarized as follows:In Chapter 1,the concept of pseudo-random sequence generators and its significance are introduced.First,some background and fundamental results on feedback shift registers(FSRs),filter generators and binary machines are introduced.Then,the basic concept and properties of Boolean networks,which are the main method to investigate pseudo-random sequence generators in this paper,are introduced.In Chapter 2,the definition of semi-tensor product(STP)of matrices and the algebraic state space representations of pseudo-random sequence generators are introduced.First,the definition and some basic properties of STP are given.Then,based on the method of STP,the algebraic state space representation of Boolean networks is introduced.Finally,the algebraic state space representations of feedback shift registers and filter generators are also presented.In Chapter 3,the transformation between Fibonacci FSRs and Galois FSRs is addressed.First,these two kinds of FSRs are regarded as Boolean networks,and the corresponding alge-braic state space representations are obtained.For any given Fibonacci FSR with n stages,the algorithm of constructing all of the weakly equivalent Galois FSRs with n stages is proposed,and it is proved that there is no weakly equivalent Galois FSR with lower stages.Furthermore,the number of logical operators is optimized.In addition,for any given Galois FSR with n stages,the algorithm of weakly equivalent Fibonacci FSRs with minimum stages is proposed.In Chapter 4,globally stable and monotonous FSRs are constructed.According to the definition of monotonicity,one necessary and sufficient condition is obtained using the STP technique.The topological structures including fixed points and periodic attractors are dis-cussed,and then necessary condition for globally stable and monotonous FSRs is derived.One sufficient condition for globally stable and monotonous FSRs is given by destroying all the periodic attractors.Then there are 22n-2-1+2n-4 number of globally stable and monotonous FSRs with n stages,which are 22n-4/?(n)times of the existing results,where n>5 and ? represents the Euler function.In Chapter 5,the construction of filter generators based on the side channel analysis is discussed.First,the algebraic state space representation of the filter generator is obtained using the STP method.Given a binary sequence,the minimum stage of the filter generator is studied,and then the local information of the state transition matrix is determined.Based on the side channel analysis of the difference of the power consumption,all possible relations between the side information and the key sequence can be obtained.Moreover,an effective algorithm is given to determine the value of the unnecessary bits to reduce the dependence of the side information on the key sequence.Finally,the construction algorithm of filter generators is established.In Chapter 6,the topic of reducing high computational complexity is studied.On one hand,one necessary and sufficient condition is obtained by using the STP method.Then,based on the method of discrete differential,a Boolean matrix with n x n dimension is constructed,where n is the number of nodes in the network,based on which,a sufficient condition for local convergence is derived.Compared with the method of STP,the computational complexity is reduced from O(23n)to O(n2).On the other hand,the incidence matrices are used to study the fast-time stability,then compared with the STP method,the computational complexity is reduced from O(n22n)to O(n4).In addition,considering the fast stabilization problem,the pinning controllers are designed based on the neighbors of controlled nodes rather than all the nodes.In Chapter 7,finite state automaton is used to simulate a discrete event system,and then the distributed fault diagnosis problem is systematically addressed.The distributed fault diagnosis under static event observations is extended to the case of dynamic event observations.The communication model of each observation point is constructed by defining label functions and synchronization operators between finite automata.Furthermore,the global extension model and the local extension model are constructed with the help of communication models.The relations between the original model and the extension model are further analyzed.Then by defining the extended observable mapping,the fault testing automation is constructed.Finally,a necessary and sufficient condition is obtained for the distributed fault diagnosis under dynamic event observations.In Chapter 8,we summarize the above work,and make some prospects for our further work.