Revisiting LFSMs

François Arnault 1 Thierry Pierre Berger 1 Marine Minier 2 Benjamin Pousse 1
1 DMI
XLIM - XLIM
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 :
Rapport
[Research Report] 2010, pp.15
Liste complète des métadonnées

https://hal.inria.fr/inria-00524376
Contributeur : Marine Minier <>
Soumis le : jeudi 7 octobre 2010 - 17:11:44
Dernière modification le : jeudi 11 janvier 2018 - 06:26:18

Identifiants

  • HAL Id : inria-00524376, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

281