Algebraic Attacks On Nonlinear Filter Generators

Algebraic attacks have attracted cryptanalyst's attention since it had been presented, it is a powerful tool cryptanalysis tool for cryptanalysis certain ciphers especially the stream ciphers based on LFSRs. This kind of attacks can recover the secret keys by solving an overdefined group of low-degree multivariate equations. So how to establish and how to solve such equations are the key points of algebraic attacks.To resist algebraic attacks, a new design criterion of a Boolean function called algebraic immunity has been proposed. In cases where Boolean functions with high algebraic immunity are used, In order to obtain low-degree multivariate equations, probabilistic algebraic attacks had been presented by Braeken and Preneel in 2005, it recover the secret keys by solving a system of multivariate equations true with high probability, but less than 1.However, it is an open problem whether there exist some more efficient methods for solving this type of huge equations.Based on probabilistic algebraic attacks, we investigate the approach functions of a Boolean function whose algebraic immunity are lower and present an improved attack on two kinds of filter generators in this dissertation.The main results are as follows:1. We present a sufficient and necessary condition to determine the degree of annihilators and the algebraic immunity of a Boolean function by using the zero-coefficient matrix which we have proposed, estimate the low bound of linearly independent annihilators of a Boolean function, and then introduce a method to search approach functions of a Boolean function.2. We first introduce a method to solve linear p-equation systems, and then use this method to present an improved algebraic attack on filter generators whose feedback functions are with sparseness coefficients.3. We also present an improved algebraic attack on equidistant filter generators.