Générateur de nombres pseudo-aléatoires - Définition

Historique du développement des générateurs pseudo-aléatoires

Le développement des algorithmes générant des nombres pseudo-aléatoires est très lié à celui de la cryptographie, l’importance militaire et économique de cette science ayant motivé de nombreuses recherches au cours de l’histoire.

Les chiffrements utilisés traditionnellement jusqu’au XIX^e siècle reposaient essentiellement sur le secret autour de la méthode utilisée, et sur l’absence de traitement de masse. De nos jours, de telles méthodes sont impraticables car il existe de nombreuses théories statistiques qui permettent de retrouver l’algorithme de génération à partir de ses résultats. En outre, les techniques de chiffrement ne peuvent plus être gardées secrètes, et en 1883, Auguste Kerckhoffs exposera une règle fondamentale de la cryptographie moderne : la sécurité d’un système ne doit pas reposer sur la méconnaissance de la méthode de chiffrement. Cette règle, accompagnée par le développement des algorithmes de chiffrement par clé, marquera le début de l’essor des générateurs pseudo-aléatoires.

Leur importance est toutefois restée limitée tant que les moyens physiques de calcul n’ont pu supporter les longs et répétitifs calculs qu’ils nécessitent. C’est pourquoi leur émergence n’a vraiment commencé qu’en 1946, quand John von Neumann publie son générateur middle-square. C'est durant les années qui suivirent que la plupart des algorithmes rapides et populaires virent le jour : en 1948 D. H. Lehmer introduit les générateurs congruentiels linéaires qui seront améliorés en 1958 par G.J. Mitchell et D.P. Moore ; et deviendront par la suite extrêmement répandus, la plupart des fonctions de chiffrement basique y ayant recours.

Ces premiers générateurs pseudo-aléatoires possèdent malgré leur large popularité des propriétés statistiques assez mauvaises, et ne répondaient pas aux besoins des cryptographes. Plus récemment, des algorithmes robustes vis-à-vis des analyses statistiques ont été élaborés, comme l’algorithme Mersenne Twister (1997) ou encore la Méthode de Fibonacci lacunaire.

Mais aucun algorithme pseudo-aléatoire ne peut vraiment générer de suite à l’abri de toute analyse statistique, en particulier car la « graine » doit en théorie être elle-même aléatoire, et l’algorithme utilisé ne peut s’initialiser lui-même. Les générateurs cryptographiques actuels sont donc obligés de faire intervenir une part de hasard qui n’est pas générée par un moyen déterministe : on s’oriente vers des générateurs hybrides, possédant un algorithme de génération de nombres pseudo-aléatoires robuste, et s’initialisant sur un moyen physique de production de hasard.

Domaines d'application

Les générateurs pseudo-aléatoires ont, à travers le temps, acquis une grande importance dans divers domaines, allant du médical à la sécurisation, et se sont montrés être d’une grande efficacité quant à leurs apports dans ces domaines.

Confidentialité des échanges sur les réseaux sans fils

L’échange par réseaux sans fil pose de nombreux problèmes concernant la confidentialité des éléments échangés. Ceci dit, il faut alors un mécanisme qui peut conserver le mieux possible cette confidentialité, ce mécanisme est alors le WEP pour Wired Equivalent Privacy. Le principe consiste à définir une clé chiffrée sur une longueur allant de 40 à 128 bits. Ensuite, la clé est déclarée au niveau du point d’accès et du client. Le but de la clé est de créer un nombre pseudo aléatoire d’une longueur égale à celle de la trame de transmission. Le nombre pseudo aléatoire ainsi généré sert à chiffrer la transmission, et alors à assurer la confidentialité de cette dernière.

Toutefois, le WEP n’assure malheureusement pas une sécurité optimale, les compagnies Fluhrer et Shamir ont montré que la génération de la chaîne pseudo aléatoire rend possible la découverte de la clé de session en stockant 100 Mo à 1 Go de trafic créé intentionnellement. 24 bits de la clé sont dédiés à l’initialisation, ce qui veut dire que chiffrer à 128 bits est de loin meilleur que de chiffrer à 64 bits dans la mesure où chiffrer à 128 bits offre une possibilité réelle de chiffrer à 104 bits, tandis que chiffrer a 64 bits n’en offre que 40 bits.

Sécurisation des applications web

Les applications WEB qui ont pour utilisateurs les navigateurs WEB ont un système qui sert à protéger leurs clients par la création de sessions. Les sessions sont des espaces de travail qui ont un espace de stockage d’informations connu, elles sont aussi privées et appartiennent à un utilisateur particulier dûment authentifié.

Néanmoins, ces sessions ne présentent pas toujours le niveau de sécurité souhaité. C’est ici qu’interviennent les nombres pseudo aléatoires. L’exemple le plus connu est celui d’attaque par session de type prédiction (méthode de détourner ou de personnifier un utilisateur WEB, elle s’accomplit par la déduction ou l'estimation de la valeur unique qui identifie la session associée). Pour éviter ce genre d’attaques, il est devenu courant d’utiliser un gestionnaire d’applications WEB capable de générer des identifiants qu’on ne peut pas prévoir. Il n’y a plus à chercher, car les applications de génération de nombres pseudo aléatoires ont été suffisamment développées pour ce faire.

Système de chiffrement

La cryptanalyse est une discipline récente, et signe un grand niveau de fiabilité quant aux méthodes de chiffrement qu’elle utilise, notamment le chiffrement par flot. Ce dernier consiste à additionner bit à bit au message clair une suite binaire pseudo aléatoire de même longueur appelée suite chiffrante. Ce procédé est reconnu pour sa rapidité et sa compétitivité vis-à-vis des autres procédés dans la mesure où il est peu sensible aux erreurs introduites lors de la transmission. Des registres à décalage avec rétroaction linéaire font souvent partie des générateurs pseudo aléatoires utilisés pour produire les suites chiffrantes.

Domaine biomédical

Une application importante au niveau biomédical concerne l’amélioration de la modélisation du dépôt de dose dans le corps et aussi pour accélérer le calcul de traitement. En effet, sur les grilles de calcul, il est impératif que chaque processus de calcul puisse disposer d’une sous séquence aléatoire issue d’une séquence globale de nombres aléatoires à générer. L’un des fruits des recherches menées à ce sujet, est la plate-forme de simulation Monte-Carlo GATE, qui est un logiciel de calcul de dépôt de dose sur plusieurs grappes, et qui a permis de mettre en évidence des facteurs d’accélération de l’ordre de 30 du temps de calcul en comparaison avec une utilisation en milieu hospitalier.

Une application originale : le GPS

Les codes pseudo-aléatoires connaissent une application originale dans le cadre du système de localisation par satellites GPS. Ils y sont en effet utilisés non pas en fonction de leur prévisibilité vis-à-vis d’une analyse extérieure pour protéger des données, mais parce qu’ils présentent une séquence connue, facile à calculer, et qui n’a aucune similitude avec les séquences obtenues en changeant de graine.

Ces caractéristiques sont utiles aux GPS à cause de l’utilisation qui en est faite : le but est de mesurer une distance entre deux équipements, en l’occurrence un satellite de la constellation GPS et un récepteur.

Cette mesure est réalisée en générant une séquence pseudo-aléatoire sur chacun des équipements, que l’on supposera synchronisés, et générant la séquence à la même vitesse. La séquence du satellite est alors modulée et transmise au récepteur, qui la compare a sa propre séquence. Il y a alors un décalage entre les deux chaînes, et ce décalage correspond au temps de propagation de l’information du satellite au récepteur. Il suffit alors de mesurer ce décalage, de le multiplier par la vitesse des ondes électromagnétiques dans l’air et on obtient la distance recherchée.

Ce principe est toutefois contrarié dans la réalité par de multiples facteurs qui conditionnent le choix du générateur pseudo-aléatoire à utiliser :

• Les séquences générées par les codes pseudo-aléatoires ne sont pas infinies et se répètent périodiquement, la période dépendant du code utilisé et de la machine sur laquelle il est implanté. Ce « défaut » entraîne une ambiguïté sur la distance mesurée par le récepteur : le décalage mesuré est de t, mais il peut aussi être de t+T (où T est la période de la séquence), de t-T, ou de tout nombre entier de périodes. Il est a priori impossible de lever cette ambiguïté sans traitement informatique qui relie la mesure de distance réalisée a la position du récepteur estimée précédemment. C’est pourquoi une caractéristique importante des codes pseudo-aléatoires utilisés dans le système GPS est leur période, qui doit être la plus longue possible : l’un des codes utilisés, appelé code P, possède une longueur d’onde supérieure au diamètre de la terre, ce qui fait disparaître de problème de l’ambiguïté.

• La vitesse de génération du code par les équipements conditionne la précision de la mesure de distance. En effet, la précision ne pourra jamais être plus grande que la distance élémentaire obtenue en multipliant le temps nécessaire a calculer ou émettre un bit par la vitesse de la lumière. En d’autres termes, on ne peut pas être plus précis que la distance parcourue par le signal du satellite pendant l’émission d’un bit du code. Il est donc primordial de posséder un code généré extrêmement rapidement, et dont la formule de calcul soit la plus simple possible. À titre d’exemple, pour obtenir une précision idéale de l’ordre du mètre, il faudrait générer un bit toutes les 3 nanosecondes.

• La méthode de mesure du décalage entre les deux codes est réalisée par une fonction de corrélation. La première caractéristique que cela impose au code est d’avoir une autocorrélation aussi proche que possible d’un pic de Dirac : si l’autocorrélation du code est importante quand il y a décalage de phase, il deviendra impossible de mesurer le décalage car il y aura ambiguïté entre deux possibles. De même, si entre deux satellites la corrélation des codes n’est pas faible, leurs signaux se perturberont mutuellement et cela rendra la mesure difficile voire irréalisable.

L’ensemble de ces facteurs ont conduit les constructeurs du système GPS à utiliser les codes de Gold. Ces codes, basés sur la combinaison de deux séquences binaires, présentent des caractéristiques intéressantes pour le GPS : ils sont relativement faciles à calculer, et possèdent des périodes appropriées. Le point fort des codes de Gold est leur excellente réponse au 3^e critère : la corrélation de deux codes est faible, que ce soient deux codes décalés ou différents, et le seul cas ou la corrélation est forte est celui de deux mêmes codes en phase. De ce fait, ils sont très utilisés en télécommunications pour réaliser le multiplexage par codes ou CDMA.