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

Un registre à décalage à rétroaction linéaire, ou LFSR (acronyme de l'anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite récurrente linéaire, initialement sur le corps fini à 2 élements (0 et 1), mais la notion a été généralisée à n'importe quel corps fini.

Réalisé électroniquement, pour le corps à 2 éléments F₂, c'est un registre à décalage (de type SIFO, Serial In - Parallel Out) avec rétroaction linéaire, ce qui dans ce cas signifie que le bit entrant est le résultat d'un OU exclusif (ou XOR) entre plusieurs bits du registre.

La suite récurrente produite par un LFSR est nécessairement périodique à partir d'un certain rang, étant définie sur un corps fini. Les LFSR sont utilisés en cryptographie pour engendrer des suites de nombres pseudo-aléatoires. La fonction de rétraction est choisie de façon à obtenir une période la plus grande possible. Ils interviennent comme composants de certains chiffrements à flot comme par exemple A5/1, chiffre du GSM, ou plus récemment SOSEMANUK (en) proposé dans le cadre du projet européen eSTREAM (en).

Rétroaction basée sur un XOR entre plusieurs bits.
Appuyer sur la touche "échap" pour faire cesser l'animation

Sommaire

1 Description mathématique
2 Registre à décalage et cryptographie
- 2.1 Génération de pseudo-aléatoire
- 2.2 Algorithme de Berlekamp-Massey
3 Voir aussi

Description mathématique

Représentation par les suites

Les suites de bits pouvant être produites par un registre à décalage à rétroaction linéaire sont simples à décrire mathématiquement : ce sont les suites récurrentes linéaires. Autrement dit, on peut obtenir le terme $t+n~$ à partir des termes $t,...,t+n-1~$ par une équation linéaire du type

$u_{t+n}= \alpha_n u_{t}+\alpha_{n-1} u_{t+1}+...+\alpha_{1} u_{t+n-1}~$

où les $\alpha_i~$ valent $0$ ou $1$ .

Représentation polynômiale

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

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

$U(X) P(X)= T(X)~$

où

$T(X)=\sum_{i=0}^{n-1} u_iX^i$
$P(X)=1+\alpha_1 X+ ... +\alpha_n X^n~$

Le polynôme $T~$ correspond à l'initialisation du registre, alors que le polynôme $P$ , appelé polynôme de rétroaction, caractérise le registre.

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 $2 n$ , donc $f:t\mapsto (u_{t},...,u_{t+n-1})$ est surjective, soit $\exists t_0,t_1, f(t_0)=f(t_1)$ . Mais, clairement on a $\forall x,y$ et $i$ , $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 $2 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 2 [X]$ des polynômes à coefficients binaires, le plus petit t tel que ce polynôme divise $X t - 1$ est $2 n - 1$ (c'est le polynôme minimal d'un élément d'ordre multiplicatif $2 n - 1$ dans le corps à $2 n$ éléments).

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

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 pseudo-aléatoire

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 -- mesure de temps entre frappes de touches sur un clavier, déplacement de la souris, ... --, et d'autre part l'expansion d'une courte suite aléatoire de bits en une suite 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 probablement un peu de là l'origine 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 LFSRs ne sont donc pas utilisés de manière isolée, mais essentiellement sous la forme des registres combinés ou filtrés.

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}$ ? L'algorithme de Berlekamp-Massey répond à cette question de la façon suivante : 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. En abrégé : tout. 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.

L'algorithme de Berlekamp-Massey fut 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.

Voir aussi

Bibligraphie

(en) Rudolf Lidl et Harald Niederreiter (de), Finite Fields, Cambridge University Press, 1997, 2^e éd. (ISBN 978-0-521-39231-0)

Liens externes

Registres à rétroaction linéaire sur apprendre-en-ligne.net
Shift generator sur inria.fr
(en) Simple VHDL coding for Galois and Fibonacci LFSR.

v · 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

Portail de l’informatique
Portail de la cryptologie
Portail de l’électricité et de l’électronique

Catégorie :

Circuit intégré logique

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Registre à décalage à rétroaction linéaire de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

Registre a decalage — Registre à décalage En électronique et en informatique, un registre à décalage est un registre de taille fixe dans lequel les bits sont décalés à chaque coup d horloge (dans le cas d un système synchrone sur l horloge). Un registre à décalage est … Wikipédia en Français
Registre à décalage — Un registre à décalage est un registre, c est à dire un ensemble de bascules synchrones, dont les bascules sont reliées une à une, à l exception de deux bascules qui ne sont pas forcément reliées. A chaque cycle d horloge, le nombre représenté… … Wikipédia en Français
Arithmétique modulaire — Couverture de l’édition originale des Recherches arithmétiques de Gauss, livre fondateur de l’arithmétique modulaire. En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes… … Wikipédia en Français
PANAMA — est une primitive cryptographique qui peut faire office de fonction de hachage cryptographique ou de chiffrement de flot. Elle a été conçue par Joan Daemen et Craig Clapp en 1998 à partir de StepRightUp. Fonctionnement PANAMA est basée sur une… … Wikipédia en Français
StepRightUp — est une fonction de hachage cryptographique et un chiffrement de flot conçu par Joan Daemen en 1995. La primitive est basée sur un automate fini de 544 bits avec un registre à décalage à rétroaction linéaire de 8448 bits. La fonction a évolué… … Wikipédia en Français
Code pseudo-aléatoire — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… … Wikipédia en Français
Fonction pseudo-aléatoire — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… … Wikipédia en Français
Generateur de nombres pseudo-aleatoires — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… … Wikipédia en Français
Générateur De Nombres Pseudo-Aléatoires — Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les nombres sont supposés être… … Wikipédia en Français
Générateur de nombre pseudo-aléatoire — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

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

Sommaire