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
Type de document :
[Research Report] 2010, pp.15
Liste complète des métadonnées
Contributeur : Marine Minier <>
Soumis le : jeudi 7 octobre 2010 - 17:11:44
Dernière modification le : mercredi 28 février 2018 - 15:20:19


  • 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〉



Consultations de la notice