Affiliations: [a] Science and Technology on Communication Security Laboratory, Chengdu 610041, P. R. China. linwang@math.pku.edu.cn | [b] School of Mathematics and Statistics, Central South University, Changsha 410083, P. R. China. huzhi_math@csu.edu.cn
Correspondence:
[‡]
Address for correspondence: School of Mathematics and Statistics, Central South University, Changsha 410083, P. R. China.
Note: [*] supported by National Natural Science Foundation of China (Grant No. 61502441) and National Key R&D Program of China (Grant No. 2017YFB0802004).
Note: [†] supported by National Natural Science Foundation of China (Grants No. 61602526 and No. 61773404)
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.
