Registre à décalage à rétroaction linéaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Article principal : Registre à décalage.

Les registres à décalage à rétroaction linéaire, souvent notés par l'acronyme anglophone LFSR venant de Linear Feedback Shift Register dans la littérature scientifique, sont présents dans les domaines de l'informatique et plus spécialement dans les domaines du codage et de la cryptographie.

Modélisables par des fonctions mathématiques, ils peuvent être implémentés sous forme logicielle ou matérielle. Cette dernière est la plus populaire car cette solution demeure simple, peu couteuse et très efficace.

L’étendue des applications est très large : chiffrement des communications, auto-test des composants électroniques ou bien gestion des erreurs lors des copies de données.

Fonctionnement[modifier | modifier le code]

Principe[modifier | modifier le code]

Principe de base d'un registre à décalage 8 bits à rétroaction linéaire à base de XOR initialisé avec 01110101.

Un LFSR est un dispositif dérivé du registre à décalage de type SIPO, Serial In - Parallel Out, dans lequel un ou plusieurs « étages » du registre subissent une transformation pour être réinjectés en entrée de celui-ci[1].

Il est dit de longueur « r » lorsqu'il est composé de r éléments appelés « étages » ou « cellules », le contenu de l'ensemble de ces éléments à un moment « t » est l'état du LFSR à ce moment[2]. À chaque top d'horloge le contenu d'un étage est transféré au suivant et le premier est rempli par le résultat d'une fonction linéaire qui prend en compte l'état d'un ou de plusieurs étages[2].

Exemple[modifier | modifier le code]

LFSR à 4 bits[3]
Horloge État du LFSR Sortie
0 0 1 1 0 -
1 1 0 1 1 0
2 0 1 0 1 1
3 0 0 1 0 1
4 0 0 0 1 0
5 1 0 0 0 1
6 1 1 0 0 0
7 0 1 1 0 0

Exemple des états successifs d'un LFSR à 4 bits avec une connexion des premier, second et quatrième étages au niveau de la fonction de retour :

  • à t = 0 l'état initial du LFSR est 0 1 1 0 ;
  • à t = 1 le bit d'entrée vaut 1 (0 \oplus 1 \oplus 0), l'état du LFSR est 1 0 1 1 et le bit de sortie vaut 0 ;
  • à t = 2 le bit d'entrée vaut 0 (1 \oplus 0 \oplus 1), l'état du LFSR est 0 1 0 1 et le bit de sortie vaut 1 ;
  • à t = 6 le bit d'entrée vaut 1 (1 \oplus 0 \oplus 0), l'état du LFSR est 1 1 0 0 et le bit de sortie vaut 0 ;
  • à t = 7 le bit d'entrée vaut 1 (1 \oplus 1 \oplus 0), l'état du LFSR est 0 1 1 0 et le bit de sortie vaut 0.

Au septième top d'horloge l'état du registre est identique à son état initial. On dit que le LFSR est de période 7[3].

Modèles mathématiques[modifier | modifier le code]

Conception[modifier | modifier le code]

Conception d'un LFSR

Un LFSR est défini comme suit sur un corps fini \mathbb{F}_{p^n} ou p est premier et n \ge 1[4] :

  • un entier r qui est sa taille ;
  • un état initial S_{r-1} =(a_{0}, a_{1}, \ldots, a_{r-1}) à éléments sur \mathbb{F}_{p^n} ;
  • une fonction linéaire de retour f() ;
  • on calcule a_{r}=f(a_{0}, a_{1}, \ldots, a_{r-1}) ;
  • on fait entrer a_{r} et fait sortir a_{0} ;
  • on obtient une nouvelle séquence de sortie S_{r} = (a_{1}, a_{2}, \ldots, a_{r}).

Définitions[modifier | modifier le code]

Taille
Si un LFSR a {r} étages alors il est de taille {r}.
Coefficients de connexion
Soient r éléments dans \mathbb{F}_{p^n} notés c_{1}, c_{2}, ... , c_{r}. Ils sont appelés les coefficients de connexion du LFSR[5].
Fonction de retour
{f()} est définie par f(x_{1}, x_{2}, ..., x_{r-1}, x_{r}) = c_{1}x_{1} + c_{2}x_{2} + ... + c_{r-1}x_{r-1} + c_{r}x_{r}[2].
Séquence
La séquence a_{i} d'un LFSR est l'état des {r} étages à un moment {t}.
Elle satisfait la récursivité suivante : a_{i}=\sum_{j=1}^{j=r} c_{j}a_{i-j}i \geqq r[5].
On peut la trouver aussi écrite sous la forme suivante : a_{i+n}=\sum_{j=0}^{n-1} c_{i}a_{i+j}[1].
Triplet
Un LFSR peut être défini comme un triplet {L} = \Bigl(\mathbb{F}_{p^n}, r, (c_{1}, c_{2}, ... , c_{r})\Bigr) ou {L} = \Bigl(\mathbb{F}_{p^n}, r, f()\Bigr)[5].
Fonction génératrice
L'étude d'un LFSR via les séries formelles permet de connaître sa fonction génératrice. Elle est définie par A(X) = \sum_{i=0}^{\infty} a_{i}X^{i} sur \mathbb{F}_{p^n}[[X]][6],[7].

En général, on construit les LFSRs sur \mathbb{F}_{2} = \{0, 1\} et f() est alors une fonction booléenne.

Représentations polynomiales[modifier | modifier le code]

Polynôme de rétroaction
Soit un LFSR {L} défini par le triplet \Bigl(\mathbb{F}_{p^n}, r, (c_{1}, c_{2}, ... , c_{r})\Bigr). Son polynôme de rétroaction, appelé aussi polynôme caractéristique, est T(X) = 1 + \sum_{i=1}^{r} c_{i}X^{i}[8].
Exemple : Un LFSR {L} = \Bigl(\mathbb{F}_{2}, 7, (1, 0, 1, 1, 0, 0, 1)\Bigr) aura comme polynôme de rétroaction T(X) = 1 + X^7 + X^4 + X^3 + X^1.


Polynôme de connexion
Pour un LFSR défini par le triplet {L} = \Bigl(\mathbb{F}_{p^n}, r, (c_{1}, c_{2}, ... , c_{r})\Bigr), le polynôme de connexion est q(X) = \sum_{i=1}^{r} c_{i}X^{i} - 1 dans \mathbb{F}_{p^n}[[X]][6],[7].
Exemple : Un LFSR {L} = \Bigl(\mathbb{F}_{2}, 7, (1, 0, 1, 1, 0, 0, 1)\Bigr) aura comme polynôme de connexion q(X) = X^7 + X^4 + X^3 + X^1 - 1.

Périodicité[modifier | modifier le code]

Puisque la prochaine valeur d'entrée d'un LFSR dépend uniquement des valeurs de certains étages de celui-ci et que l'état « tout à zéro » ne génère jamais de changement sa séquence est de période maximale q^{r}-1 sur \mathbb{F}_{q}{r} est la taille du registre[9],[10].

Une séquence d'un LFSR sur \mathbb{F}_{q} avec une période q^{r}-1{r} est la taille du registre est appelé une « m-sequence (en) »[3],[9].

Exemple : Un LFSR {L} = \Bigl(\mathbb{F}_{2}, 7, (1, 0, 1, 1, 0, 0, 1)\Bigr) aura une période maximale de 2^{7}-1 = 127.

Algorithme de Berlekamp-Massey[modifier | modifier le code]

Introduit en 1969 par James Massey l'algorithme de Berlekamp-Massey (en) permet d'obtenir le plus petit LFSR possible pour une séquence de sortie choisie[11]. Il suffit de capter {2}{r} bits consécutifs d'une m-séquence de période {2}^{r}-1 pour pouvoir reconstruire la séquence entièrement[12].

Description de l'algorithme[13] :

En entrée : les 2n éléments d'une séquence récurrente de manière linéaire définie sur \mathbb{K} avec n \in \N donnés par la liste (a_{0}, a_{1}, \ldots, a_{2n-1}). Le polynôme minimal est de degré limite n.

En sortie : le polynôme P(x) caractéristique minimal de la séquence.

Début

Variables locales
R, R_{0}, R_{1}, V, V_{0}, V_{1}, Q sont des polynômes de x.
Initialisation
R_{0} := x^{2n}; \quad R_{1} := \sum_{i=0}^{2n-1} a_{i}x^{i}; \quad V_{0} = 0; \quad V_{1} = 1;
Boucle, tant que n \leqslant deg(R1) faire :
Q := quotient de la division de R_{0} par R_{1};
R := reste de la division de R_{0} par R_{1};
V := V_{0} - QV_{1}
V_{0} := V_{1}
V_{1} := V
R_{0} := R_{1}
R_{1} = R
Fin boucle
d := max\Bigl(deg(V_{1}), 1 + deg(R_{1})\Bigr); \quad P := x^{d}V_{1}(1/x);
Retour
P := P/\text{leadcoeff}(P).

Fin

Modes de connexion[modifier | modifier le code]

Le mode le plus naturel pour représenter la connexion entre les différents étages du registre est le mode dit de « Fibonacci ». Il est appelé ainsi car la suite de Fibonacci se représente dans ce mode. En 2002 Andy Klapper et Mark Goresky (en) mettent en place le mode dit de « Galois »[14],[15].

Fibonacci[modifier | modifier le code]

LFSR de Fibonacci à 8 bits
LFSR de Fibonacci à 8 bits

Un registre en mode Fibonacci applique strictement la définition d'un LFSR : les contenus des différents étages sont ajoutés ou non les uns aux autres, le résultat de cette addition est ensuite placé dans l'étage d'entrée du registre et tous les étages subissent un décalage vers la sortie[14],[16].

Galois[modifier | modifier le code]

Exemple d'un LFSR Galois à 8 bits
Exemple d'un LFSR Galois à 8 bits

Dans le mode dit de Galois le contenu de l'étage de sortie est ajouté ou non au contenu des étages du registre puis tous les étages subissent un décalage vers la sortie et le contenu de l'étage sortant est réinjecté dans l'étage d'entrée[17].

Au niveau matériel les LFSRs sont souvent mis en œuvre en utilisant ce mode car celui-ci est plus rapide et présente moins de latence que le mode Fibonacci puisque les étages sont mis à jour simultanément[18],[19].

Applications[modifier | modifier le code]

Les LFSRs existent sous deux formes: matérielle et logicielle, mais c'est surtout la première configuration qui est utilisée car elle est simple à mettre en œuvre (matériel peu onéreux associé à un algorithme de traitement simple)[15].

L'usage de cette technologie peut se retrouver dans les domaines suivants[3] :

Génération de nombres pseudo-aléatoires[modifier | modifier le code]

Il y a eu beaucoup de publications à propos de la génération des nombres pseudo-aléatoires par les registres à décalage et à part quelques études sur les registres à rétroaction non linéaires (en), la majorité des auteurs utilisent la rétroaction linéaires[2].

Un problème fondamental en cryptologie est la production de suites de bits « aussi aléatoires que possible ». Un exemple évident étant la génération des clefs de chiffrement (symétrique ou asymétrique)[20].

Ce problème se décompose en fait en deux parties :

  • La génération de bits par des procédés physiques, dans le cas d'un ordinateur des mesures liées à l'activité de la machine (températures interne, déplacement de la souris, etc.)
  • L'expansion d'une courte suite aléatoire de bits en une suite éventuellement beaucoup plus grande; Dans ce dernier cas, on parle de suite pseudo-aléatoire.

Chiffrement des données[modifier | modifier le code]

Cryptographie[modifier | modifier le code]

Article détaillé : Cryptographie.
Schéma du A5/1 et ses trois registres à décalage. Un registre est décalé si le bit en orange correspond à la majorité des trois bits orange. On insère alors un bit correspondant à un XOR entre les bits en bleu.
Schéma d'un tour de RC4

Les générateurs pseudo-aléatoires à base de LFSR sont utilisés dans les chiffrements de flux que l'on retrouve sous le terme anglais cipher stream[21], ils constituent avec les chiffrements par bloc les 2 grandes catégories modernes du chiffrement symétrique de la cryptographie.

Les LFSRs sont les composants de base de nombreux générateurs chiffrants[22].

Les raisons pour lesquels les LFSRs sont utilisés dans un grand nombre de générateurs de flux de sont les suivantes[22] :

  • Les LFSRs sont bien adaptés à une configuration matérielle ;
  • Ils peuvent produire des grandes périodes de séquences binaires ;
  • Les séquences produites ont des bonnes propriétés statistiques ;
  • En raison de leur nature, ils peuvent être facilement analysés en utilisant des modèles mathématiques.


Cependant, l'utilisation des LFSRs dans leur configurations initiales est devenue très vite vulnérable aux attaques mathématiques (démontré par l'algorithme de Berlekamp-Massey).


Un système informatique pour ne pas être vulnérable doit être sécurisé contre les attaques connues et référencées, c'est pourquoi un LFSR ne doit jamais être utilisé par lui-même comme un générateur de flux de clés[23].

Néanmoins, les LFSRs restent encore utilisés en raison de leurs coûts de mise en œuvre très bas[23].


Trois méthodes peuvent être employées pour contourner l'effet des propriétés de linéarité des LFSRs[23] :

  • Associer une fonction non linéaire aux sorties de plusieurs LFSRs ;
  • Utiliser une fonction de filtrage non linéaire basé sur le contenu d'un seul LFSR ;
  • Utiliser plusieurs LFSRs en parallèle ou une horloge externe qui peut provenir d'un autre LFSR[24].


Les propriétés attendues d'un générateur de flux de chiffrement sont[23] :

  • Une grande période ;
  • Grande complexité linéaire ;
  • Bonnes propriétés statistiques.


Exemples d'algorithmes cryptographiques utilisant les LFSRs :

Stéganographie[modifier | modifier le code]

Article détaillé : Stéganographie.
génération d'une image stéganographie avec FPGA


La stéganographie est la technique qui permet de cacher de l'information, le plus souvent un texte dans des images, une des méthodes est de remplacer le bit de poids faible de chaque pixel formant l'image par un autre bit d'information[26].

Les séquences pseudo-aléatoires à base de LFSRs sont une des méthodes de cryptage de l'information[26].

Embarqués dans des circuits logiques programmables tels que les FPGA[note 4], ils répondent à un besoin croissant de cacher l'information[27].

Détection d'erreurs et correction de données[modifier | modifier le code]

Plusieurs type de CRC selon les applications[3]
Application Type taille LFSR
CRC CRC-12 12
CRC-16 16
Réseau ATM[note 5] CRC-32 32


Ce mécanisme que l'on appelle contrôle de redondance cyclique et que l'on retrouve sous le nom de CRC[note 6] est un dispositif de contrôle d'erreur lors des transmissions de données brutes dans le domaine du réseau, le stockage numérique ou encore dans la compression de donnée[28].

Les composants hardware LFSR sont un des moyens facile et bon marché pour générer des suite pseudo-aléatoire utilisées par ces procédés[28].

Auto-contrôle des circuits électronique[modifier | modifier le code]

Le test des circuits électroniques a été longtemps problématique car les solutions existantes donnant des temps de réponses corrects étaient souvent très onéreuses. Le coût n'est pas le seul problème, il faut aussi que le dispositif puisse répondre à 2 problématiques[29] :

  • Le temps : Il ne faut pas que le mécanisme consomme trop de temps à générer l'échantillonnage de test au détriment de l'efficacité du composant ;
  • Le volume de donnée : La taille de échantillonnage peut devenir tellement grande que le test n'est plus efficace.

La technologie BIST[note 7] est une méthode de test des composants électroniques qui s'appuie sur plusieurs mécanismes[30] :

  • Technique de parité ;
  • Technique de comptage ;
  • LFSRs.

Les tests aléatoires sur une partie du composant suppose de pouvoir agir sur un échantillonnage des données du composant[31].

Traitement numérique du signal[modifier | modifier le code]

C'est l’étude du traitement du signal numérisé tel que le filtrage ou la compression, elle est assurée par un processeur de signal numérique que l'on retrouve indiqué dans ce domaine par DSP[note 8]. Ces opérations seraient difficilement réalisables directement sur les données binaires en mémoire sans algorithme de compression/décompression.

Les LFSRs sont fréquemment utilisés pour cette tache car ils sont efficaces dans le traitement de grande quantité de données binaires et ils ont un faible cout d’implémentation dans leurs formes matériels [32].

Compteurs à base de LFSRs[modifier | modifier le code]

Les Compteurs binaires (en) sont des composants qui sont utilisés couramment dans des équipements nécessitant un comptage comme par exemple les montres digitales ou les chronomètres.

Un LFSR est un type spécial de compteur qui génère une séquence pseudo-aléatoire, il peut être utilisé en remplacement des compteurs binaires traditionnels[33].

Exemples d'utilisation[34]:

  • Compteurs à incrément ou décrément 'up/down counters' ;
    • Down counters - commence à w/ 111 ;
    • Utilise une porte 'XOR' pour la retroaction ;
    • L'initialisation ne doit pas être que des zéros.
  • 'Up counters' commence à w/ 000.

Utilisation du XNOR

Avantages[35] Inconvénients[35]
Nécessite peu de logique pour être mis en place ;
  • Les compteurs avec des grandes valeurs restent efficaces ;
    • Pas de besoin d'un nombre élevé de portes logiques ;
    • Ils sont très rapides.
  • Les erreurs sont détectables typiquement un timer 2*n.
  • Besoin d'initialiser le registre pour avoir un état valide ;
  • Certaines applications ont besoin d'une séquence binaire ;
  • Pas de moyen simple de prédire la séquence de comptage.

Autres utilisations des LFSRs[modifier | modifier le code]

L'industrie du jeu vidéo a utilisé le LFSR au travers d'un composant qui est le SN76489, on a pu ainsi sonoriser certaines consoles de jeux vidéo grâce à ce circuit électronique[36].

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. GSM pour Global System for Mobile Communications, historiquement Groupe Spécial Mobile
  2. SSL pour Secure Sockets Layer
  3. WEP pour Wired Equivalent Privacy
  4. FPGA pour Field-Programmable Gate Array
  5. ATM pour Asynchronous Transfer Mode
  6. CRC pour Cyclic Redundancy Check
  7. BIST pour Built-In Self-Test
  8. DSP pour Digital Signal Processor

Références[modifier | modifier le code]

  1. a et b Klein 2013, p. 17
  2. a, b, c et d Cagigal 1986, p. 191
  3. a, b, c, d et e Ahmad 2003, p. 2
  4. Marjane 2011, p. 80-81
  5. a, b et c Marjane 2011, p. 81
  6. a et b Klein 2013, p. 19
  7. a et b Marjane 2011, p. 83
  8. Ahmad 2003, p. 3
  9. a et b Klein 2013, p. 18
  10. Moon 2005, p. 154
  11. Reeds 1985, p. 505
  12. Marjane 2011, p. 14
  13. Ben Atti 2006, p. 76
  14. a et b Marjane 2011, p. 22
  15. a et b Lauradoux 2007, p. 2
  16. Goresky 2002, p. 2827
  17. Goresky 2002, p. 2828
  18. Joux 2006, p. 437
  19. Marjane 2011, p. 152
  20. Bresson 2011, p. 11
  21. Menezes 1996, p. 191
  22. a et b Menezes 1996, p. 195
  23. a, b, c et d Menezes 1996, p. 204
  24. Chambers 1988, p. 17
  25. Kitsos 2001, p. 991
  26. a et b Gamil 2002, p. 239
  27. Sundararaman 2011, p. 24
  28. a et b PATEL 1971, p. 11
  29. McCluskey 1985, p. 21
  30. McCluskey 1985, p. 25
  31. Breuer 1988, p. 933
  32. Lauradoux 2007, p. 1
  33. Ajane 2011, p. 1
  34. Chen 2010, p. 3
  35. a et b Chen 2010, p. 8
  36. [[#A53|]], p. 1

Bibliographie[modifier | modifier le code]

Document utilisé pour la rédaction de l’article : document utilisé comme source pour la rédaction de cet article.

  • (en) W. Liang et Jing Long, « A cryptographic algorithm based on Linear Feedback Shift Register », Computer Application and System Modeling (ICCASM), 2010 International Conference on,‎ 22-24 octobre 2010 (DOI 10.1109/ICCASM.2010.5622523) Document utilisé pour la rédaction de l’article
  • (en) Bernard Elspas, « The Theory of Autonomous Linear Sequential Networks », Circuit Theory, IRE Transactions on,‎ mars 1959, p. 45-60 (ISSN 0096-2007, DOI 10.1109/TCT.1959.1086506) Document utilisé pour la rédaction de l’article
  • (en) N.P. Cagigal et S. Bracho, « Algorithmic determination of linear-feedback in a shift register for pseudorandom binary sequence generation », Electronic Circuits and Systems, IEE Proceedings G,‎ août 1986, p. 191-194 (ISSN 0143-7089, DOI 10.1049/ip-g-1:19860031) Document utilisé pour la rédaction de l’article
  • (en) Lauradoux, « From Hardware to Software Synthesis of Linear Feedback Shift Registers », Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International,‎ 26-30 mars 2007, p. 1-8 (DOI 10.1109/IPDPS.2007.370643) Document utilisé pour la rédaction de l’article
  • (en) M. Scaffardi, G. Berrettin et A.T Nguyen, « Optical linear feedback shift register », Lasers and Electro-Optics Europe (CLEO EUROPE/EQEC), 2011 Conference on and 12th European Quantum Electronics Conference,‎ 22-26 mai 2011, p. 1 (ISSN 978-1-4577-0533-5, DOI 10.1109/CLEOE.2011.5942992)
  • (en) « A multiple seed linear feedback shift register », Computers, IEEE Transactions on,‎ février 1992, p. 250-252 (ISSN 0018-9340, DOI 10.1109/12.123404)
  • (en) « Linear feedback shift register design using cyclic codes », Computers, IEEE Transactions on,‎ octobre 1988, p. 1302-1306 (ISSN 0018-9340, DOI 10.1109/12.5994)
  • (en) « Deterministic built-in self-test using multiple linear feedback shift registers for test power and test volume reduction », Computers & Digital Techniques, IET,‎ juillet 2010, p. 317-324 (ISSN 1751-8601, DOI 10.1049/iet-cdt.2009.0092)
  • (en) « Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm », IBM Journal of Research and Development,‎ mai 1976, p. 204-212 (ISSN 0018-8646, DOI 10.1147/rd.203.0204)
  • (en) D.G. Maritsas, A.C. Arvillias et A.C. Bounas, « Phase-Shift Analysis of Linear Feedback Shift Register Structures Generating Pseudorandom Sequences », Computers, IEEE Transactions on,‎ juillet 1978, p. 660-669 (ISSN 0018-9340, DOI 10.1109/TC.1978.1675166)
  • (en) Arvind M Patel, « A multi-channel CRC register », AFIPS '71 (Spring) Proceedings of the May 18-20, 1971, spring joint computer conference,‎ 18 mai 1971, p. 11-14 (DOI 10.1145/1478786.1478789)
  • (en) J. Lawrence Carter, « The theory of signature testing for VLSI », STOC '82 Proceedings of the fourteenth annual ACM symposium on Theory of computing,‎ 5 mai 1982, p. 66-76 (DOI 10.1145/800070.802178)
  • (en) W.B. Jone et C.A. Papachristou, « A coordinated approach to partitioning and test pattern generation for pseudoexhaustive testing », DAC '89 Proceedings of the 26th ACM/IEEE Design Automation Conference,‎ juin 1989, p. 525-534 (DOI 10.1145/74382.74470)
  • (en) Salvatore Filippone, Paolo Santangelo et Marcello Vitaletti, « A vectorized long-period shift-register random number generator », Supercomputing '90: Proceedings of the 1990 ACM/IEEE conference on Supercomputing,‎ octobre 1990, p. 676-684
  • (en) Li-Ren Huang, Sy-Yen Kuo et Ing-Yi Chen, « A Gauss-elimination based PRPG for combinational circuits », EDTC '95 Proceedings of the 1995 European conference on Design and Test,‎ 6 mars 1995, p. 212
  • (en) Laurence Goodby et Alex Orailoğlu, « Pseudorandom-pattern test resistance in high-performance DSP datapaths », DAC '96 Proceedings of the 33rd annual Design Automation,‎ juin 1996, p. 813-818 (DOI 10.1145/240518.240671)
  • (en) D.V. Sarwate, « Mean-square correlation of shift-register sequences », Communications, Radar and Signal Processing, IEE Proceedings F,‎ avril 1984, p. 101-106 (ISSN 0143-7070, DOI 10.1049/ip-f-1:19840018)
  • (en) Ahmad Zawawi, Bin Seman Kamaruzzaman et Nurzi Juana Mohd Zaizi, « Randomness analysis on grain - 128 stream cipher », International Conference on Mathematical Sciences and Statistics 2013,‎ 5-7 février 2013 (DOI 10.1063/1.4823866)
  • (en) A. Ahmad, Sameer Al-Busaidi et Ahmed Al-Naamany, Measurement techniques of lfsr sequences,‎ mars 2003 Ouvrage utilisé pour la rédaction de l'article
  • (en) M. Goresky et A.M. Klapper, « Fibonacci and Galois representations of feedback-with-carry shift registers », Information Theory, IEEE Transactions on,‎ novembre 2002, p. 2826-2836 (ISSN 0018-9448, DOI 10.1109/TIT.2002.804048) Document utilisé pour la rédaction de l’article
  • (en) Andreas Klein, « Linear Feedback Shift Registers », Stream Ciphers,‎ 20 avril 2013, p. 17-58 (DOI 10.1007/978-1-4471-5079-4) Document utilisé pour la rédaction de l’article
  • (en) J.L. Massey, « Shift-Register Syntheses and BCH Decoding », Information Theory, IEEE Transactions on,‎ janvier 1969, p. 122-127 (ISSN 0018-9448, DOI 10.1109/TIT.1969.1054260)
  • Anne Canteaut, Attaques de cryptosystèmes à mots de poids faible et construction de fonctions t-résilientes,‎ 10 octobre 1996, 147-167 p. (lire en ligne)
  • (en) P.H. Bardell et W.H. McAnney, « Pseudorandom Arrays for Built-In Tests », Computers, IEEE Transactions on,‎ juillet 1986, p. 653-658 (ISSN 0018-9340, DOI 10.1109/TC.1986.1676810)
  • (en) T.K. Moon, « Chapter 4. Cyclic Codes, Rings, and Polynomials », Error Correction Coding: Mathematical Methods and Algorithms,‎ 27 juin 2005, p. 154-170 (DOI 10.1002/0471739219.ch4) Document utilisé pour la rédaction de l’article
  • (en) Dai Zongduo et Wan Zhexian, « A relationship between the Berlekamp-Massey and the euclidean algorithms for linear feedback shift register synthesis », Acta Mathematica Sinica,‎ 1er mars 1988, p. 55-63 (ISSN 1439-8516, DOI 10.1007/BF02560313)
  • (en) Nadia Ben Atti, Gema M. Diaz–Toca et Henri Lombardi, « The Berlekamp-Massey Algorithm revisited », Applicable Algebra in Engineering, Communication and Computing,‎ avril 2006, p. 75-82 (ISSN 0938-1279, DOI 10.1007/s00200-005-0190-z) Document utilisé pour la rédaction de l’article
  • (en) S.B. Gashkov et I.B. Gashkov, « Berlekamp—Massey Algorithm, Continued Fractions, Pade Approximations, and Orthogonal Polynomials », Mathematical Notes,‎ 2006, p. 41-54 (ISSN 0001-4346, DOI 10.1007/s11006-006-0004-z)
  • (en) Antoine Joux et Pascal Delaunay, « Galois LFSR, Embedded Devices and Side Channel Weaknesses », Progress in Cryptology - INDOCRYPT 2006,‎ 2006, p. 436-451 (ISSN 0302-9743, DOI 10.1007/11941378_31) Document utilisé pour la rédaction de l’article
  • Abdelaziz Marjane, Conception Vectorielle de Registre à rétroaction avec retenue sur les corps finis,‎ 8 juillet 2011 (lire en ligne) Ouvrage utilisé pour la rédaction de l'article
  • (en) J.A. Reeds et J.A. Sloane, « Shift Register Synthesis (Modulo m) », SIAM Journal on Computing,‎ août 1985, p. 505-513 (ISSN 00975397, DOI 10.1137/0214038) Document utilisé pour la rédaction de l’article
  • (en) T.N. Rajashekhara, « Signature analyzers in built-in self-test circuits: a perspective », Southern Tier Technical Conference,‎ 25 avril 1990, p. 275-281 (DOI 10.1109/STIER.1990.324654)
  • (en) M. Koutsoupia, E. Kalligeros et X. Kavousianos, « LFSR-based test-data compression with self-stoppable seeds », Design, Automation & Test in Europe Conference & Exhibition,‎ 20-24 avril 2009, p. 1482-1487 (ISSN 1530-1591, DOI 10.1109/DATE.2009.5090897)
  • (en) A. Ajane, P.M. Furth et E.E. Johnson, « Comparison of binary and LFSR counters and efficient LFSR decoding algorithm », Circuits and Systems (MWSCAS), 2011 IEEE 54th International Midwest Symposium on,‎ 07/10/2013 août 2011, p. 1548-3746 (ISSN 1548-3746, DOI 10.1109/MWSCAS.2011.6026392) Document utilisé pour la rédaction de l’article
  • (en) H Rizk, C Papachristou et F Wolff, « Designing self test programs for embedded DSP cores », Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings,‎ 16-20 février 2004, p. 816 - 821 (ISSN 1530-1591, DOI 10.1109/DATE.2004.1268982)
  • (en) T. Jamil et A. Ahmad, « An investigation into the application of linear feedback shift registers for steganography », SoutheastCon, 2002. Proceedings IEEE,‎ 5 juin 2002, p. 239-244 (DOI 10.1109/.2002.995594)
  • (en) T Siegenthaler, « Decrypting a Class of Stream Ciphers Using Ciphertext Only », Computers, IEEE Transactions on,‎ janvier 1985, p. 81 - 85 (ISSN 0018-9340, DOI 10.1109/TC.1985.1676518)
  • (en) J. E. Meggitt, « Error correcting codes and their implementation for data transmission systems », Information Theory, IRE Transactions on,‎ octobre 1961, p. 234-244 (ISSN 0096-1000, DOI 10.1109/TIT.1961.1057659)
  • (en) R. David, « Testing by Feedback Shift Register », Computers, IEEE Transactions on,‎ juillet 1980, p. 668-673 (ISSN 0018-9340, DOI 10.1109/TC.1980.1675641)
  • (en) W. Daehn et J. Mucha, « A hardware approach to self-testing of large programmable logic arrays », Circuits and Systems, IEEE Transactions on,‎ novembre 1981, p. 1033-1037 (ISSN 0098-4094, DOI 10.1109/TCS.1981.1084933)
  • (en) S. Pupolin et Carlo Tomasi, « Moments of the Weights of Pseudo-Noise Subsequences », Military Communications Conference - Progress in Spread Spectrum Communications, 1982. MILCOM 1982. IEEE,‎ 17-20 octobre 1982, p. 15.3-1-15.3-4 (DOI 10.1109/MILCOM.1982.4805920)
  • (en) T. Siegenthaler, « Decrypting a Class of Stream Ciphers Using Ciphertext Only », Computers, IEEE Transactions on,‎ janvier 1985, p. 81-85 (ISSN 0018-9340, DOI 10.1109/TC.1985.1676518)
  • (en) E.J. McCluskey, « Built-In Self-Test Techniques », Design & Test of Computers, IEEE,‎ avril 1985, p. 21-28 (ISSN 0740-7475, DOI 10.1109/MDT.1985.294856)
  • (en) W.G. Chambers, « Clock-controlled shift registers in binary sequence generators », Computers and Digital Techniques, IEE Proceedings E,‎ janvier 1988, p. 17-24 (ISSN 0143-7062)
  • (en) S. Sastry et M. Breuer, « Detectability of CMOS stuck-open faults using random and pseudorandom test sequences », Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on,‎ septembre 1988, p. 933-946 (ISSN 0278-0070, DOI 10.1109/43.7792)
  • (en) A. Ahmad, N. Nanda et K. Garg, « The use of irreducible characteristic polynomials in an LFSR based testing of digital circuits », TENCON '89. Fourth IEEE Region 10 International Conference,‎ 22-24 novembre 1989, p. 494-496 (DOI 10.1109/TENCON.1989.176866)
  • (en) P. Kitsos, « A reconfigurable linear feedback shift register (LFSR) for the Bluetooth system », Electronics, Circuits and Systems, 2001. ICECS 2001. The 8th IEEE International Conference on (Volume:2 ),‎ 2001, p. 991 - 994 (ISSN 0-7803-7057-0, DOI 10.1109/ICECS.2001.957640)
  • (en) Yuhua Chen, Linear Feedback Shift Register (LFSR) Counters,‎ 2010 (lire en ligne) Ouvrage utilisé pour la rédaction de l'article
  • (en) An Implementation Of The Noise Shift Register (lire en ligne) Ouvrage utilisé pour la rédaction de l'article
  • (en) A. Menezes et P. van Oorschot, Handbook of Applied Cryptography,‎ 1996, 191-222 p. (lire en ligne) Ouvrage utilisé pour la rédaction de l'article
  • (en) E. Bresson, Cryptographie-chiffrement par flot,‎ 2007, 1-53 p. (lire en ligne) Ouvrage utilisé pour la rédaction de l'article
  • (en) R. Sundararaman, Stego System on chip with LFSR based Information Hidin Approach,‎ mars 2011, 24-31 p. (lire en ligne) Ouvrage utilisé pour la rédaction de l'article

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]