Registres à décalage avec feedback. Registre à décalage linéaire avec historique de rétroaction des registres à décalage

Registre à décalage de rétroaction ( FRS ) se compose de deux parties : registre à décalage Et fonctions de rétroaction .

Un registre à décalage (Erreur : source de référence introuvable) est une séquence de bits. Lorsqu'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 la valeur de la fonction de rétroaction des bits restants du registre. Période Le registre à décalage correspond à la longueur de la séquence résultante avant qu'elle ne commence à se répéter.

Le type le plus simple de registre à décalage de rétroaction est registre à décalage linéaire avec rétroaction (LFSR – Gauche Retour Changement Registre) (Erreur : source de référence introuvable). Le retour est simplement XOR de quelques p bits s'inscrire, la liste de ces bits est appelée séquence de frappe.

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 avec une période 2 n -1 morceaux Le nombre d'états internes et la période sont égaux car remplir le registre avec des zéros entraînera la production d'une séquence infinie de zéros, ce qui est absolument inutile. Seulement avec certaines séquences de tapotements, le LFSR parcourra toutes les 2 n -1 états internes. Ces LFSR sont appelés LFSRavec période maximale.

Pour qu'un LFSR particulier ait une période maximale, un polynôme formé à partir de la séquence de prises et de la constante 1 doit être primitif modulo 2 .

Calculer la primitivité d'un polynôme est un problème mathématique assez complexe. Par conséquent, il existe des tableaux prêts à l'emploi qui montrent le nombre de séquences de prises qui fournissent la période maximale du générateur. Par exemple, pour un registre à décalage 32 bits, vous pouvez trouver l'entrée suivante : (32,7,5,3,2,1,0) . Cela signifie que pour générer un nouveau bit, vous devez additionner les trente-deuxième, septième, cinquième, troisième, deuxième et premier bits à l'aide de la fonction XOR.

Le code d’un tel LFSR en C++ ressemblerait à ceci :

// Toute valeur autre que zéro

ShiftRegister = ((((ShiftRegister >> 31)

^ (ShiftRegister >> 6)

^ (ShiftRegister >> 4)

^ (ShiftRegister >> 2)

^ (ShiftRegister >> 1)

^ ShiftRegistre)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

retourner ShiftRegister & 0x00000001 ;

Les implémentations logicielles de LFSR sont assez lentes et fonctionnent plus rapidement si elles sont écrites en langage assembleur plutôt qu'en C. Une solution consiste à utiliser 16 LFSR en parallèle (ou 32 selon la longueur des mots dans l'architecture informatique spécifique). Ce schéma utilise un tableau de mots dont la taille est égale à la longueur du LFSR, et chaque unité 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.

AVEC 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 le résultat du générateur devient le nouveau. bit le plus à gauche (Erreur : source de référence introuvable).

Cette modification s'appelle Configuration galoisienne. En C, cela ressemble à ceci :

statique non signé long ShiftRegister = 1 ;

void seed_LFSR (graine longue non signée)

ShiftRegister = graine ;

int Galua_LFSR (vide)

si (ShiftRegister & 0x00000001) (

ShiftRegister = (ShiftRegister ^ masque >> 1) | 0x8000000 ;

ShiftRegistre >>= 1 ;

L'avantage est que tous les XOR sont effectués en une seule opération. Ce circuit peut également être parallélisé.

Les LFSR eux-mêmes sont de bons générateurs de séquences pseudo-aléatoires, mais ils possèdent certaines propriétés non aléatoires indésirables. Les bits consécutifs sont linéaires, ce qui les rend inutiles pour le chiffrement. Pour les longueurs LFSR n l'état interne représente le précédent n bits de sortie du générateur. Même si le modèle de rétroaction est gardé secret, il peut être déterminé par 2 n bits de sortie du générateur à l'aide d'algorithmes spéciaux. De plus, les grands nombres aléatoires générés à l’aide de bits consécutifs de cette séquence sont fortement corrélés et ne sont pas aléatoires pour certains types d’applications. Malgré cela, les LFSR sont souvent utilisés pour créer des algorithmes de chiffrement. À cette fin, plusieurs LFSR sont utilisés, généralement avec des longueurs et des numéros de séquence de prises différents. La clé est l'état initial des registres. Chaque fois qu'un nouveau bit est nécessaire, tous les registres sont décalés. Cette opération s'appelle pointage. Le bit de sortie est une fonction, de préférence non linéaire, de certains bits LFSR. Cette fonction est appelée combinant, et le générateur dans son ensemble – générateur de combinaison. Beaucoup de ces générateurs sont toujours sûrs.

Ministère de l'Éducation et des Sciences

UNIVERSITÉ SOCIALE D'ÉTAT RUSSE

FACULTÉ DE TECHNOLOGIE DE L'INFORMATION

DÉPARTEMENT DE PROTECTION DE L'INFORMATION

Méthodes cryptographiques et moyens d'assurer la sécurité de l'information

Travaux de cours

"R registres à décalage avec rétroaction linéaire comme générateurs de nombres pseudo-aléatoires"

Complété:

étudiant en 3ème année

groupe KZOI-D-3

Larionov I.P.

Vérifié:

Assoc. Baranova E.K.

Moscou 2011
CONTENU

Introduction ……………………………..…………………………………….3

1. Base théorique du travail…………………………………………4
   1. Informations générales sur les registres à décalage à rétroaction............4
      1. À propos des chiffrements de flux basés sur RgSsLOS………………….………10
      2. Sur la complexité linéaire de la séquence pseudo-aléatoire générée RgCsLOC………………………………….……12
      3. Sur l'indépendance de corrélation de la séquence générée de nombres pseudo-aléatoires PrCsLOC………..….13
      4. À propos des autres méthodes d'ouverture de la séquence générée de nombres pseudo-aléatoires PrCsLOC……………………………………………………..14
2. Implémentation logicielle de PrCsLOS en tant que générateur de séquences pseudo-aléatoires….…………………………….15
   1. Schéma généralisé de l'algorithme…………………………………...15
   2. Description des modules logiciels et de l'interface.……………….16
   3. Mode d'emploi………………………………………...20

Conclusion ………………………………………………………………22

Bibliographie………………………………………………….....23

Annexe A ….………………………………………………………..24

INTRODUCTION

Le but de ce travail est de développer une application logicielle qui implémente le fonctionnement d'un générateur de nombres pseudo-aléatoires utilisant des registres à décalage avec rétroaction. Le développement de cette application à interface graphique est réalisé dans le langage C++ pour le système d'exploitation Windows.

Avec le développement de la cryptographie au XXe siècle, les cryptographes ont été confrontés à la tâche de créer des dispositifs et des machines de cryptage capables de crypter et de déchiffrer les messages de manière rapide et fiable. Cette exigence était satisfaite par les systèmes de chiffrement symétrique déjà ouverts à cette époque, mais leur point faible était leur forte dépendance à la clé et à son secret. La classe de chiffrements la plus pratique pouvant être utilisée à cette fin est celle des chiffrements gamma. Le problème s'est posé de générer un gamma qui ne pouvait pas être détecté lors du décryptage d'un message. Théoriquement, cela était possible si à chaque fois le gamma était aléatoire et changeait dans le temps. Cependant, lors de l'utilisation d'un gamma changeant de manière totalement aléatoire, il serait difficile de garantir un cryptage et un déchiffrement fiables du message. Les cryptographes ont entrepris de résoudre ce problème, dont le but était de trouver un algorithme qui implémente la génération d'un gamma aléatoire selon une certaine règle ; une telle séquence devrait contenir des zéros et des uns dans des positions « soi-disant » aléatoires, et le nombre de uns et les zéros devraient être à peu près les mêmes. Cette séquence aléatoire a été appeléepseudo-aléatoire,puisqu'il a été généré selon une certaine règle, et non par hasard.

Une solution fut bientôt trouvée. L'étude des propriétés des registres à décalage a permis d'établir que les registres à décalage par rétroaction sont capables de générer des séquences pseudo-aléatoires suffisamment résistantes au décryptage, du fait de leur structure interne.

1.Base théorique du travail

1.1.Informations générales sur les registres à décalage avec retour 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.

Un registre à décalage en boucle fermée (ci-après dénommé RGSSOC) se compose de deux parties : un registre à décalage et une fonction de rétroaction.Un registre à décalage est une séquence de bits. Le nombre de bits est déterminé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.Période du registre de décalageest la longueur de la séquence résultante avant le début de sa répétition.

Registre à décalage de chiffres avec rétroaction

Les registres à décalage ont rapidement été utilisés dans les chiffrements de flux car ils étaient facilement implémentés à l'aide de matériel numérique. 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 de rétroaction estregistre à décalage à rétroaction linéaire ( registre à décalage à rétroaction linéaire, ci-après LFSR ou РгСсЛОС) . Le retour de tels registres est simplement un XOR (addition modulo deux) 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 PrCsVOC. En analysant les séquences de sortie résultantes, vous pouvez vérifier que les séquences sont suffisamment aléatoires pour être sûres. RGCCLOS est utilisé plus souvent que les autres registres à décalage en cryptographie.

Figure PrCsLOS Fibbonacci

En général, n -bit PrCsLOS peut être dans l'un des N=2n -1 états internes. Cela signifie que théoriquement un tel registre peut générer une séquence pseudo-aléatoire avec une période de T=2 n -1 bits. (Le nombre d'états internes et la période sont égaux N = Tmax =2n -1 car remplir PrCcLOS avec des zéros fera que le registre à décalage produira une séquence infinie de zéros, ce qui est absolument inutile). Ce n'est que pour certaines séquences de branchement que PrCsLOS traversera cycliquement les 2 n -1 états internes, ces PrCsLOS sontRgSsLOS avec période maximale. Le résultat résultant est appeléSéquence M.

Exemple . La figure ci-dessous montre un PrCCLOS à 4 bits avec les premier et quatrième bits exploités. S'il est initialisé avec la valeur 1111, alors avant de répéter le registre prendra les états internes suivants :

Numéro d'horloge de décalage (état interne)	Statut d'inscription				Bit de sortie
Valeur initiale
15 (retour à l'état initial)
16 (répétition des états)

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 de période T=15, le nombre total d'états internes possibles (sauf zéro), N =2 4 -1=16-1=15= Tmax , donc la séquence de sortie M -sous-séquence.

Pour qu'un PrCsLOS 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 polynôme est représenté comme une somme de puissances, par exemple, un polynôme de degré n apparaît comme ceci :

a n x n +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 +…+a 1 x+a 0 , où a i =(0, 1 ) pour i=1…n, a x i indique le chiffre.

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 diviseur de x 2n−1 +1, mais n'est pas un diviseur de x d +1 pour tout d qui est diviseur de 2 n -1. La théorie mathématique correspondante peut être trouvée dans.

En général, il n’existe pas de moyen simple de 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 sélectionné au hasard est premier – mais de nombreux logiciels mathématiques peuvent résoudre ce problème.

Certains polynômes de différents degrés, mais certainement pas tous, qui sont primitifs modulo 2 sont donnés ci-dessous. Par exemple, enregistrez

(32, 7, 5, 3, 2, 1, 0) signifie que le polynôme suivant est primitif modulo 2 : x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

Ceci peut être facilement généralisé à PrCsVOC avec une période maximale. Le premier nombre est la longueur de PrCsLOS. 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ème et premier bits, le PrCsLOS résultant aura une longueur maximale, parcourant 2 32 -1 valeurs.

Figure 4 PrCsLOC 32 bits avec longueur maximale

Considérons le code de programme PrCsLOS, dans lequel la séquence de prises est caractérisée par un polynôme (32, 7, 5, 3, 2, 1, 0). En C, cela ressemble à ceci :

int LFSR() (

statique non signé long ShiftRegister = 1 ;

/* Tout sauf 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegistre >> 6)

^(ShiftRegistre >> 4)

^(ShiftRegistre >> 2)

^(ShiftRegistre >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

retourner ShiftRegister & 0 x 00000001 ;)

Si le registre à décalage est plus long qu’un mot informatique, le code devient plus compliqué, mais pas beaucoup. Dans l'application B un tableau de quelques polynômes primitifs modulo 2 est donné ; nous l'utiliserons dans le futur pour identifier certaines propriétés de ces polynômes, ainsi que dans l'implémentation logicielle pour spécifier la séquence de prises.

Veuillez noter que tous les éléments du tableau ont un nombre impair de coefficients. Ce long tableau est fourni pour des travaux ultérieurs avec RgCsLOC, puisque RgCsLOC est souvent utilisé pour la cryptographie avec des chiffrements de flux et dans des générateurs de nombres pseudo-aléatoires. Dans notre cas, nous pouvons utiliser des polynômes dont le degré le plus élevé ne dépasse pas sept.

Si p(x) est primitif, alors x l’est aussi n p(1/x), donc chaque élément du tableau définit en fait deux polynômes primitifs. Par exemple, si (a, b, 0) est primitif, alors (a, a-b, 0) est également primitif. Si (a, b, c, d, 0) est primitif, alors (a, a-d, a-c, a-b, 0) est également primitif. Mathématiquement:

si x est primitif a + x b +1, alors x est aussi primitif a +x ab +1,

si x est primitif a +x b +x c +x d +1, alors x est aussi primitif a +x a-d +x a-c +x ab +1. Les trinômes primitifs sont les plus rapides à implémenter dans un logiciel, puisque pour générer un nouveau bit il faut effectuer un XOR uniquement sur deux bits du registre à décalage (le terme zéro n'est pas pris en compte, c'est-à-dire x 0 =1, voir exemple ci-dessus). En effet, tous les polynômes de rétroaction donnés dans le tableau sont clairsemés, c'est-à-dire qu'ils ont peu de coefficients. La parcimonie est toujours source de faiblesse, ce qui suffit parfois à casser l’algorithme. Pour les algorithmes cryptographiques, il est préférable d’utiliser des polynômes primitifs denses, ceux comportant de nombreux coefficients. En utilisant des polynômes denses, notamment dans le cadre d’une clé, des PrCsLOS beaucoup plus courts peuvent être utilisés.

Générer des polynômes primitifs denses modulo 2 n’est pas facile. En général, pour générer des polynômes primitifs de degré k, il faut connaître la factorisation du nombre 2 k-1.

En eux-mêmes, les PrCsLOS sont de bons générateurs de séquences pseudo-aléatoires, mais ils possèdent certaines propriétés non aléatoires (déterministes) indésirables. Les bits consécutifs sont linéaires, ce qui les rend inutiles pour le chiffrement. Pour un PrCcLOS de longueur n, l'état interne est constitué des n bits de sortie précédents du générateur. Même si le circuit de rétroaction est gardé secret, il peut être déterminé à partir des 2n bits de sortie de l'oscillateur à l'aide de l'algorithme très efficace de Berlekamp-Massey.

De plus, les grands nombres aléatoires générés à l’aide de bits consécutifs de cette séquence sont fortement corrélés et, pour certains types d’applications, ne sont pas du tout aléatoires. Malgré cela, les RgCCLOS sont souvent utilisés pour créer des algorithmes de chiffrement en tant que composants de systèmes et d'algorithmes de chiffrement.

1.2.À propos des chiffrements de flux basés sur RgSSLOS

L'approche de base pour concevoir un générateur de flux de clés basé sur RgSSLOS est simple. Tout d’abord, un ou plusieurs PrCsLOS sont pris, généralement avec des longueurs différentes et des polynômes de rétroaction différents. (Si les longueurs sont premières entre elles et que tous les polynômes de rétroaction sont primitifs, alors le générateur généré aura une longueur maximale.) La clé est l'état initial des registres PrCcLOS. Chaque fois qu'un nouveau bit est nécessaire, décalez d'un bit les registres PrCCLOC (c'est ce qu'on appelle parfois le timing). Le bit de sortie est une fonction, de préférence non linéaire, de certains bits des registres PrCsLOS. Cette fonction est appelée fonction de combinaison et le générateur dans son ensemble est appelé générateur combinatoire. (Si le bit de sortie est fonction d'un seul PrCCLOS, alors l'oscillateur est appelé oscillateur à filtre.) Une grande partie de la théorie de ce type de dispositif est développée par Selmer et Neal Zierler. Un certain nombre de complications peuvent être introduites. Certains oscillateurs utilisent des fréquences d'horloge différentes pour différents RgSsLOS, parfois la fréquence d'un oscillateur dépend de la sortie d'un autre. Ce sont toutes des versions électroniques d'idées de machines de chiffrement d'avant la Seconde Guerre mondiale appelées oscillateurs contrôlés par horloge ( générateurs contrôlés par horloge ). Le contrôle de l'horloge peut être rétroactif, où la sortie d'un PrCcLOC contrôle la fréquence d'horloge d'un autre PrCcLOC, ou rétroaction, où la sortie d'un PrCcLOC contrôle sa propre fréquence d'horloge. Bien que tous ces générateurs soient sensibles, du moins en théorie, aux attaques par imbrication et éventuelle corrélation, nombre d’entre eux restent sûrs.

Ian Cassells, ancien responsable des mathématiques pures à Cambridge et cryptanalyste à Bletchly Park, a déclaré que « la cryptographie est un mélange de mathématiques et de confusion, et sans confusion, les mathématiques peuvent être utilisées contre vous ». Ce qu'il voulait dire, c'est que dans les chiffrements de flux, certaines structures mathématiques telles que PrCcLOS sont nécessaires pour fournir une longueur maximale et d'autres propriétés, mais un chaos non linéaire complexe doit être introduit pour empêcher quelqu'un d'obtenir le contenu du registre et de casser l'algorithme. Ce conseil s’applique également aux algorithmes de blocage.

La plupart des chiffrements de flux réels sont basés sur PrCsLOS. Même aux débuts de l’électronique, leur construction n’était pas difficile. Le registre à décalage n'est rien de plus qu'un tableau de bits et la séquence de rétroaction est un ensemble de portes XOR. Même en utilisant VLSI, le chiffrement de flux basé sur PrCsLOC offre une sécurité considérable à l'aide de plusieurs portes logiques. Le problème avec PrSSLOS est que leur implémentation logicielle est très inefficace. Vous devez éviter les polynômes de rétroaction clairsemés - ils facilitent les attaques de corrélation - et les polynômes de rétroaction denses sont inefficaces.

Cette branche de la cryptographie se développe rapidement et est sous le contrôle vigilant du gouvernement. N.S.A. . La plupart des développements sont classifiés : de nombreux systèmes de cryptage militaires utilisés aujourd'hui sont basés sur RgSSLOS. En effet, la plupart des ordinateurs Cray (Cray 1, Cray X-MP, Cray Y-MP) disposent d'une instruction très intéressante, communément appelée « comptage de population ». Il compte le nombre de un dans un registre et peut être utilisé à la fois pour calculer efficacement la distance de Hamming entre deux mots binaires et pour implémenter une version vectorisée de PrCcLOS. Cette instruction est considérée comme une instruction canonique de la NSA, devant figurer dans presque tous les contrats relatifs aux ordinateurs.

D’un autre côté, un nombre étonnamment élevé de générateurs de registres à décalage apparemment complexes ont été piratés. Et bien entendu, le nombre de générateurs de ce type piratés par des agences militaires de cryptanalyse telles que la NSA est encore plus important.

1.3.Sur la complexité linéaire de la séquence générée de nombres pseudo-aléatoires PrCsLOC

Les chiffrements par flux sont souvent plus faciles à analyser que les chiffrements par blocs. Par exemple, un paramètre important utilisé pour analyser les générateurs basés sur PrCsLOS est la complexité linéaire, ou intervalle linéaire. Elle est définie comme la longueur n du PrCsLOS le plus court pouvant simuler la sortie du générateur. Toute séquence générée par un automate fini sur un champ fini a une complexité linéaire finie. La complexité linéaire est importante car, à l'aide d'un algorithme simple appelé algorithme de Berlekamp-Massey, il est possible de déterminer ce PrCcLOS en vérifiant seulement 2n bits du flux de clés. En recréant le PrCsLOS souhaité, vous déchiffrez le chiffrement de flux.

Cette idée peut être étendue des champs aux anneaux et aux cas où la séquence de sortie est traitée comme des nombres dans un champ de caractéristiques impaires. Une extension supplémentaire conduit à l'introduction du concept de profil de complexité linéaire, qui détermine la complexité linéaire d'une séquence à mesure qu'elle s'allonge. Il existe également des concepts de complexité sphérique et quadratique. Dans tous les cas, rappelez-vous qu'une complexité linéaire élevée ne garantit pas nécessairement la sécurité du générateur, mais qu'une faible complexité linéaire indique que le générateur n'est pas suffisamment sécurisé.

1.4.Sur l'indépendance de corrélation de la séquence générée de nombres pseudo-aléatoires PrCsLOS

Les cryptographes tentent d'obtenir une complexité linéaire élevée en combinant de manière non linéaire les résultats de certaines séquences de sortie. Le danger ici est qu'une ou plusieurs séquences de sortie internes - souvent uniquement les sorties de PrCsLOS individuels - peuvent être connectées par un flux de clés commun et ouvertes à l'aide de l'algèbre linéaire. Cette autopsie est souvent appelée autopsie de corrélation ou autopsie diviser pour régner. Thomas Siegenthaler a montré qu'il est possible de définir précisément 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'une attaque par corrélation 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, on peut obtenir des informations sur cette sortie intermédiaire. En utilisant ces informations et d'autres corrélations, des données peuvent être collectées sur d'autres sorties intermédiaires jusqu'à ce que le générateur soit compromis.

Les attaques de corrélation et leurs variantes, telles que les attaques de corrélation rapide, offrent un compromis entre complexité informatique et efficacité et ont été utilisées avec succès contre de nombreux générateurs de flux de clés basés sur PrCsLOS.

1.5.À propos des autres méthodes d'ouverture de la séquence générée de nombres pseudo-aléatoires PrCsLOS

Il existe d'autres moyens de briser les générateurs de keystream. Un test de cohérence linéaire tente de trouver un sous-ensemble de la clé de chiffrement à l'aide d'une technique matricielle. Il existe également une « attaque de cohérence par rencontre au milieu ». L'algorithme du syndrome linéaire est basé sur la capacité d'écrire un fragment de la séquence de sortie sous la forme d'une équation linéaire. Il existe une attaque par meilleure approximation affine et une attaque par séquence dérivée. Des méthodes de cryptanalyse différentielle et linéaire peuvent également être appliquées aux chiffrements par flux.

2. Description de l'implémentation logicielle de PrCsLOS en tant que générateur de séquences pseudo-aléatoires

2.1.Schéma généralisé de l'algorithme

2.2.Description des modules logiciels et de l'interface

La figure 3 ci-dessous montre la fenêtre du programme.

Interface du programme Figure

Le menu a les fonctions suivantes :

• Fichier->Enregistrer le rapport

Cette fonction crée un fichier de rapport qui enregistre l'état initial de PrCsLOS, la séquence de prises, la période de la séquence de bits pseudo-aléatoire reçue, la séquence elle-même et la table d'état. Si le fichier a été enregistré avec succès, un message indiquant que l'enregistrement a réussi s'affiche (Figure 4). L'extension recommandée du fichier de rapport est *. SMS.

Dessin

• Fichier->Quitter

Cette fonctionnalité garantit la fermeture de l'application.

• Définir la séquence de frappe

Cette fonction génère une séquence de frappes en lisant les valeurs des cases que l'utilisateur a cochées sur le formulaire d'écran. Après quoi, il informe l'utilisateur de la création d'une séquence de frappes (Figure 5). La séquence de prises détermine quelles bascules du registre à décalage fourniront un retour. XOR pour générer un bit de décalage. Par défaut, le retour du premier déclencheur est toujours activé ; en l'absence d'autres connexions, un décalage vers la gauche sera effectué avec le bit de poids faible se déplaçant vers la position de poids fort.

Dessin

• Définir la valeur initiale

Cette fonction lit la valeur du registre initial fournie par l'utilisateur à partir de la fenêtre Modifier 1 et vérifie la valeur saisie selon les conditions spécifiées : la chaîne saisie n'est pas vide (Figure 6), la chaîne saisie a une longueur de huit (8 bits = 1 octet, Figure 7), la chaîne saisie ne contient que des zéros et/ou uns (Figure 8), la chaîne saisie est différente de zéro (Figure 9). Dans le cas contraire, des messages d'erreur s'affichent, l'utilisateur doit les corriger et appuyer à nouveau sur le bouton. Si la vérification réussit, la valeur initiale sera écrite dans le tableau d'état dans la ligne « Initial » et une notification sera émise (Figure 10).

Dessin

Dessin

Dessin

Dessin

Dessin

• Cas de changement

Cette fonction émule le fonctionnement d'un registre à décalage. En effectuant séquentiellement 256 décalages, chaque décalage génère un bit de sortie de séquence pseudo-aléatoire et un nouvel état de registre. Dès que l'état du registre est égal à celui initial, la période est calculée et affichée dans le champ Note 1 séquence pseudo-aléatoire résultante.

• Aide->À propos du programme

Cette fonction affiche une brève description du programme et des instructions (Figure 11).

Dessin

• Aide->À propos de l'auteur

Cette fonction affiche des informations sur l'auteur du programme (Figure 12).

Dessin

2.3.Instructions d'utilisation

1. Réglez d’abord le registre à son état initial. Il doit contenir huit caractères binaires. Sinon, un message d'erreur s'affichera et vous devrez corriger la valeur saisie. Cliquez sur l'élément de menu « Définir la valeur initiale ».
2. Cochez ensuite les cases correspondant aux retours d'enregistrement (Tap Sequence). Cliquez sur l'élément de menu « Définir la séquence de frappe ».
3. Ensuite, cliquez sur l’élément de menu « Case Shift ». Avant de faire cela, assurez-vous d'avoir terminé les étapes 1 et 2, sinon une erreur logicielle se produira.
4. Après avoir reçu les résultats, vous pouvez les enregistrer en cliquant sur l'élément de menu « Fichier->Enregistrer le rapport ». Avant de faire cela, assurez-vous d'avoir terminé les étapes 1 à 3, sinon une erreur logicielle se produira.
5. Pour obtenir de l'aide, cliquez sur les éléments de menu « Fichier->À propos du programme », « Fichier->À propos de l'auteur ».
6. Pour voir le fonctionnement du registre avec d'autres valeurs de la séquence de prises et l'état initial du registre, répétez les étapes des étapes 1 à 3, en entrant d'autres paramètres.

CONCLUSION

Dans ce travail, les PrCsLOS ont été considérés comme des générateurs de nombres pseudo-aléatoires. Le programme peut servir de démonstration visuelle des principes de fonctionnement des registres à décalage avec rétroaction linéaire XOR . Vous pourrez y étudier le principe de formation d'une séquence pseudo-aléatoire de bits, la relation entre la valeur initiale du registre et la valeur de la séquence pseudo-aléatoire, la séquence de prises et la période. Le gamma pseudo-aléatoire résultant peut être utilisé dans une autre application logicielle (par exemple, une implémentation logicielle d'un chiffre gamma).

Pour le moment, ces registres ne sont pas utilisés comme générateurs indépendants de nombres pseudo-aléatoires, mais font partie de dispositifs plus complexes. Cependant, ce sont eux qui ont ouvert de nouvelles directions en mathématiques (recherche de polynômes primitifs dans des corps finis, méthodes mathématiques de piratage de générateurs de nombres pseudo-aléatoires). Sans connaissance des principes de fonctionnement des générateurs basés sur PrSSLOS, il est impossible de comprendre le fonctionnement d'appareils plus complexes. En raison de leur mise en œuvre matérielle simple, ils sont largement utilisés dans la technologie. Les recherches de RgCCOS ont conduit à l'émergence de nouveaux chiffrements - bloc et flux - basés sur ces types de registres (chiffre à permutation mobile, DES et ainsi de suite.; EDS, fonctions de hachage).

En général, la recherche dans ce domaine a sérieusement poussé le développement de la cryptographie et de la cryptanalyse, des ordinateurs et des appareils, et a également permis de mettre en œuvre un certain nombre d'autres fonctions utiles (par exemple, la correction des codes cycliques).

BIBLIOGRAPHIE

1. Schneier Bruce. Cryptographie appliquée. Protocoles, algorithmes, textes sources en langage C. M. : Triomphe, 2002
2. Babash A.V. Aspects cryptographiques et théoriques des automates de la sécurité de l'information moderne. Tome 1 M. : Maison d'édition. Centre EAOI, 2009. 414 p.
3. E.S. Selmer. Monographie : « Récursion linéaire dans un corps fini. » Université de Bergen, Norvège, 1966.
4. N. Zierler et J. Brillhart. "Sur les trinômes primitifs modulo 2", Journal of Information and Control, Vol. 13 n° 6 décembre 1968, pp. 541-544.
5. K.H. Meyer et W.L. Tuchman. "Les codes pseudo-aléatoires peuvent être déchiffrés", magazine Electronic Design, no. 23 novembre 1972.
6. J.L. Massey. "Généralisation des registres à décalage et décodage du code Bose-Chowdhury-Hocquenghem", Transactions IEEE sur la théorie de l'information, v. IT-15, n . 1, janvier 1969, p. 122-127.
7. S.U. Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (réimprimé par Aigean Park Press, 1982).

Annexe A

Tableau de quelques polynômes primitifs modulo 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Entrée dans l'état initial (IS)

vérifier l'exactitude de la saisie

Émettre un message d'erreur

Régler la séquence de frappe

Enregistrement d'un IC dans la table d'état

Enregistrer je ème état du registre et bit de sortie dans la table d'état

IS==État actuel

Sauvegarde des résultats

Sortie de séquence pseudo-aléatoire

Sortie

Lancement

Oui

Oui

Non

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 pour les grands nombres premiers, il n'y a pas 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.

Le type de fonction de rétroaction le plus simple est une 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.

№	P.(X)	№	P.(X)	№	P.(X)
	(39, 16, 23, 35)		(38, 5, 6, 27)		(32, 2, 7, 16)
	(30, 6, 4, 1)		(31, 6)		(31, 7)
	(31, 13)		(31, 25, 23, 8)		(33, 13)
	(35, 2)		(47, 5)		(48, 9, 7, 4)
	(47, 11, 24, 32)		(46, 18, 31, 40)		(53, 6, 2, 1)
	(55, 24)		(57, 7)		(58, 19)
	(59, 7, 4, 2)		(41, 27, 31, 32)		(61, 5, 2, 1)
	(42, 30, 31, 34)		(51, 15, 24, 46)		(50, 17, 31, 34)

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.

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.

Dans ce cas, les bits qui sont des variables de la fonction de rétroaction 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 :

Définition

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 :

Numéro d'étape	État	Bit généré
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

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. Par conséquent, il existe des tableaux prêts à l'emploi qui montrent 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 ; )

Les implémentations logicielles des générateurs LFSR sont assez lentes et fonctionnent plus rapidement si elles sont écrites en 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 SFLO-1, - la longueur de SFLO-2, et d est le rapport des 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 performances statistiques.