A Fast Cryptanalysis of the Generalized Self-shrinking Sequences
Cnis Key · JOURNAL OF ELECTRONICS INFORMATION TECHNOLOGY · 2004
An initial reconstruction algorithm is given for the generalized self-shrinking sequences using the ideas of the guessing attack.The result shows that: (1) when both the characteristic polynomial of the Linear Feedback Shift Register (LFSR) and the linear combiner are known, the algorithm ensures the cryptanalysis with complexity 0((L/2)~32~(L-l)) l≤L/2; (2) when the linear combiner is unknown, the algorithm ensures the cryptanalysis with complexity O(L~32~(2L-l)),l≤L; (3) When the characteristic polynomial of the LFSR is unknown, the algorithm ensures the cryptanalysis with complexity O(φ(2L-1)L~(-1)2~(2L-l)), l≤L. Here L is the length of the LFSR, φ is the Euler's totient function.