Registres à décalage à rétroaction linéaire en tant que générateurs de nombres pseudo-aléatoires. Registres à décalage avec rétroaction Exemple de registre à décalage avec rétroaction linéaire

Les séquences de registres à décalage sont utilisées à la fois en cryptographie et en théorie du codage. Leur théorie est bien développée : les chiffrements de flux basés sur des registres à décalage étaient la bête de somme de la cryptographie militaire bien avant l'avènement de l'électronique.

Registre à décalage avec retour se compose de deux parties : un registre à décalage et une fonction de rétroaction (Figure 1.2.1). Un registre à décalage est une séquence de bits. (Le nombre de bits est déterminé par la longueur du registre à décalage. Si la longueur est de n bits, alors le registre est appelé registre à décalage de n bits.) Chaque fois qu'un bit doit être récupéré, tous les bits du registre à décalage sont décalés d’une position vers la droite. Le nouveau bit le plus à gauche est fonction de tous les autres bits du registre. La sortie du registre à décalage est un bit, généralement le moins significatif. La période du registre à décalage est la longueur de la séquence résultante avant qu'elle ne commence à se répéter.

Riz. 1.2.1.

Les cryptographes appréciaient les chiffrements par flux basés sur des registres à décalage : ils étaient faciles à mettre en œuvre à l'aide de matériel numérique. Je n'aborderai que brièvement la théorie mathématique. En 1965, Ernst Selmer, cryptographe en chef du gouvernement norvégien, a développé la théorie de la séquence des registres à décalage. Solomon Golomb, un mathématicien de la NSA, a écrit un livre présentant certains de ses résultats et ceux de Selmer.

Le type le plus simple de registre à décalage à rétroaction est le registre à décalage à rétroaction linéaire, ou LFSR (Figure 1.2.2). Le retour est simplement un XOR de certains bits de registre, une liste de ces bits appelée séquence de prises. Parfois, un tel registre est appelé configuration de Fibbonacci. En raison de la simplicité de la séquence de rétroaction, une théorie mathématique assez avancée peut être utilisée pour analyser le LFSR. Les cryptographes adorent analyser des séquences, se convainquant que les séquences sont suffisamment aléatoires pour être sécurisées. Les LFSR sont les registres à décalage les plus couramment utilisés en cryptographie.

Riz. 1.2.2.

En figue. La figure 1.2.3 montre un LFSR 4 bits avec des prises sur les premier et quatrième bits. S'il est initialisé avec la valeur 1111, alors avant de répéter le registre prendra les états internes suivants :

Riz. 1.2.3. 4

La séquence de sortie sera une chaîne de bits de poids faible :

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

Un LFSR de n bits peut être dans l’un des 2n-1 états internes. Cela signifie que, théoriquement, un tel registre peut générer une séquence pseudo-aléatoire d'une période de 2n-1 bits. (Le nombre d'états internes et la période sont de 2n-1 car remplir le LFSR avec des zéros entraînera la production par le registre à décalage d'une chaîne infinie de zéros, ce qui est complètement inutile.) Ce n'est que pour certaines séquences de prises que le LFSR parcourra tous les 2n- 1 états internes, ces LFSR sont des LFSR avec une période maximale. Le résultat résultant est appelé une séquence M.

Pour qu'un LFSR particulier ait une période maximale, le polynôme formé à partir de la séquence de prises et de la constante 1 doit être primitif modulo 2. Le degré du polynôme est la longueur du registre à décalage. Un polynôme primitif de degré n est un polynôme irréductible qui est diviseur mais n'est pas diviseur de xd+1 pour tous les d diviseurs de 2n-1.

En général, il n'y a pas manière simple générer des polynômes primitifs d'un degré donné modulo 2. Le moyen le plus simple est de sélectionner un polynôme au hasard et de vérifier s'il est primitif. Ce n’est pas facile – et c’est un peu comme vérifier si un nombre aléatoire est premier – mais de nombreux logiciels mathématiques peuvent résoudre ce problème.

Certains polynômes de divers degrés, mais certainement pas tous, sont primitifs modulo 2. Par exemple, écrire (32, 7, 5, 3, 2, 1, 0) signifie que le polynôme suivant est primitif modulo 2 :

x32 + x7 +x5 + x3 + x2 + x + 1

Ceci peut être facilement généralisé à la période maximale LFSR. Le premier chiffre est la longueur du LFSR. Le dernier chiffre est toujours 0 et peut être omis. Tous les nombres sauf 0 spécifient une séquence de prises, comptée à partir du bord gauche du registre à décalage. Autrement dit, les termes d'un polynôme de degrés inférieurs correspondent à des positions plus proches du bord droit du registre.

En continuant avec l'exemple, l'écriture (32, 7, 5, 3, 2, 1, 0) signifie que pour un registre à décalage de 32 bits donné, un nouveau bit est généré en effectuant un XOR sur les trente-deuxième, septième, cinquième, troisième, deuxièmement et premiers bits, le LFSR résultant aura une longueur maximale, parcourant les valeurs 232-1 avant de se répéter.

Registre à décalage de rétroaction se compose de deux parties : un registre à décalage et fonctions de rétroaction.

Figure 19. Registre à décalage de rétroaction.

En général, un registre à décalage est une séquence de certains éléments en anneau ou en champ. Le plus souvent utilisé peu registres à décalage. La longueur d'un tel registre est exprimée en nombre de bits. Chaque fois qu'un bit est récupéré, tous les bits du registre sont décalés d'une position vers la droite. Le nouveau bit de poids fort est calculé en fonction de tous les autres bits du registre. La sortie est généralement le bit le moins significatif. La période du registre à décalage est la durée de la séquence de sortie avant qu'elle ne commence à se répéter.

Le type de registre à décalage le plus simple est un registre à décalage à rétroaction linéaire (LFSR ou LRS). Retour - opération simple XOR sur certains bits de registre. La liste de ces bits est déterminée polynôme caractéristique et s'appelle séquence de coups. Parfois, ce schéma est appelé Configuration de Fibonacci.

Figure 20. Configuration RSLOS de Fibonacci.

Lors de l'implémentation de LFSR dans le logiciel, un schéma modifié est utilisé : pour générer un nouveau bit significatif, au lieu d'utiliser les bits de la séquence de prises, une opération XOR est effectuée sur chacun de ses bits avec la sortie du générateur, remplaçant l'ancien bit de la séquence de frappe. Cette modification est parfois appelée Configuration galoisienne.

Figure 21. RSLOS de configuration Galois.

n-bit LFSR peut être dans l'un des 2 n– 1 états internes. Cela signifie que théoriquement un tel registre peut générer une séquence pseudo-aléatoire d'une période de 2 n– 1 bits (le remplissage avec des zéros est totalement inutile). Passage des 2 n– Les états internes 1 ne sont possibles qu'avec certaines séquences de prises. De tels registres sont appelés LFSR avec une période maximale. Pour assurer la période maximale du SFSR, il faut que son polynôme caractéristique soit primitif modulo 2. Le degré du polynôme est la longueur du registre à décalage. Polynôme de degré primitif n- C'est tellement irréductible un polynôme qui est un diviseur mais qui n'est pas un diviseur xd+ 1 pour tout le monde d, qui sont des diviseurs de 2 n– 1. (Lorsqu’on parle de polynômes, le terme nombre premier est remplacé par le terme polynôme irréductible). Le polynôme caractéristique du LFSR représenté sur les figures :

X 32 + X 7 + X 5 + X 3 + X 2 + X + 1

est primitive modulo 2. La période d'un tel registre sera maximale, passant cycliquement par toutes les valeurs 2 32 – 1 avant qu'elles ne soient répétées. Les plus couramment utilisés sont les polynômes amincis, c'est-à-dire qui n'ont que quelques coefficients. les plus populaires sont les trinômes.

Un paramètre important générateur basé sur RSLOS, est complexité linéaire. Elle est définie comme la longueur n le HFSR le plus court capable de simuler la sortie du générateur. La complexité linéaire est importante car l'utilisation de simples Algorithme de Berlenkamp-Massey vous pouvez recréer un tel LFSR en cochant seulement 2 n bits gamma. Une fois le RFSL requis déterminé, le chiffrement de flux est réellement craqué.

Dans un registre à décalage à rétroaction linéaire, il y a deux parties (modules) : le registre à décalage lui-même et les circuits (ou sous-programmes) qui calculent la valeur du bit poussé. Un registre est constitué de cellules fonctionnelles (ou de bits d'un mot machine ou de plusieurs mots), dont chacune stocke l'état actuel d'un bit. Le nombre de cellules est appelé longueur du registre. Les bits (cellules) sont généralement numérotés avec des nombres, chacun étant capable de stocker un bit, et le bit calculé est poussé dans la cellule, et le bit généré suivant est supprimé de la cellule. Le calcul du bit à pousser est généralement effectué avant le décalage du registre, et ce n'est qu'après le décalage que la valeur du bit calculé est placée dans la cellule.

La période du registre à décalage est la longueur minimale de la séquence résultante avant qu'elle ne commence à se répéter. Puisqu'un registre de cellules binaires n'a que des états différents non nuls, alors, en principe, la période du registre ne peut pas dépasser ce nombre. Si la période du registre est égale à ce nombre, alors un tel registre est appelé registre de période maximale.

Pour LFSR, la fonction de retour est une fonction booléenne linéaire des états de tout ou partie des bits du registre. Par exemple, la somme modulo deux ou son inversion logique est une fonction booléenne linéaire (opération XOR, notée dans les formules par ) et est le plus souvent utilisée dans de tels registres.

De plus, les bits qui sont variable de fonction les commentaires sont généralement appelés virages.

Le contrôle des registres dans les implémentations matérielles est effectué en appliquant une impulsion de décalage (autrement appelée horloge ou impulsion de synchronisation) à toutes les cellules, dans le logiciel - en exécutant un cycle logiciel, comprenant le calcul de la fonction de rétroaction et le décalage des bits dans un mot.

À chaque pas de temps, les opérations suivantes sont effectuées :

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

Ainsi, l'opération logique XOR (OU exclusif) est prise comme fonction de retour, c'est-à-dire :

Propriétés des polynômes primitifs

Propriétés

Les propriétés de la séquence produite par le LFSR sont étroitement liées aux propriétés du polynôme associé. Ses coefficients non nuls sont appelés virages, ainsi que les cellules de registre correspondantes qui fournissent les valeurs des arguments de la fonction de rétroaction.

Complexité linéaire

La complexité linéaire d’une séquence binaire est l’une des caractéristiques les plus importantes du fonctionnement du LFSR. Introduisons la notation suivante :

Complexité linéaire d'une séquence binaire infinie s'appelle un nombre, qui est défini comme suit :

Complexité linéaire d'une séquence binaire finie est appelé un nombre égal à la longueur du LFSR le plus court qui génère une séquence ayant pour premiers termes .

Propriétés de la complexité linéaire

Soit et soit des séquences binaires. Alors:

Indépendance de la corrélation

Pour atteindre une complexité linéaire élevée, les cryptographes tentent de combiner de manière non linéaire les résultats de plusieurs séquences de sortie. Dans ce cas, le danger est qu'une ou plusieurs séquences de sortie (souvent même les sorties de LFSR individuels) puissent être reliées par un flux de clé commun et ouvertes à l'aide de l'algèbre linéaire. Le piratage basé sur une telle vulnérabilité est appelé autopsie de corrélation. Thomas Siegenthaler a montré qu'il est possible de spécifier avec précision l'indépendance de corrélation et qu'il existe un compromis entre l'indépendance de corrélation et la complexité linéaire.

L'idée principale d'un tel hack est de détecter une certaine corrélation entre la sortie du générateur et la sortie de l'un de ses Composants. Ensuite, en observant la séquence de sortie, des informations sur cette sortie intermédiaire peuvent être obtenues. En utilisant ces informations et d'autres corrélations, les données peuvent être collectées sur d'autres broches intermédiaires jusqu'à ce que le générateur soit compromis.

Les attaques de corrélation ou leurs variantes telles que les attaques de corrélation rapide impliquant un compromis entre complexité informatique et efficacité ont été utilisées avec succès contre de nombreux générateurs de flux de clés de registre à décalage à rétroaction linéaire.

Exemple

Pour SFLOS avec un polynôme associé, la séquence générée a la forme . Disons qu'avant le début du processus la séquence est écrite dans le registre, alors la période du flux binaire généré sera égale à 7 avec la séquence suivante :

Puisque l'état interne de la septième étape est revenu à son état d'origine, alors, à partir de l'étape suivante, il y aura une répétition. En d'autres termes, la période de la séquence s'est avérée être égale à 7, ce qui s'est produit en raison du caractère primitif du polynôme.

Algorithmes de génération de polynômes primitifs

Tableaux prêts

Calculer la primitivité d'un polynôme est un problème mathématique assez complexe. Il y a donc tableaux prêts à l'emploi, qui affiche le nombre de séquences de prises qui fournissent la période maximale du générateur. Par exemple, pour un registre à décalage de 32 bits, il existe la séquence . Cela signifie que pour générer un nouveau bit, vous devez ajouter les 31e, 30e, 29e, 27e, 25e et 0e bits à l'aide de la fonction XOR. Le code d'un tel RLOS en langage C est le suivant :

Int LFSR (void) ( statique non signé long S = 1; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1 ) ; retourner S & 1 ; )

Implémentations logicielles Les générateurs RFLS sont assez lents et fonctionnent plus rapidement s'ils sont écrits en langage assembleur plutôt qu'en langage C. Une solution consiste à utiliser 16 RSLOS en parallèle (ou 32, selon la longueur des mots dans l'architecture d'un ordinateur particulier). Dans un tel schéma, un tableau de mots est utilisé, dont la taille est égale à la longueur du LFSR, et chaque bit d'un mot du tableau fait référence à son propre LFSR. À condition que les mêmes numéros de séquence de prises soient utilisés, cela peut fournir un gain de performances notable. [besoin d'un exemple de code] (Voir : bitslice).

Configuration galoisienne

Configuration galoisienne d'un registre à décalage à rétroaction linéaire

Le circuit de rétroaction peut également être modifié. Dans ce cas, le générateur n’aura pas une plus grande force cryptographique, mais il sera plus facile à implémenter dans le logiciel. Au lieu d'utiliser le bit le plus à gauche de la séquence de prises pour générer le nouveau bit le plus à gauche, il XOR chaque bit de la séquence de prises avec la sortie du générateur et le remplace par le résultat de cette action, puis la sortie du générateur devient la nouvelle le bit le plus à gauche. En C, cela ressemble à ceci :

Int LFSR (void) ( static non signé long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

L'avantage est que tous les XOR sont effectués en une seule opération.

• on peut prouver que la configuration de Fibonacci donnée en premier et la configuration de Galois donnée ici donnent les mêmes séquences (longueur 2 32 −1), mais décalées en phase l'une par rapport à l'autre
• une boucle d'un nombre fixe d'appels à la fonction LFSR dans la configuration Galois s'exécute environ deux fois plus vite que dans la configuration Fibonacci (compilateur MS VS 2010 sur Intel Core i5)
• A noter que dans la configuration Galois l'ordre des bits dans le mot définissant le feedback est inversé par rapport à la configuration Fibonacci

Exemples de générateurs

Générateurs stop-and-go

Générateur stop-go alterné

Cet oscillateur utilise la sortie d'un LFSR pour contrôler la fréquence d'horloge d'un autre LFSR. La sortie d'horloge de RSLOS-2 est contrôlée par la sortie de RSLOS-1, de sorte que RSLOS-2 ne peut changer d'état au temps t que si la sortie de RSDOS-1 au temps t-1 était égale à un. Mais ce schéma n’a pas pu résister à la dissection corrélationnelle.

Par conséquent, un générateur amélioré basé sur la même idée a été proposé. C'est ce qu'on appelle un générateur alternatif stop-go. Il utilise trois LFSR de longueurs différentes. RSLOS-2 est cadencé lorsque la sortie de RSLOS-1 est égale à un, et RSLOS-3 est cadencé lorsque la sortie de RSLOS-1 est égale à zéro. La sortie du générateur est la somme modulo 2 de RSLOS-2 et RSLOS-3. Ce générateur a une longue période et une grande complexité linéaire. Ses auteurs ont également montré une méthode d'ouverture corrélative de RSLOS-1, mais cela n'affaiblit pas beaucoup le générateur.

Cascade Gollmann

Cascade Gollmann

La cascade Gollmann est une version renforcée du générateur stop-go. Il consiste en une séquence de LFSR, dont le timing de chacun est contrôlé par le LFSR précédent. Si la sortie de RSLOS-1 au temps t est 1, alors RSLOS-2 est cadencé. Si la sortie de RSLOS-2 au temps t est 1, alors RSLOS-3 est cadencé, et ainsi de suite. La sortie du dernier LFSR est la sortie du générateur. Si la longueur de tous les LFSR est la même et égale à n, alors la complexité linéaire d'un système de k LFSR est égale à .

Cette idée est simple et peut être utilisée pour générer des séquences avec des périodes énormes, une grande complexité linéaire et de bonnes propriétés statistiques. Mais malheureusement, ils sont sensibles à l’ouverture, appelée « lock-in ». Pour une plus grande durabilité, il est recommandé d'utiliser un k d'au moins 15. De plus, il est préférable d'utiliser plus de SFSR courts que moins de SFSR longs.

Générateur de seuil

Générateur de seuil

Ce générateur tente de contourner les problèmes de sécurité inhérents aux générateurs précédents en utilisant un nombre variable de registres à décalage. En théorie, lorsqu'on utilise un plus grand nombre de registres à décalage, la complexité du chiffrement augmente, ce qui a été fait dans ce générateur.

Ce générateur est constitué d'un grand nombre de registres à décalage dont les sorties alimentent la fonction de majoration. Si le nombre de un aux sorties des registres est supérieur à la moitié, alors le générateur en sort un. Si le nombre de zéros aux sorties est supérieur à la moitié, alors le générateur génère zéro. Pour que la comparaison du nombre de zéros et de uns soit possible, le nombre de registres à décalage doit être impair. Les longueurs de tous les registres doivent être relativement premières et les polynômes de rétroaction doivent être primitifs, afin que la période de la séquence générée soit maximale.

Pour le cas de trois registres à décalage, le générateur peut être représenté comme :

Ce générateur est similaire au générateur Geff sauf que le générateur de seuil a une complexité plus linéaire. Sa complexité linéaire est :

où , , sont les longueurs des premier, deuxième et troisième registres à décalage.

Son inconvénient est que chaque bit de sortie fournit des informations sur l'état du registre à décalage. Ou plutôt 0,189 bits. Par conséquent, ce générateur pourrait ne pas être en mesure de résister à une attaque par corrélation.

Autres types

Auto-éclaircissant

Les générateurs auto-décimants sont ceux qui contrôlent leur propre fréquence. Deux types de tels générateurs ont été proposés. Le premier consiste en un registre à décalage à rétroaction linéaire et certains circuits qui synchronisent le registre en fonction des valeurs de sortie du registre à décalage. Si la sortie du SFSR est égale à un, alors le registre est cadencé d fois. Si la sortie est nulle, alors le registre est cadencé k fois. Le second a presque la même conception, mais légèrement modifié : dans le circuit d'horloge, l'entrée, pour vérifier 0 ou 1, n'est pas le signal de sortie lui-même, mais XOR de certains bits du registre à décalage avec rétroaction linéaire. Malheureusement, ce type de générateur n’est pas sécuritaire.

Oscillateur à plusieurs vitesses avec produit interne

Cet oscillateur utilise deux registres à décalage à rétroaction linéaire avec des fréquences d'horloge différentes : RSLOS-1 et RSLOS-2. La fréquence d'horloge de RSLOS-2 est d fois supérieure à celle de RSLOS-1. Les bits individuels de ces registres sont combinés à l'aide de l'opération ET. Les sorties de l’opération ET sont ensuite XOR. La séquence de sortie est extraite de ce bloc XOR. Encore une fois, ce générateur n'est pas parfait (il n'a pas résisté à la découverte de la cohérence linéaire. Si - la longueur de SFOS-1, - la longueur de SFOS-2, et d est le rapport fréquences d'horloge, alors l'état interne du générateur peut être obtenu à partir d'une séquence de sortie de longueur ), mais il présente une complexité linéaire élevée et d'excellentes caractéristiques statistiques.

Le type de fonction de rétroaction le plus simple est fonction linéaire, par exemple, la somme modulo 2 du contenu de certains bits. Ce registre est appelé registre à décalage à rétroaction linéaire (LFSR). En général, la fonction de rétroaction linéaire est donnée par la formule. Ici ck= 1 si k Le ème bit est utilisé dans la fonction de retour, et ck= 0 sinon. Le symbole Å désigne l'addition modulo 2 (OU exclusif).

Par exemple, considérons un LFSR avec une fonction de retour (voir figure).

Si l'état initial du registre est 1111, alors dans les cycles d'horloge suivants, il prendra la série d'états suivante : 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110, 1111, ...

La séquence de sortie est formée à partir du bit le moins significatif (le plus à droite) du registre. Cela ressemblera à ceci : 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. On peut voir que la séquence de bits générée est entièrement déterminée par l'état initial du registre et la fonction de retour. Puisque le nombre d'états de registre possibles est fini (il est égal à 2 L), puis tôt ou tard, la séquence de touches commencera à se répéter. La longueur maximale d'une partie non répétitive d'une séquence de touches est appelée son point T. La période dépend de la fonction de rétroaction. La période maximale possible est T maximum = 2 L-1 (le registre accepte tous les états possibles sauf 0000...0). La séquence de sortie du LFSR ayant la période maximale est appelée Séquence M.

Pour connaître les conditions dans lesquelles le LFSR aura une période maximale, les fonctions de feedback attribuent un polynôme caractéristique. Ainsi, le registre donné ci-dessus à titre d'exemple correspond à un polynôme. L'analyse théorique montre que le LFSR aura une période maximale si et seulement si le polynôme P.(X) est primitif. Vous trouverez ci-dessous quelques polynômes primitifs recommandés pour une utilisation pratique. Le tableau montre les puissances de la variable X en notation polynomiale. Par exemple, l'entrée (31, 3) correspond à un polynôme.

Les LFSR ont été initialement conçus pour être implémentés dans le matériel sous la forme d'un ensemble de circuits numériques. Les implémentations logicielles de LFSR sont généralement inférieures en vitesse aux implémentations matérielles. Pour augmenter les performances, il est avantageux de stocker l'état du registre sous forme d'entier L-numéro de bit dont les bits individuels correspondent aux bits binaires du registre. Ensuite, des opérations au niveau du bit (décalage, masquage, etc.) sont utilisées pour accéder aux bits individuels.

Les séquences sur les registres à décalage sont souvent utilisées pour construire des chiffrements de flux. Le registre à décalage avec rétroaction se compose de deux parties : le registre à décalage et la fonction de rétroaction, comme le montre la Fig. 87. Le registre à décalage lui-même est une séquence de bits dont le nombre détermine la longueur du registre. Ainsi, si un registre contient n bits, alors on dit qu'il s'agit d'un registre à décalage de n bits. Chaque fois qu'un bit est extrait, tous les bits du registre à décalage sont décalés d'une position vers la droite, généralement vers les bits les moins significatifs. La période du registre à décalage est la durée de la séquence résultante avant le début de sa répétition.

Riz. 87.

Toute fonction mathématique qui effectue une action sur des bits peut servir de retour. Le type le plus simple de registre à décalage à rétroaction est un registre à décalage à rétroaction linéaire (LFSR). Dans RFLS, la rétroaction est simplement une opération d'addition modulo 2 (XOR) sur certains bits de registre ; la liste de ces bits est appelée une séquence de prises, ou points de collecte, comme le montre la Fig. 88. Parfois, ce modèle est appelé configuration de Fibonacci. En raison de la simplicité de la séquence de rétroaction, une théorie mathématique assez avancée peut être utilisée pour analyser le LFSR. Dans tous les cas, la qualité de la PSP générée est évaluée à l'aide d'un ensemble spécial de tests.

Riz. 88.

Les SFLO sont écrits sous forme de polynômes. Dans ce cas, la puissance du premier élément du polynôme indique le nombre de bits dans le registre à décalage, et les exposants de puissance des membres restants du polynôme indiquent quels points d'échantillonnage seront utilisés. Ainsi, par exemple, l'entrée x 4 + x + 1 signifie qu'un registre de quatre éléments sera utilisé, pour lesquels les bits bi et b 0 participeront à la formation du feedback (Fig. 89).

Riz. 89,4

Considérons le fonctionnement du registre illustré à la Fig. 89. On l'initialise, par exemple, avec la valeur 0101 (l'initialisation initiale peut être effectuée par n'importe quelle séquence de bits, à l'exception d'une séquence de zéros uniquement, puisque dans ce cas le retour formera toujours la valeur zéro et le registre ne produit pas la bande passante attendue). Ainsi, le registre se décale d’une position vers la droite. Le bit de poids faible, égal à 1, est forcé de sortir du registre et constitue le premier bit de la bande passante mémoire. Les bits qui étaient en position b et b 0 sont ajoutés modulo 2 avant le décalage et forment un nouveau

le morceau le plus significatif du registre. Un exemple clair du fonctionnement du LFSR considéré est présenté sur la Fig. 90.

Riz. 90.

Comme on peut le voir sur la Fig. 90, le remplissage du registre passera par le poids de 15 des 16 états possibles (précédemment nous avons déterminé que le seizième état, lorsque LFSR est 0000, ne peut pas être pris en compte). Après cela, le remplissage du registre sera à nouveau égal à la valeur initiale 0101 et la génération de la séquence de bits commencera à se répéter. La séquence de sortie du registre sera une chaîne de bits les moins significatifs (jusqu'à la ligne horizontale sur la figure 90) : 101011110001001. La taille de la séquence de bits avant qu'elle ne soit répétée est appelée le point. Pour garantir la période maximale d'un LFSR particulier (c'est-à-dire pour que le registre passe par le poids des états internes possibles), le polynôme qui détermine le fonctionnement du registre doit être primitif modulo 2. Comme c'est le cas avec les grands nombres premiers, il n'existe aucun moyen de générer de tels polynômes. Vous pouvez uniquement prendre un polynôme et vérifier s'il est irréductible modulo 2 ou non. Dans le cas général, un polynôme primitif de degré n est un polynôme irréductible qui est un diviseur de x 2 "+1, mais n'est pas un diviseur de x d +1 pour tous les d qui sont des diviseurs de 2" -1. Dans l'ouvrage de B. Schneier, un tableau de quelques polynômes est donné, qui sont irréductibles modulo 2.

En résumant les connaissances obtenues en considérant un exemple de fonctionnement du LFSR (Fig. 90), nous pouvons dire qu'un LFSR à n bits peut être dans l'un des états internes 2"-1. Théoriquement, un tel registre peut générer une séquence pseudo-aléatoire de période 2 n -1 bits. De tels registres sont appelés registres LFSR avec une période maximale. La sortie résultante est appelée une séquence t.