Some Results on FCSR Automata With Applications to the Security of FCSR-Based Pseudorandom Generators

Abstract

This article describes new theoretical results concerning the general behavior of a feedback with carry shift register (FCSR) automaton. They help to better understand how the initial parameters must be chosen to use this automaton as a basic block of a filtered stream cipher. These results especially concern the structure of the transition graph of an FCSR automaton and the number of iterations of the FCSR transition function required to reach the main part of the graph. A potential linear weakness and a easy way to prevent the corresponding attack are also given.