Study On Algebraic Attack Based On Stream Cipher And The Immunity Of Boolean Function

As a new method, algebraic attack has brought challenge to many cryptography systems. Originally, algebraic attack was used in public key cipher and group cipher. It's the first time in stream cipher when Courtois analysis the correlation characteristic of the Toyocrypt system. Subsequently, algebraic attack was extensively used in stream cipher. Due to easy implement and quickly encrypt speed, algebraic attack has been used in military affairs, business and other fields for a long time. So attack and analysis the stream cipher has many mature measures. In this paper, we firstly introduce some methods of attacking stream ciphers, and then we specialize the principium and method of algebraic attack based on stream cipher.Algebraic attack's main idea is set up the equations between the inputs and the outputs. And solving the equations and get the secret key by linearization or XL arithmetic. However with the number of variables increasing, the complexity of solving the equations is also increase. The algebraic immunity is a method for decide the ability of Boolean function to resist algebraic attack; it was defined as the degree of annihilator whose degree is the most lowness. To succeed one must found the lowness annihilators of Boolean function, and then he can decrease the complexity of solving the equations.In this paper we study the characteristic of annihilators by set theory. We get the big and small relations of algebraic immunity of multi-Boolean functions by the contain and combine relations of multi- annihilators. So the characteristic of Annihilators can affect the characteristic of algebraic immunity. And we also study the relations between the algebraic immunity and the other cryptography property, getting an expression to estimate the algebraic immunity by the weight of Boolean functions.It is very important to get the algebraic immunity for Boolean functions' design and estimating the ability of Boolean function to resist algebraic attack. In this paper we afford a new arithmetic to calculate the algebraic immunity. The arithmetic need not solving equations, so it avoids the Gauss elimination.