Design and Properties of a New Pseudorandom Generator Based on a Filtered FCSR Automaton

Abstract

Feedback with carry shift registers (FCSR) was introduced by Goresky and Klapper in 1993. It is similar to the classical linear feedback shift registers (LFSR) used in many pseudorandom generators. The main difference is that the elementary additions are not additions modulo 2 but with propagation of carries. The main problem for the use of an FCSR automaton is the fact that the generated sequences are predictable. In order to remove this weakness of FCSR-based generators, we propose filtering the state of the FCSR with a linear function. This method is efficient since the FCSR structure is not related to a linear property. This paper presents an extensive study of FCSR automata, a security analysis of our generator (concerning linear and 2-adic cryptanalysis, algebraic attack, correlation attack, etc.), and a practical example of parameters in order to design this generator. An important point concerning this generator is the fact that it is simple and efficient, both in hardware and software implementation.