Stream Cipher Complexity

With the rapid development and wide application of communication and network, more and more information has been transmitted through the network. Therefore, the information security and protection are getting more and more important. The cryptography theory and technology, which aims at the information security, have become the important research fields in information science and technology. The stream cipher is one of the important branches of modern cryptography. Together with the effectively mathematical tools and the development of shift register theory has brought great progress of stream cipher theory. This dissertation mainly studies important measure indexes—linear complexity, k-error linear complexity and period, on the security of stream ciphers which are based on of feedback shift register. The main study is from several following respects:Firstly, the author studied the nonlinear complexity of periodic binary sequences which are base on feedback shift register, and considered the design of periodic binary sequences with nonlinear complexity of a given value. Besides, some forms of sequences with the minimum nonlinear complexity were searched by computer. In addition, the nonlinear complexity and linear complexity of a type of special sequences were given.Secondly, the author studied the linear complexity of periodic sequences which are base on linear feedback shift register and reads some fast algorithm of the linear complexity of periodic sequences. And the author present an efficient and attractive fast algorithm to determine the linear complexity of up~v-periodic sequence in finite field F_p under gcd(u , p ) = 1.Besides, the author pointed out how to reduce the calculation of the linear complexity of a up~v-periodic sequence to calculation of the linear complexities of certain p~v-periodic sequences. Also,calculations of the linear complexities of these p~v-periodic sequences can use the parallel program, so the calculation of the linear complexity of a up~v-periodic sequence could be much faster.Finally, by the calculation of the linear complexity of a up~v-periodic sequence reduce to calculation of the linear complexities of certain p~v-periodic sequences, the author got relation between the linear complexity and the k-error linear complexity of the up~v-periodic sequences. In addition, a necessary and sufficient condition of p~v-periodic sequences which its k-error linear complexity is strictly less than the linear complexity was also showed.