2005 | OriginalPaper | Chapter
Cryptanalysis of Keystream Generator by Decimated Sample Based Algebraic and Fast Correlation Attacks
Authors : Miodrag J. Mihaljević, Marc P. C. Fossorier, Hideki Imai
Published in: Progress in Cryptology - INDOCRYPT 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper proposes a novel approach for cryptanalysis of keystream generators consisting of the composition of a linear finite state machine (LFSM) and nonlinear mapping. The proposed approach includes a dedicated decimation of the sample for cryptanalysis based on the following: Suppose certain
B
bits of the LFSM initial state as known and identify time instances where certain arguments of the nonlinear function depend only on these
B
bits and are equal to zero. As opposed to previously reported methods, the proposed one also identifies and uses certain characteristics of the LFSM state-transition matrix in order to reduce the nonlinearity of the system of overdefined equations employed in an algebraic attack scenario, or to reduce the noise introduced by the linearization of the nonlinear function which corrupts the linear equations employed in a correlation attack scenario. The proposed method is employed for developing efficient algorithms for cryptanalysis of the nonlinear combination keystream generator reported at INDOCRYPT 2004.