Stream Cipbers And Analysis Of Its Complexity

This dissertation mainly investigate important measure indexes條inear complexity, k-error linear complexity and period, on the security of stream ciphers, design several fast algorithms for determining the linear complexity and k-error linear complexity of periodic sequences. The author obtains main results as follows:1.A characterization and two determinant conditioi~ of perfect secrecy of general cryptosystem are presented. Necessary and sufficient conditions for three special cryptosystems to be perfect secrecy are proved.2.A characterization of the minimal polynomials generated a sequence with given minimal period is proved, the distribution of the linear complexity of periodic sequences is shown, and a new solving process of mathematical expectation and variance of linear complexity of periodic sequences is presented. Randomness of minimal periodic sequences is discussed.3.A fast algorithm is proposed for computing the linear complexity of a binary sequence with period p? and generalized one for determining the linear complexity of a sequence with period pfl over GF(q).4.A fast algorithm for computing the linear complexity and the minimal polynomial of a binary sequence with period T抪m is proposed, and generalized one for determining the linear complexity of a sequence with period pmqfl over GF(q).5.A fast algorithm for determining the linear complexity and the minimal polynomial of a sequence with period 2pfl over GF(q) is proposed, and a new algorithm for determining the linear complexity of a sequence with period pfl over GF(p敀) IS introduced.6.Three fast algorithms for determining the k-error linear complexity of periodic sequences are proposed.7.The concept of q-ary Geffe sequence is introduced, and the period and the linear complexity of n-ary Geffe sequence are investigated.8.The period and the linear complexity of sequences generated by the q-ary shrinking generator are investigated. A new construct method of self-shrinking sequence is presented, the period and the linear complexity of sequences generated by the new method is give.