On Graph Algorithms for Degeneracy Test and Recursive Description of Stream Ciphers

Abstract

Keystreams of a degenerate stream cipher can be generated by another stream cipher of less bits, and recursive description of stream ciphers is useful in cryptanalysis. Two algorithms are proposed based on directed graphs informing whether each pair of bits are related in the state transition: One tests two categories of degenerate synchronous additive stream ciphers, particularly for realistic stream ciphers with sparse transition equations; the other finds a recursive description of a given stream cipher. Specially, the latter algorithm has to balance the efficiency and the number of sequences for a recursive description, and a sufficient condition is given to test degeneracy based on the recursive description.