Utilisateur:Proz/brouillon

Un récit courant Fowler 1999, p. 356.

1/2

Définition

Cas booléen

Un registre à décalage et rétroaction peut être réalisé électroniquement par un dispositif dérivé du registre à décalage de type SIPO, Serial In - Parallel Out, dans lequel le bit d'entrée est obtenu en fonction du contenu du registre. Quand la fonction en question dite fonction de rétroaction, est linéaire, c'est-à-dire que le bit d'entrée est obtenu par XOR (addition modulo 2), à partir de bits contenus dans le registre à certains emplacements donnés, il s'agit d'un registre à décalage et rétroaction linéaire ou LFSR.

Un LFSR de longueur (ou de taille) r utilise un registre de r éléments successifs appelés « étages » ou « cellules », que l'on peut numéroter de 0 à r -1. Chacun de ses éléments peut contenir un bit et possède une entrée et une sortie. Le contenu du registre est contrôlé par une horloge. À chaque top d'horloge

• le contenu d'un étage i (0 ≤ i < r - 1) est transféré au suivant i+1,
• le premier étage (numéroté 0) reçoit le bit de rétroaction obtenu par XOR à partir des bits contenus dans une sélection donnée des étages,
• le bit du dernier étage (numéroté r - 1) est le bit de sortie, la suite engendrée par le LFSR est la suite des bits de sorties.

Un LFSR est donc décrit par sa longueur, par la sélection des étages qui seront utilisés pour calculer le bit de rétroaction. Par exemple sur le schéma donné ci-dessus, le LFSR possède 16 cellules et, en les numérotant de 0 à 15 de la gauche vers la droite, la sélection des étages utilisés pour la retroaction est [10,12,13,15].

La suite engendrée par un LFSR de longueur r, soit (s_t)_{t in ℕ} où s_t est le bit de sortie au bout de t tops d'horloge, est alors entièrement déterminée par le contenu initial du registre, soit dans l'ordre de la numérotation, (s_r-1, … , s₀), appelé état initial du registre.

Plus généralement l'état du LFSR est le contenu des étages à un instant t (t top d'horloges), soit (s_{t + r-1}, … , s_t).

Le calcul du bit de rétroaction peut également être décrit par une suite de coefficients (c₁, … , c_r) choisis dans {0,1} parfois appelés coefficients de rétroaction ((en)Feedback coefficients), c_i = 1 si le i-ème registre (numéroté i+1) est utilisé pour le calcul du bit de rétroaction, 0 sinon. Dans l'exemple ci-dessus, les coefficients de connexion sont

(c₁, … , c₁₆) = (0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1)

La suite engendrée par le LFSR est alors la suite définie par récurrence par la relation

$s_{n+r}=\sum _{i=0}^{r-1}c_{r-i}s_{n+i}{\pmod {2}}$

soit pour l'exemple du schéma ci-dessus

s_n+16 = s_n + s_n+2 + s_n+3 + s_n+5 (mod 2).

A remplacer.

Suite des états d'un LFSR de 4 cellules

t	bit de rétroaction st+4	État du LFSR st+3 st+2 st+1 st	Sortie st-1
0	1	1 0 0 0
1	0	1 1 0 0	0
2	1	0 1 1 0	0
3	0	1 0 1 1	0
4	0	0 1 0 1	1
5	0	0 0 1 0	1
6	1	0 0 0 1	0
7	1	1 0 0 0	1
…	…	…	…

Le LFSR considéré est de longueur 4. Il est défini par la relation de récurrence

s_t+4 = s_t+3 + s_t+1 + s_t

c'est-à-dire que les coefficients de connexion sont

(c₁,c₂,c₃,c₄) = (1,0,1,1)

et l'état initial du registre est (1,0,0,0).

Le calcul de la suite des états du registre du LFSR fait apparaître qu'au bout de 7 étapes l'état du registre égale l'état initial. La suite engendrée est donc périodique de période 7, cette période est (0,0,0,1,1,0,1).

Description mathématique

Pour analyser mathématiquement le dispositif décrit à la section précédente, on s'intéresse à la suite de bits (a_n) engendrée, le bit s_i étant le contenu de la dernière cellule au i-ème top d'horloge.

Suite engendrée

Les suites d'éléments de F_q pouvant être produites par un registre à décalage à rétroaction linéaire sont les suites récurrentes linéaires, si le registre est de longueur r la suite récurrente linéaire est d'ordre r.

Autrement dit on peut obtenir le terme d'indice t + r à partir des termes d'indice t,...,t+r-1 par une relation linéaire du type

$a_{t+n}=c_{r}a_{t}+c_{r-1}a_{t+1}+...+c_{1}a_{t+r-1}~$

où les c_i appartiennent à F_q (c_i = 0 ou c_i = 1 dans le cas binaire F₂).

Périodicité

Il est facile de voir qu'une suite produite par un tel registre est nécessairement périodique : le nombre de possibilités combinatoires pour un $n$-uplet est au plus de $q^{n}$, donc $f:t\mapsto (u_{t},...,u_{t+n-1})$ n'est pas injective, soit $\exists t_{0},t_{1},f(t_{0})=f(t_{1})$. Mais, clairement on a $\forall x,y$, $f(x)=f(y)\Rightarrow f(x+i)=f(y+i)$ en prenant $i=\max(t_{0}-t_{1},t_{1}-t_{0})$ on a donc un multiple de la période de la suite.

La période maximale est $q^{n}-1$ car si le $n$-uplet tout à zéro est atteint, la suite est nécessairement constante égal à zéro. On sait prévoir lorsque cette valeur atteinte, une condition nécessaire et suffisante étant que le polynôme de rétroaction soit primitif -- i.e. est irréductible et tel que, dans l'anneau $F_{q}[X]$ des polynômes à coefficients binaires, le plus petit t tel que ce polynôme divise $X^{t}-1$ est $q^{n}-1$ (c'est le polynôme minimal d'un élément d'ordre multiplicatif maximal $q^{n}-1$ dans le corps à $q^{n}$ éléments).

Une suite de période maximale est appelée m-sequence dans la terminologie anglo-saxonne.

Représentation polynômiale

Il est possible de décrire les LFSR en utilisant les séries formelles :

si à une suite $U=(u_{i})$ on associe la série $U(X)=\sum _{i=0}^{\infty }u_{i}X^{i}$ alors l'équation ci-dessus peut se mettre sous la forme suivante : $U(X)P(X)=T(X)$

où

• $P(X)=1+\alpha _{1}X+...+\alpha _{n}X^{n}$
• Le polynôme T(X) a pour degré au plus n -1 et dépend des conditions initiales (les u_i de 0 à n - 1) et de P.

Le polynôme P, appelé polynôme de rétroaction, caractérise le registre.

Notion de complexité linéaire

Tout $m$-uplet de bits peut être généré par un LFSR. Plus précisément, il existe toujours un LFSR -- i.e. un polynôme de rétroaction ainsi qu'une initialisation -- tel que les $m$ premières sorties de ce LFSR correspondent au $m$-uplet. Dans le pire des cas on prend un registre de longueur $m$, le polynôme de rétroaction important peu dans ces conditions.

Ceci donne lieu à la définition de la complexité linéaire d'une suite (finie) comme la longueur minimale d'un LFSR généré cette suite. Comme le prouve la remarque ci-dessus cette complexité est bornée supérieurement par la longueur de la suite.

Cette notion intervient notamment en cryptographie à cause de l'existence de l'algorithme de Berlekamp-Massey.

Registre à décalage et cryptographie

Génération de nombres pseudo-aléatoires

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 : d'une part 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.), et d'autre part 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.

Le chiffrement par masque jetable illustre bien les enjeux. Dans ce chiffrement, le texte chiffré est produit par addition bit à bit (modulo 2) de la clef de chiffrement. Le déchiffrement est également effectué par addition bit à bit de la clef. Le problème est qu'il est alors nécessaire de partager une donnée secrète, à savoir la clef, de la même taille que le message à échanger. C'est très souvent impraticable. Vient alors l'idée d'engendrer la clef à partir d'un procédé déterministe -- il faut pouvoir le faire au chiffrement et au déchiffrement -- utilisant une donnée secrète plus petite. C'est le fonctionnement du chiffrement par flot.

Une première possibilité consiste à choisir un LFSR et à utiliser la donnée secrète partagée comme initialisation du registre. Toutefois, l'algorithme de Berlekamp-Massey met vite fin à cette tentative : une connaissance même très partielle de la suite produite permet de retrouver toutes les informations voulues.

Dans la pratique, les LFSR ne sont donc pas utilisés de manière isolée, mais essentiellement sous la forme de registres combinés ou filtrés par des fonctions non linéaires ou mieux, par des procédés qui ne tiennent pas seulement compte des entrées mais aussi de l'état du dispositif (voir A5/1 ou E0).

Algorithme de Berlekamp-Massey

Un LFSR de taille $n$ produisant des suites récurrentes linéaires d'ordre $n$, la connaissance de $n$ termes consécutifs d'une suite et de l'équation linéaire -- ou bien de manière équivalente le polynôme de rétroaction -- détermine toute la suite.

Si maintenant on ne suppose plus connu le polynôme de rétroaction, que peut-on déduire de l'observation d'une partie de la sortie du LFSR, par exemple les termes $u_{t_{0}},u_{t_{0}+1},...,u_{t_{0}+L-1}$ ? Si $L$ est supérieur où égal à deux fois la taille du plus petit LFSR générant la suite $(u_{i})$, alors on peut retrouver le polynôme de rétroaction et l'initialisation du registre, c'est-à-dire déterminer entièrement le LFSR (on voit ainsi apparaître la complexité linéaire comme le paramètre permettant d'estimer la quantité d'information nécessaire pour recréer une suite sous forme de LFSR). De plus il existe un algorithme efficace qui permet de retrouver efficacement ces paramètres, l'algorithme de Berlekamp-Massey, introduit en 1969 par James Massey (Massey, J. L. "Shift-Register Synthesis and BCH Decoding." IEEE Trans. Information Th. 15, 122-127, 1969.). C'est une adaptation d'un algorithme, dû à Elwyn Berlekamp, de décodage de codes correcteurs -- les codes de Bose-Chaudhuri-Hocquenghem.

Manuels et cours

• (en) Andreas Klein, Linear Feedback Shift Registers, 20 avril 2013 (DOI 10.1007/978-1-4471-5079-4), p. 17-58
• (en) Rudolf Lidl et Harald Niederreiter, Finite Fields, Cambridge University Press, 1997, 2^e éd. (ISBN 978-0-521-39231-0)
• (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) Rainer A. Rueppel, Analysis and design of stream ciphers, Springer, 1986 (ISBN 978-3-540-16870-6, lire en ligne), p. 244