Breaking Modified Bruer Generator by Solving the System of Linear Equations of the Generated Sequence

Abstract

Linear Feedback Shift Register (LFSR) systems are used widely in stream cipher systems field. Golomb used the recurrence relation to find the next state values of single LFSR depending on initial values, s.t. he can be considered the first who can construct a linear equations system of a single LFSR. Attacking of key generator means attempt to find the initial values of the combined LFSR's.In this paper, a Golomb's method introduced to construct a linear equations system of a single LFSR. This method developed to construct a linear equations system of key generator (a LFSR system) where the effect of combining function of LFSR is obvious. Finally, before solving the linear equations system, the uniqueness of the solution must be tested, then solving the linear equations system using one of the classical methods like Gauss Elimination. Find the solution of linear equations system means find the initial values of the generator. One of the known generators; Modified Bruer generator, treated as a practical example of this work.