Revisiting LFSMs

Linear Finite State Machines (LFSMs) are particular primitives widely used in information theory, coding theory and cryptography. Among those linear automata, a particular case of study is Linear Feedback Shift Registers (LFSRs) studied and implemented in many cryptographic applications such as design of stream ciphers or pseudo-random generation. LFSRs could be seen as particular LFSMs without inputs. In this paper, we give first a general representation of LFSMs using traditional matrices representation linking this definition together with a new polynomial representation leading to sparse representations and implementations. As direct applications, we focus our work on the LFSRs case and show how the new LFSMs representation leads to a powerful design for LFSRs called Ring LFSRs efficient in both hardware and software. We also study a particular LFSRs subcase called windmill LFSRs used for example in the E0 stream cipher and we generalize their representation leading to better hardware performances