C'est le suivant. Tout d’abord, deux grands nombres premiers 1 sont sélectionnés Un entier positif supérieur à un est appelé simple, s'il n'est divisible par aucun autre nombre que lui-même et un. Pour plus d’informations sur les nombres premiers, consultez Principes fondamentaux de la théorie des nombres utilisés dans la cryptographie à clé publique. nombres p et q. Les nombres p et q doivent être tous deux comparableà partir de 3 modulo 4, c'est-à-dire que lorsque p et q sont divisés par 4, le même reste 3 doit être obtenu. Ensuite, le nombre M = p* q, appelé entier de Bloom, est calculé. Ensuite, un autre entier aléatoire x est choisi, qui est premier (c'est-à-dire n'a pas de diviseur commun autre qu'un) avec M. On calcule x0= x 2 mod M. x 0 est appelé le numéro de départ du générateur.

A chaque nième étape du fonctionnement du générateur, x n+1 = x n 2 mod M est calculé. Le résultat de la nième étape est un bit (généralement le moins significatif) du nombre x n+1. Parfois, le résultat est un bit de parité, c'est-à-dire le nombre de un dans la représentation binaire de l'élément. Si le nombre de un dans l'enregistrement numérique est pair, le bit de parité est pris égal à 0, si le nombre est impair, le bit de parité est pris égal à 1.

Par exemple, soit p = 11, q = 19 (on s'assure que 11 mod 4 = 3, 19 mod 4 = 3). Alors M = p* q = 11*19=209 . Choisissons x qui est premier à M : soit x = 3. Calculons le numéro de départ du générateur x 0 :

x 0 = x 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.

Calculons les dix premiers nombres x i en utilisant l'algorithme BBS. Comme bits aléatoires, nous prendrons le bit le moins significatif dans la représentation binaire du nombre x i :

La propriété la plus intéressante de cette méthode à des fins pratiques est que pour obtenir le nième nombre de la séquence, il n'est pas nécessaire de calculer tous les n nombres x i précédents. Il s'avère que x n peut être immédiatement obtenu en utilisant la formule

Par exemple, calculons x 10 directement à partir de x 0 :

En conséquence, nous avons en fait obtenu la même valeur que dans le calcul séquentiel - 137. Les calculs semblent assez complexes, mais en fait ils sont faciles à formuler dans une petite procédure ou un petit programme et à utiliser si nécessaire.

La possibilité d'obtenir « directement » xn vous permet d'utiliser l'algorithme BBS pour le cryptage de flux, par exemple pour des fichiers à accès aléatoire ou des fragments de fichiers avec des enregistrements de base de données.

La sécurité de l’algorithme BBS repose sur la difficulté de factoriser un grand nombre M. On fait valoir que si M est suffisamment grand, il n’est même pas nécessaire de le garder secret ; Tant que M n'est pas factorisé, personne ne peut prédire la sortie du générateur PNG. Cela est dû au fait que la tâche de factoriser des nombres de la forme n = pq (p et q sont des nombres premiers) est très difficile sur le plan informatique si nous ne connaissons que n, et p et q sont de grands nombres composés de plusieurs dizaines ou centaines de nombres. bits (c'est ce qu'on appelle problème de factorisation).

De plus, il peut être prouvé qu'un attaquant, connaissant une certaine séquence générée par le générateur BBS, ne pourra déterminer ni les bits précédents ni les suivants. Générateur de BBS imprévisible dans la direction gauche Et dans la bonne direction. Cette propriété est très utile à des fins de cryptographie et elle est également associée aux fonctionnalités de factorisation du nombre M.

L'inconvénient le plus important de l'algorithme est qu'il n'est pas assez rapide, ce qui empêche son utilisation dans de nombreux domaines, par exemple dans les calculs en temps réel, et aussi, malheureusement, dans cryptage de flux.

Mais cet algorithme produit une très bonne séquence de nombres pseudo-aléatoires avec une grande période (avec un choix approprié de paramètres initiaux), ce qui lui permet d'être utilisé à des fins cryptographiques lors de la génération de clés de chiffrement.

Termes clés

Chiffrement de flux– chiffrement de flux.

Algorithme BBS– une des méthodes de génération de nombres pseudo-aléatoires. Le nom de l'algorithme vient des noms des auteurs - L. Blum, M. Blum, M. Shub. L'algorithme peut être utilisé en cryptographie. Pour calculer le nombre suivant x n+1 à l'aide de l'algorithme BBS, utilisez la formule x n+1 = x n 2 mod M, où M = pq est le produit de deux grands nombres premiers p et q.

Générateur de nombres pseudo-aléatoires (PRNG)- un algorithme ou un dispositif qui crée une séquence de bits qui semble aléatoire.

Générateur congruent linéaire nombres pseudo-aléatoires - l'un des PRNG les plus simples, qui pour calculer le nombre suivant k i utilise la formule k i =(a*k i-1 +b)mod c, où a, b, c sont des constantes, a k i-1 est le le précédent nombre pseudo-aléatoire.

Méthode de Fibonacci avec décalages– une des méthodes de génération de nombres pseudo-aléatoires. Peut être utilisé en cryptographie.

Chiffrement de flux– un chiffre qui crypte le message d'entrée sur un bit (ou un octet) par opération. Un algorithme de chiffrement de flux élimine le besoin de diviser un message en un nombre entier de blocs. Les chiffrements de flux sont utilisés pour chiffrer les données en temps réel.

Bref résumé

Un chiffrement de flux est un chiffrement qui crypte un message d'entrée sur un bit (ou un octet) par opération. Un algorithme de chiffrement de flux élimine le besoin de diviser un message en un nombre entier de blocs. Ainsi, si un flux de caractères est transmis, chaque caractère peut être crypté et transmis en une seule fois. Les chiffrements de flux sont utilisés pour chiffrer les données en temps réel.

Les programmes informatiques nécessitent souvent une émulation aléatoire. Par exemple, lors du développement de jeux. Si le programme a un certain générateur, c'est-à-dire un producteur, d'un nombre aléatoire, alors, en utilisant le nombre ainsi obtenu, vous pouvez sélectionner l'une ou l'autre branche de l'exécution du programme, ou un objet arbitraire de la collection. En d’autres termes, l’essentiel est de générer un nombre. L'émulation d'un autre type de hasard est basée sur cela.

Nous ne savons certainement pas s’il y a du hasard dans la nature, ou si cela nous semble dû aux limites de nos connaissances. Nous savons seulement qu’il n’y a pas de véritable hasard dans la programmation. Il n’y a nulle part d’où puisse provenir un nombre arbitraire ; il est impossible de programmer son apparition de nulle part. Vous ne pouvez créer qu'un programme qui, en appliquant une formule complexe au « grain », produira un nombre, et il nous semblera que ce nombre est aléatoire.

« Grain » correspond aux données d'entrée de la formule. Il peut s'agir, par exemple, de l'heure du système en millisecondes, qui change constamment. Par conséquent, le « grain » sera constamment différent. Ou le programmeur peut le définir lui-même.

Un tel programme (en réalité un module ou une fonction) est appelé générateur de nombres pseudo-aléatoires. La bibliothèque standard Python inclut le module random. Il contient de nombreuses fonctions liées à l'émulation du caractère aléatoire (par exemple, « mélanger » les éléments d'une séquence), et pas seulement des fonctions permettant de générer des nombres pseudo-aléatoires.

Ce tutoriel couvrira les fonctions random(), randrange() et randint() du module random. Veuillez noter que le module random contient la fonction random() du même nom. Cela arrive.

Pour accéder aux fonctions, vous devez importer le module aléatoire :

>>> importer au hasard

Ou importez-en des fonctions individuelles :

>>> à partir d'une importation aléatoire aléatoire, randrange, randint

Fonctions pour obtenir des nombres entiers "aléatoires" - randint() et randrange()

Les fonctions randint() et randrange() génèrent des entiers pseudo-aléatoires. Le premier d'entre eux est le plus simple et ne prend toujours que deux arguments - les limites de la plage entière dans laquelle n'importe quel nombre est sélectionné :

>>> aléatoire .randint (0 , 10 ) 6

ou (si des fonctions individuelles ont été importées) :

>>> randint(100 , 200 ) 110

Dans le cas de randint(), les deux limites sont incluses dans la plage, c'est-à-dire que dans le langage mathématique, le segment est décrit comme .

Les nombres peuvent être négatifs :

>>> aléatoire .randint (-100 , 10 ) -83 >>> aléatoire .randint (-100 , -10 ) -38

Mais le premier nombre doit toujours être inférieur ou au moins égal au second. C'est-à-dire un<= b.

La fonction randrange() est plus complexe. Cela peut prendre un argument, deux ou même trois. Si un seul est spécifié, il renvoie un nombre aléatoire compris entre 0 et l'argument spécifié. De plus, l’argument lui-même n’est pas inclus dans la fourchette. En langage mathématique, cela s'écrit Vi ] 2 Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]

Le système implique l'utilisation d'une clé de 112 bits et de trois cryptages EDE. Deux valeurs pseudo-aléatoires sont données en entrée : la valeur de date et d'heure et la valeur initiale de l'itération en cours ; la sortie est la valeur initiale de l'itération suivante et la valeur pseudo-aléatoire suivante. Même si le nombre pseudo-aléatoire Ri est compromis, il n'est pas possible de calculer Vi+1 à partir de Ri dans un temps raisonnable, et donc la prochaine valeur pseudo-aléatoire Ri+1, puisque trois opérations EDE supplémentaires sont effectuées pour obtenir Vi+ 1.

PRNG matériel

Hormis les anciens générateurs LFSR bien connus qui ont été largement utilisés comme PRNG matériels au 20e siècle, malheureusement, on sait très peu de choses sur les PRNG matériels modernes (chiffrements de flux), car la plupart d'entre eux ont été développés à des fins militaires et sont gardés secrets. . Presque tous les PRNG matériels commerciaux existants sont brevetés ou gardés secrets. Les PRNG matériels sont limités par des exigences strictes en matière de mémoire consommable (le plus souvent l'utilisation de la mémoire est interdite), de performances (1 à 2 cycles d'horloge) et de surface (plusieurs centaines de cellules FPGA ou ASIC). En raison d'exigences aussi strictes pour les PRNG matériels, il est très difficile de créer un générateur à l'épreuve du chiffrement, c'est pourquoi tous les PRNG matériels connus ont été brisés jusqu'à présent. Des exemples de tels générateurs sont Toyocrypt et LILI-128, qui sont tous deux des générateurs LFSR et tous deux ont été piratés à l'aide d'attaques algébriques.

En raison du manque de bons PRNG matériels, les fabricants sont obligés d'utiliser des chiffrements par blocs (DES, AES) et des fonctions de hachage (SHA-1) beaucoup plus lents mais bien connus dans les modes flux.

Générer des séquences aléatoires avec une loi probabiliste donnée et vérifier leur adéquation est l'un des problèmes les plus importants de la cryptologie moderne. Des générateurs de séquences aléatoires sont utilisés dans les cryptosystèmes existants pour générer des informations clés et définir un certain nombre de paramètres du cryptosystème. L'importance scientifique et pratique de ce problème est si grande que des monographies distinctes dans le domaine de la cryptologie lui sont consacrées, des sections sont organisées dans les revues scientifiques "Journal of Cryptology", "Cryptologia" et des sessions spéciales lors de conférences scientifiques internationales "Eurocrypt", "Asiacrypt", "Crypto" etc.

Au début du XXe siècle, des séquences aléatoires étaient simulées à l'aide des expériences aléatoires les plus simples : lancer une pièce de monnaie ou un dé, tirer des boules d'une urne, disposer des cartes, roulette, etc. En 1927, L. Tippett publie pour la première fois des tableaux contenant plus de 40 000 nombres aléatoires, « extraits au hasard des rapports de recensement ». En 1939, à l'aide d'un dispositif mécanique spécialement conçu, un générateur de nombres aléatoires, M. J. Kendall et B. Babington-Smith ont créé un tableau contenant 10 5 nombres aléatoires. En 1946, le mathématicien américain John von Neumann proposa pour la première fois un algorithme informatique permettant de générer des nombres aléatoires. En 1955, la RAND Corporation a publié des tableaux très populaires contenant 10 6 nombres aléatoires générés par ordinateur.

Actuellement, la demande de générateurs de séquences aléatoires avec des distributions de probabilité données, ainsi que des séquences aléatoires elles-mêmes, a tellement augmenté que des sociétés de recherche et de production sont apparues à l'étranger, produisant et vendant de larges gammes de nombres aléatoires. Par exemple, depuis 1996, le disque compact « Le CDROM des nombres aléatoires Marsaglia » est distribué dans le monde entier, qui contient 4,8 milliards de bits « véritablement aléatoires ».

La grande majorité des systèmes cryptographiques modernes utilisent des algorithmes de flux ou de blocs basés sur divers types de chiffrements de substitution et de permutation. Malheureusement, presque tous les algorithmes utilisés dans les systèmes de cryptographie à flux sont destinés à être utilisés dans les systèmes de communication militaires et gouvernementaux, ainsi que, dans certains cas, à protéger les informations commerciales, ce qui les rend tout naturellement secrètes et inaccessibles à l'examen. Les seuls algorithmes standards pour le chiffrement symétrique de flux sont la norme américaine DES (modes CFB et OFB) et la norme russe GOST 28147-89 (mode gamma).

Le fonctionnement des cryptosystèmes de flux repose sur des générateurs de séquences aléatoires ou pseudo-aléatoires. Examinons cette question plus en détail.

2 Générateur de nombres pseudo-aléatoires

Les clés secrètes représentent la base des transformations cryptographiques pour lesquelles, selon la règle de Kerkhoffs, la force du cryptosystème est déterminée uniquement par le secret de la clé. Le principal problème de la cryptographie classique a longtemps été la difficulté de générer une clé secrète. La modélisation physique du caractère aléatoire à l'aide de phénomènes physiques tels que le rayonnement radioactif ou le bruit de tir dans un tube à vide est assez difficile et coûteuse, et l'utilisation de frappes au clavier et de mouvements de souris nécessite des efforts de l'utilisateur et ne fournit pas non plus de véritables processus aléatoires. Par conséquent, au lieu de la modélisation physique, des méthodes de modélisation mathématique du hasard et de génération de séquences aléatoires sous la forme de programmes informatiques ou de dispositifs spécialisés sont utilisées.

Ces programmes et appareils, bien qu'appelés générateurs de nombres aléatoires, génèrent en réalité des séquences déterministes qui semblent uniquement aléatoires dans leurs propriétés et sont donc appelées séquences pseudo-aléatoires. Ils sont tenus de garantir que, même connaissant la loi de formation, mais ne connaissant pas la clé sous la forme de conditions initiales données, personne ne serait capable de distinguer la séquence générée d'une séquence aléatoire, comme si elle était obtenue en lançant un idéal dés.

Générateur de nombres pseudo-aléatoires(PRNG, anglais générateur de nombres pseudo-aléatoires, PRNG) - un algorithme qui génère une séquence de nombres dont les éléments sont presque indépendants les uns des autres et obéissent à une distribution donnée (généralement uniforme).

Il est possible de formuler trois exigences principales auxquelles doivent satisfaire les générateurs cryptographiquement puissants de séquences pseudo-aléatoires ou de gammas.

1. La période gamma doit être suffisamment grande pour chiffrer des messages de différentes longueurs.

2. Le gamma devrait être difficile à prédire. Cela signifie que si le type de générateur et un morceau de gamma sont connus, alors il est impossible de prédire le bit gamma qui suit ce morceau ou le bit gamma qui précède ce morceau.

3. La génération d'une gamme ne doit pas être associée à des difficultés techniques et organisationnelles majeures.

La caractéristique la plus importante d'un générateur de nombres pseudo-aléatoires est la longueur de l'information de sa période, après quoi les nombres se répéteront simplement ou pourront être prédits. Cette longueur détermine pratiquement le nombre possible de clés dans le cryptosystème. Plus cette longueur est longue, plus il est difficile de trouver la clé.

La deuxième des exigences ci-dessus est liée au problème suivant : sur quelle base pouvons-nous conclure que le gamma d'un générateur particulier est vraiment imprévisible ? Jusqu'à présent, il n'existe pas dans le monde de critères universels et pratiquement vérifiables pour vérifier cette propriété. Intuitivement, le hasard est perçu comme une imprévisibilité. Pour qu'un gamma soit considéré comme aléatoire et imprévisible, sa période doit au minimum être très longue et diverses combinaisons de bits d'une certaine longueur doivent être réparties uniformément sur toute sa longueur. Cette exigence peut être interprétée statistiquement comme la complexité de la loi permettant de générer une séquence pseudo-aléatoire de nombres. Si à partir d'un segment suffisamment long de cette séquence, il est impossible de déterminer cette loi de génération ni statistiquement ni analytiquement, alors en principe on peut s'en contenter.

Et enfin, la troisième exigence doit garantir la possibilité de mise en œuvre pratique de générateurs de séquences pseudo-aléatoires, en tenant compte de la rapidité et de la facilité d'utilisation pratique requises. Considérons maintenant quelques méthodes pratiques pour obtenir des nombres pseudo-aléatoires.

3 Méthodes pour obtenir des nombres pseudo-aléatoires

L'une des premières méthodes de ce type fut celle proposée en 1946 par D. von Neumann. Cette méthode était basée sur le fait que chaque nombre suivant dans une séquence pseudo-aléatoire était formé en mettant au carré le nombre précédent et en supprimant les chiffres aux deux extrémités. Cependant, cette méthode s’est avérée peu fiable et a été rapidement abandonnée. Une autre méthode est la méthode dite congruente.

3.1 Méthode linéaire congruente

La méthode linéaire congruente est l'un des algorithmes permettant de générer des nombres pseudo-aléatoires. Il est utilisé dans des cas simples et n’a pas de force cryptographique. Inclus dans les bibliothèques standards de divers compilateurs.

Cet algorithme consiste à appliquer de manière itérative la formule suivante :

où a>0, c>0, m>0 sont des constantes entières. La séquence résultante dépend du choix du numéro de départ X0 et pour différentes valeurs de celui-ci, différentes séquences de nombres aléatoires sont obtenues. En même temps, de nombreuses propriétés de la séquence Xj sont déterminés par le choix des coefficients dans la formule et ne dépendent pas du choix du numéro de départ. Il est clair que la séquence de nombres générée par un tel algorithme est périodique avec une période n'excédant pas m. Dans ce cas, la durée du délai est égale à m si et seulement si :

· PGCD (c, m) = 1 (c'est-à-dire que c et m sont premiers entre eux) ;

· a - 1 multiple de p pour tous les p - diviseurs premiers de m ;

· a - 1 est un multiple de 4 si m est un multiple de 4.

Les propriétés statistiques de la séquence de nombres aléatoires résultante sont entièrement déterminées par le choix des constantes un Et cà une profondeur de bits donnée e. Pour ces constantes, des conditions sont écrites qui garantissent une qualité satisfaisante des nombres aléatoires résultants.

Le tableau ci-dessous présente les paramètres les plus couramment utilisés des générateurs de congruences linéaires, notamment dans les bibliothèques standards de différents compilateurs (fonction rand()).

3.2 Méthode de Fibonacci

Une classe intéressante de générateurs de séquences pseudo-aléatoires est basée sur l’utilisation de séquences de Fibonacci. Un exemple classique d'une telle séquence est (0,1,1,2,3,5,8,13,21,34...) - à l'exception de ses deux premiers membres, chaque membre suivant est égal à la somme des deux précédents.

Les caractéristiques de distribution des nombres aléatoires générés par l’algorithme linéaire congruent rendent impossible leur utilisation dans des algorithmes statistiques nécessitant une haute résolution.

À cet égard, l'algorithme congruent linéaire a progressivement perdu de sa popularité et sa place a été prise par la famille des algorithmes de Fibonacci, dont l'utilisation peut être recommandée dans les algorithmes critiques pour la qualité des nombres aléatoires. Dans la littérature anglophone, les capteurs de Fibonacci de ce type sont généralement appelés « Subtract-with-borrow Generators » (SWBG).

Les capteurs de Fibonacci ont acquis la plus grande popularité en raison du fait que la vitesse d'exécution des opérations arithmétiques avec des nombres réels est devenue égale à la vitesse de l'arithmétique des nombres entiers, et les capteurs de Fibonacci sont naturellement implémentés dans l'arithmétique réelle.

L'un des capteurs de Fibonacci les plus utilisés est basé sur la formule itérative suivante :

Où X k - nombres réels de la plage )