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

Un registre à décalage à rétroaction linéaire, ou LFSR (sigle de l'anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite de bits qui peut être vue comme une suite récurrente linéaire sur le corps fini F₂ à 2 éléments (0 et 1). La notion a été généralisée à n'importe quel corps fini.

Réalisé électroniquement, dans le cas particulier d'une suite de 0 et de 1, c'est un registre à décalage avec rétroaction linéaire, ce qui signifie que le bit entrant est le résultat d'un OU exclusif (ou XOR) entre plusieurs bits du registre, cette opération étant également l'addition sur le corps fini F₂. Ces dispositifs sont simples, peu coûteux et efficaces.

La suite récurrente produite par un LFSR est nécessairement périodique à partir d'un certain rang. Les LFSR sont utilisés en cryptographie pour engendrer des suites de nombres pseudo-aléatoires. La fonction de rétroaction est alors choisie de façon à obtenir une période la plus grande possible.

L’étendue des applications est très large : chiffrement des communications, contrôle d'erreurs sur la transmission de données, auto-test des composants électroniques…

Schéma de fonctionnement d'un LFSR : le bit de rétroaction est obtenu par XOR sur une sélection des bits du registre.

Fonctionnement[modifier | modifier le code]

Principe[modifier | modifier le code]

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^[3] :

à $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=3$ le bit d'entrée vaut 0 $(0\oplus 1\oplus 1)$ , l'état du LFSR est 0 0 1 0 et le bit de sortie vaut 1 ;
à $t=4$ le bit d'entrée vaut 0 $(0\oplus 0\oplus 0)$ , l'état du LFSR est 0 0 0 1 et le bit de sortie vaut 0 ;
à $t=5$ le bit d'entrée vaut 1 $(0\oplus 0\oplus 1)$ , l'état du LFSR est 1 0 0 0 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 0 $(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.

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

Conception[modifier | modifier le code]

Un LFSR est défini comme suit sur un corps fini $\mathbb {F} _{p^{n}}$ ou $p$ est premier et $n\geq 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]

Un LFSR peut être défini comme un triplet ${L}={\Bigl (}\mathbb {F} _{q},r,(c_{1},c_{2},...,c_{r}){\Bigr )}$ , où F_q est le corps fini à q éléments, r est le nombre de cellules du LFSR, les coefficients c₁, …, c_r sont des éléments de F_q^[5].

Suite engendrée: La suite engendrée par ce LFSR est une suite $(a_{n})_{n\in \mathbb {N} }$ vérifiant la relation de récurrence

$a_{n}=\sum _{i=1}^{i=r}c_{i}a_{n-i}$ , pour $n\geq r$ ^[5]
ou de façon équivalente
$a_{r+n}=\sum _{j=0}^{r-1}c_{r-j}a_{n+j}$ ^[1].

Taille: La taille du LFSR est r le nombre de cellules.
Coefficients de connexion: les coefficients c₁, …, c_r sont appelés les coefficients de connexion du LFSR^[5].
Fonction de retour ou de rétroaction: La fonction f 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}$
est appelée fonction de retour ou de rétroaction du LFSR^[2]. Quand q=2, F₂ est le corps des booléens et f est une fonction booléenne (linéaire).
Fonction génératrice: La fonction génératrice de la suite engendrée par un LFSR sur le corps F_q est la série formelle de F_q [[X]] définie par^[6]^,^[7]
$A(X)=\sum _{n=0}^{\infty }a_{n}X^{n}$

Représentations polynomiales[modifier | modifier le code]

Cette section a besoin d'être recyclée (février 2015).
Une réorganisation et une clarification du contenu sont nécessaires.

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^{1}+X^{3}+X^{4}+X^{7}$ .

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]

Cette section a besoin d'être recyclée (février 2015).
Une réorganisation et une clarification du contenu sont nécessaires.

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}$ où ${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$ où ${r}$ est la taille du registre est appelé une « m-sequence »^[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 \mathbb {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]

La représentation employée jusqu'ici pour représenter la connexion entre les différents étages du registre décrit le mode dit de « Fibonacci ». Une autre représentation est possible, utilise le mode dit de « Galois »^[14].

Fibonacci[modifier | modifier le code]

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^[15].

Galois[modifier | modifier le code]

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^[16].

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^[17]^,^[18].

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)^[14].

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

Générateur de nombres pseudo-aléatoires ;
Algorithmes de chiffrement des données (Cryptographie, Stéganographie) ;
Détection d'erreurs et correction de données ;
Auto-contrôle des circuits électroniques ;
Traitement numérique du signal ;
Compteurs à base de LFSRs ;
Autres utilisations des LFSRs (Jeux vidéo, radar…).

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

Article détaillé : Générateur de nombres pseudo-aléatoires.

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éaire^[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)^[19].

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.

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^[20], 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^[21].

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

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^[22].

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

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

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^[23].

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

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

Exemples d'algorithmes cryptographiques utilisant les LFSRs :

Codage/décodage des transmissions des téléphones cellulaires
A5/1 : chiffrement des communications GSM^{[note 1]}, il utilise 3 LFSRs de 19, 22 et 23 bits (64 bits au total) ;
Codage du Bluetooth
E0 : protocole de codage du Bluetooth utilisant quatre LFSR de longueurs 25, 31, 33, et 39 bits (128 bits au total)^[24].

Stéganographie[modifier | modifier le code]

Article détaillé : Stéganographie.

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^[25].

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

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

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

Plusieurs types de CRC selon les applications^[3]
Application	Type	taille LFSR
CRC	CRC-12	12
	CRC-16	16
Réseau ATM^{[note 3]}	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 4]} 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^[27].

Les composants hardware LFSR sont un des moyens faciles et bon marché pour générer des suites pseudo-aléatoires utilisées par ces procédés^[27].

Auto-contrôle des circuits électroniques[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^[28] :

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 5]} est une méthode de test des composants électroniques qui s'appuie sur plusieurs mécanismes^[29] :

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^[30].

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 6]}. 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 ^[31].

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

Les compteurs binaires 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^[32].

Exemples d'utilisation^[33]:

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^[34]	Inconvénients^[34]
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^[35].

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

Notes[modifier | modifier le code]

↑ GSM pour Global System for Mobile Communications, historiquement Groupe Spécial Mobile
↑ FPGA pour Field-Programmable Gate Array
↑ ATM pour Asynchronous Transfer Mode
↑ CRC pour Cyclic Redundancy Check
↑ BIST pour Built-In Self-Test
↑ DSP pour Digital Signal Processor

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

↑ ^{a et b} Klein 2013, p. 17
↑ ^{a b c et d} Cagigal 1986, p. 191
↑ ^{a b c d et e} Ahmad 2003, p. 2
↑ Marjane 2011, p. 80-81
↑ ^{a b et c} Marjane 2011, p. 81
↑ ^{a et b} Klein 2013, p. 19
↑ ^{a et b} Marjane 2011, p. 83
↑ Ahmad 2003, p. 3
↑ ^{a et b} Klein 2013, p. 18
↑ Moon 2005, p. 154
↑ Reeds 1985, p. 505
↑ Marjane 2011, p. 14
↑ Ben Atti 2006, p. 76
↑ ^{a et b} Lauradoux 2007, p. 2
↑ Goresky 2002, p. 2827
↑ Goresky 2002, p. 2828
↑ Joux 2006, p. 437
↑ Marjane 2011, p. 152
↑ Bresson 2011, p. 11
↑ Menezes 1996, p. 191
↑ ^{a et b} Menezes 1996, p. 195
↑ ^{a b c et d} Menezes 1996, p. 204
↑ Chambers 1988, p. 17
↑ Klein 2013, p. 126.
↑ ^{a et b} Gamil 2002, p. 239
↑ Sundararaman 2011, p. 24
↑ ^{a et b} PATEL 1971, p. 11
↑ McCluskey 1985, p. 21
↑ McCluskey 1985, p. 25
↑ Breuer 1988, p. 933
↑ Lauradoux 2007, p. 1
↑ Ajane 2011, p. 1
↑ Chen 2010, p. 3
↑ ^{a et b} Chen 2010, p. 8
↑ [[#A53|]], p. 1

Bibliographie[modifier | modifier le code]

Manuels et cours[modifier | modifier le code]

(en) Andreas Klein, Stream Ciphers, 20 avril 2013 (DOI 10.1007/978-1-4471-5079-4), « Linear Feedback Shift Registers », p. 17-58
(en) Rudolf Lidl et Harald Niederreiter, Finite Fields, Cambridge University Press, 1997, 2^e éd., 755 p. (ISBN 978-0-521-39231-0, lire en ligne)
(en) A. Menezes et P. van Oorschot, Handbook of Applied Cryptography, 1996, 191-222 p. (lire en ligne).
(en) T.K. Moon, Error Correction Coding : Mathematical Methods and Algorithms, 27 juin 2005 (DOI 10.1002/0471739219.ch4), p. 154-170, en particulier le chapitre 4, « Cyclic Codes, Rings, and Polynomials »
(en) E. Bresson, Cryptographie-chiffrement par flot, 2007, 1-53 p. (lire en ligne).
(en) Yuhua Chen, Linear Feedback Shift Register (LFSR) Counters, 2010 (lire en ligne).

Articles de recherche[modifier | modifier le code]

(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)
(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)
(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.1986.0031)
(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)
(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 (ISBN 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 », Proceedings of ISWSN'03,‎ mars 2003 (lire en ligne).
(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)
(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) Dai Zongduo et Wan Zhexian, « A relationship between the Berlekamp-Massey and the euclidean algorithms for linear feedback shift register synthesis », Acta Mathematica Sinica,‎ 1^er 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)
(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)
Abdelaziz Marjane, Conception Vectorielle de Registre à rétroaction avec retenue sur les corps finis, 8 juillet 2011 (lire en ligne).
(en) J.A. Reeds et J.A. Sloane, « Shift Register Synthesis (Modulo m) », SIAM Journal on Computing,‎ août 1985, p. 505-513 (ISSN 0097-5397, DOI 10.1137/0214038)
(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)
(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) 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) « An Implementation Of The Noise Shift Register ».
(en) R. Sundararaman, « Stego System on chip with LFSR based Information Hidin Approach », International Journal of computer Application(0975-8887),‎ mars 2011 (lire en ligne).

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

Liens externes[modifier | modifier le code]

Registres à rétroaction linéaire sur www.apprendre-en-ligne.net
(en) Simple VHDL coding for Galois and Fibonacci LFSR.
Les registres à décalages à rétroactions linéaires LFSR sur www.picsi.org
Les Générateurs Linéaires Congruentiels sur http://rng.free.fr

[24] GSM pour Global System for Mobile Communications, historiquement Groupe Spécial Mobile

[27] FPGA pour Field-Programmable Gate Array

[29] ATM pour Asynchronous Transfer Mode

[30] CRC pour Cyclic Redundancy Check

[33] BIST pour Built-In Self-Test

[36] DSP pour Digital Signal Processor

[A23p17-1] {a et b} Klein 2013, p. 17

[A3p191-2] {a b c et d} Cagigal 1986, p. 191

[A21p2-3] {a b c d et e} Ahmad 2003, p. 2

[A34p8081-4] Marjane 2011, p. 80-81

[A34p81-5] {a b et c} Marjane 2011, p. 81

[A23p19-6] {a et b} Klein 2013, p. 19

[A34p83-7] {a et b} Marjane 2011, p. 83

[A21p3-8] Ahmad 2003, p. 3

[A23p18-9] {a et b} Klein 2013, p. 18

[A29p154-10] Moon 2005, p. 154

[A35p505-11] Reeds 1985, p. 505

[A34p14-12] Marjane 2011, p. 14

[A31p76-13] Ben Atti 2006, p. 76

[A4p2-14] {a et b} Lauradoux 2007, p. 2

[A22p2827-15] Goresky 2002, p. 2827

[A22p2828-16] Goresky 2002, p. 2828

[A33p437-17] Joux 2006, p. 437

[A34p152-18] Marjane 2011, p. 152

[A55p11-19] Bresson 2011, p. 11

[A54p191-20] Menezes 1996, p. 191

[A54p195-21] {a et b} Menezes 1996, p. 195

[A54p204-22] {a b c et d} Menezes 1996, p. 204

[A48p17-23] Chambers 1988, p. 17

[25] Klein 2013, p. 126.

[A40p239-26] {a et b} Gamil 2002, p. 239

[A56p24-28] Sundararaman 2011, p. 24

[A12p11-31] {a et b} PATEL 1971, p. 11

[A47p21-32] McCluskey 1985, p. 21

[A47p25-34] McCluskey 1985, p. 25

[A49p933-35] Breuer 1988, p. 933

[A4p1-37] Lauradoux 2007, p. 1

[A38p1-38] Ajane 2011, p. 1

[A52p3-39] Chen 2010, p. 3

[A52p8-40] {a et b} Chen 2010, p. 8

[A53p1-41] [[#A53|]], p. 1

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[note 1]

[24]

[25]

[note 2]

[26]

[note 3]

[note 4]

[27]

[28]

[note 5]

[29]

[30]

[note 6]

[31]

[32]

[33]

[34]

[35]

v · m Générateurs de nombres pseudo-aléatoires
Rapide	Générateur congruentiel linéaire Mersenne Twister RANDU
Cryptographiques	Blum Blum Shub Fortuna ISAAC Yarrow
Briques	Congruence sur les entiers Fonction de hachage LFSR