# 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$ à 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$_2$. 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…

## Fonctionnement
### Principe

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.
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. À 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.

### Exemple

LFSR à 4 bits :
| 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=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
### Conception

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

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$_1$, …, c$_r$ sont des éléments de F$_q$.

#### 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$ ou de façon équivalente $a_{r+n}=\sum _{j=0}^{r-1}c_{r-j}a_{n+j}$.

#### Taille

    La taille du LFSR est r le nombre de cellules.

#### Coefficients de connexion

    les coefficients c$_1$, …, c$_r$ sont appelés les coefficients de connexion du LFSR.

#### 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. Quand q=2, F$_2$ 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$^,$ $A(X)=\sum _{n=0}^{\infty }a_{n}X^{n}$

### Représentations polynomiales
#### 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}$.
    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]]$$^,$.
    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é

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$^,$.
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 »$^,$.
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

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. 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.
Description de l'algorithme :
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{\Bigldeg(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

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 ».

### Fibonacci

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.

### Galois

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.
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$^,$.

## Applications

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).
L'usage de cette technologie peut se retrouver dans les domaines suivants :
* 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

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.
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).
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
#### 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, 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.
Les raisons pour lesquelles les LFSRs sont utilisés dans un grand nombre de générateurs de flux sont les suivantes :
* 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.
Néanmoins, les LFSRs restent encore utilisés en raison de leurs coûts de mise en œuvre très bas.
Trois méthodes peuvent être employées pour contourner l'effet des propriétés de linéarité des LFSRs :
* 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.
Les propriétés attendues d'un générateur de flux de chiffrement sont :
* 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, 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).

#### 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.
Les séquences pseudo-aléatoires à base de LFSRs sont une des méthodes de chiffrement de l'information.
Embarqués dans des circuits logiques programmables tels que les FPGA, ils répondent à un besoin croissant de cacher l'information.

### Détection d'erreurs et correction de données

Plusieurs types de CRC selon les applications :
| Application | Type | taille LFSR |
| CRC | CRC-12 | 12 |
| | CRC-16 | 16 |
| Réseau ATM | 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 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.
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.

### Auto-contrôle des circuits électroniques

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 :
* 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 est une méthode de test des composants électroniques qui s'appuie sur plusieurs mécanismes :
* 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.

### Traitement numérique du signal

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. 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.

### Compteurs à base de LFSRs

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.
Exemples d'utilisation:
* 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 | Inconvénients |
| 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

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.