Research On Algebraic Attack Based On Stream Cipher

With the development of new technology, information security in various fields has got more and more attentions, especially in the mobile communication field. The modern cryptography theory provides great help to protect the information security. In cryptography, stream ciphers operate on data units which are as small as a bit or several bits, so they are more suitable to be used in mobile communication field compared to block ciphers. Besides, they have relatively simple construction and easily implementation in both software and hardware, so they gain the wide attention."Algebraic attack", as the hot area of research recently, analyzes the security of the cryptographic system from a new point of view and reduces it to the difficulty of solving an over-defined system of multivariate equations. It has produced a tremendous impact on the classic design of cryptographic system.The procedure of algebraic attack includes two phases. The first one is to find the relation between the initial key and the key streams, and generate a system of multivariate equations based on the relation. The second one is to solve the system and get the initial key. In order to make the system more easily to be solved, the degree of the system is often lowered. The classic way to lower the degree of system is to generate the annihilator. As to how to solve the system of the multivariate equations, the classic algorithms include Linearization, Relinearization, XL and Grobner Bases. Most of the other algorithms are the variants of these algorithms, such asF4, F5and so on.This thesis does some research on the two aspects of algebraic attack. At first,it analyses and compares several existed methods to generate the annihilator, and gives the advantage and disadvantage for each of them. Then it comes up with a new method to generate the annihilator from a new point of view. At last it makes a study on some algorithms and puts forward a new algorithm to solve the system of multivariate equations, which applies to the situation where the known bits of the key streams are less.