Skip to Main content Skip to Navigation

Revisiting LFSMs

François Arnault 1 Thierry Pierre Berger 1 Marine Minier 2 Benjamin Pousse 1 
2 SWING - Smart Wireless Networking
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
Abstract : 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.
Mots-clés : LFSMs LFSRs m-sequences
Complete list of metadata
Contributor : Marine Minier Connect in order to contact the contributor
Submitted on : Thursday, October 7, 2010 - 5:11:44 PM
Last modification on : Friday, February 4, 2022 - 3:29:54 AM


  • HAL Id : inria-00524376, version 1



François Arnault, Thierry Pierre Berger, Marine Minier, Benjamin Pousse. Revisiting LFSMs. [Research Report] 2010, pp.15. ⟨inria-00524376⟩



Record views