An Optimised Linear Attack on Pseudorandom Generators Using a Non-linear Combiner

摘要

We propose an optimised linear attack on pseudorandom generators using a nonlinear combiner. The generators consist of a number of Linear Feedback Shift Registers (LFSR) and a non linear function f(centre dot). We derive an attacking equation (AEQ) using a linear approximation of f(centre dot) and the generator polynomials of LFSRs. In the AEQ we focus on the initial value of one LFSR in the generator by eliminating the initial values of the other LFSRs using the elimination polynomial. The performance of the attack depends on the number of terms in the polynomial. We propose an optimised algorithm for an ellicient elimination polynomial. Using this attack we can determine the initial value of the LFSR from the tapped bits whose number is much smaller than the period of the pseudorandom generator.