Un générateur de nombres pseudo-aléatoires, (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les nombres sont supposés être suffisamment indépendants les uns des autres, et il est potentiellement difficile de repérer des groupes de nombres qui suivent une certaine règle (comportements de groupe).
Un algorithme déterministe génère des suites de nombres qui ne peuvent pas satisfaire complètement les critères mathématiques qualifiant les suites aléatoires. On les appelle suites pseudo-aléatoires, car leurs propriétés s'approchent seulement des propriétés idéales des suites aléatoires parfaites. Comme le faisait remarquer ironiquement John von Neumann : disait-il . De vrais nombres aléatoires peuvent être produits avec du matériel qui tire parti de certaines propriétés physiques stochastiques (bruit électronique d'une résistance par exemple).
Les méthodes pseudo-aléatoires sont souvent employées sur des ordinateurs, dans diverses tâches comme la méthode de Monte-Carlo, la simulation, l'analyse numérique, la programmation (génération de tests), l'aide à la décision, les applications cryptographiques, les algorithmes probabilistes et les jeux. Différentes raisons justifient de se satisfaire d’un rendu pseudo-aléatoire, parmi lesquelles : il est difficile d’obtenir des nombres véritablement aléatoires et, dans certaines situations, l'utilisation de nombre pseudo-aléatoires suffit en lieu et place de nombres réellement aléatoires, c'est le cas des algorithmes de Las Vegas ; les programmes générateurs de nombres aléatoires sont particulièrement adaptés à une implémentation informatique, donc plus facilement et plus efficacement utilisables ; dans certaines circonstances (par exemple en modélisation Monte-Carlo), nous devons effectuer plusieurs fois des calculs avec la même suite de nombres aléatoires : régénérer cette suite à partir de l'algorithme est plus efficace que de la stocker en mémoire.
Une analyse mathématique rigoureuse est nécessaire pour déterminer le degré d'aléa d'un générateur pseudo-aléatoire. Robert R. Coveyou, de l'Oak Ridge National Laboratory, écrivit, dans un article, que « la génération de nombres aléatoires est trop importante pour être confiée au hasard »Citation originale : « » ; ..
La plupart des algorithmes de génération de nombres pseudo-aléatoires essaient de produire des sorties qui sont uniformément distribuées ; à partir d'une suite uniforme, il existe des méthodes pour générer des suites de nombres selon les principales lois de probabilité (par exemple la méthode de la transformée inverse). Une classe très répandue de générateurs utilise une congruence linéaire. D'autres s'inspirent de la suite de Fibonacci en additionnant deux valeurs précédentes ou font appel à des registres à décalage à rétroaction linéaire, dans lesquels le résultat précédent est injecté après une transformation intermédiaire. Certains générateurs pseudo-aléatoires sont dits cryptographiques quand certaines contraintes sont satisfaites. Citons entre autres Fortuna, Yarrow ou Blum Blum Shub.
Problèmes expliquant le terme « pseudo-aléatoire »
Un générateur pseudo-aléatoire est un algorithme déterministe, donc une suite finie et non ambiguë d’opérations ; à partir d'un nombre de départ donné, il générera toujours la même suite. Utiliser des algorithmes déterministes pour créer des nombres aléatoires peut donc paraître paradoxal.
Ces reproches sont tout à fait fondés et indéniables, raisons pour lesquelles on utilise l’adjectif . En pratique, il est possible de limiter les conséquences négatives de l’utilisation d’une méthode algorithmique pour générer des nombres aléatoires.
Biais inhérent aux méthodes employées Comme un générateur de nombres aléatoires est exécuté sur un ordinateur déterministe, il devient de facto un algorithme déterministe. Ses sorties sont inévitablement entachées d'une caractéristique absente d'une vraie suite aléatoire : la périodicité. Avec des ressources limitées (mémoire, nombre de registres, etc.), le générateur retrouvera le même état interne au moins deux fois. Après coup, il entrera obligatoirement dans un cycle. Un générateur non périodique n'est pas impossible, mais nécessite une mémoire croissante pour ne pas se retrouver dans le même état. Pour contourner cet obstacle théorique, le générateur peut commencer dans un état quelconque (la « graine »). Il produira toutefois la même suite si la graine reste identique — ce qui peut être considéré comme un avantage sous certaines conditions, notamment en termes de reproductibilité. De plus, le nombre de graines possibles n'est pas infini et le générateur ne peut produire qu'un nombre limité de séquences différentes.
Pour améliorer la qualité des sorties, on peut introduire des composantes « aléatoires » provenant des imperfections du système, comme le temps entre deux accès au disque dur ou le nombre de millisecondes depuis le lancement de l'ordinateur. Ces valeurs sont toutefois comprises entre certains intervalles et/ou sont en partie prévisibles. Le système reste pseudo-aléatoire.
Déviation par rapport au hasard parfait La longueur de la période maximale double à chaque fois qu'un bit est ajouté à l'état interne. Il est facile de construire des générateurs pseudo-aléatoires avec une période plus longue que ce que n'importe quel ordinateur pourrait calculer. Mersenne Twister, un excellent générateur de nombres aléatoires pour les applications non cryptographiques, a une période prouvée mathématiquement de 219937-1.
La question est ouverte quant à savoir s'il est possible de distinguer une suite pseudo-aléatoire générée algorithmiquement d'une source parfaite d'aléa, et ceci sans connaître la graine du générateur. En cryptographie, la plupart des spécialistes partent du principe que c'est une chose impossible avec la puissance de calcul actuelle. Ce principe est utilisé pour les chiffrements par flot comme RC4 qui procède à un XOR entre une suite pseudo-aléatoire et les données.
En principe, la plupart des générateurs ont des problèmes mathématiques qui peuvent être décelés avec une analyse statistique. La qualité des sorties augmente souvent au détriment de la vitesse de génération et ces paramètres doivent être considérés lors de l'utilisation d'un générateur. Les failles peuvent être les suivantes : période plus courte avec certaines graines qualité du générateur qui varie fortement selon la graine distribution imparfaite, manque d'uniformité mauvaise distribution dans un espace de dimension supérieure à 1 (Théorème de Marsaglia) ou au contraire : distribution trop idéale, uniformité trop parfaite valeurs successives qui ne sont pas indépendantes (ce qui est toujours le cas, sauf si on injecte des données, issues de sources aléatoires, dans une étape de la génération) certains bits dans les sorties sont moins aléatoires (par exemple, le bit reste souvent à 1)
Les défauts peuvent être importants ou quasiment invisibles. L'algorithme RANDU utilisé pendant plusieurs décennies était biaisé et certains résultats obtenus à l'époque ne peuvent être complètement validés. Il arrive parfois qu'une application pratique permette de déceler le problème (par exemple une simulation physique avec des résultats complètement inattendus), mais il est préférable de faire des tests avant utilisation pour les déceler.
Historique du développement des générateurs pseudo-aléatoires
, 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 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 les algorithmes ACORN (1989) ou Mersenne Twister (1997) ou encore la Méthode de Fibonacci lacunaire.
Une théorie solide sur laquelle se fonde la nature mathématique du concept de suite aléatoire s'est développée et s'appelle la théorie de la complexité de Kolmogorov.
Mais aucun algorithme pseudo-aléatoire ne peut vraiment générer de suite à l’abri de toute analyse statistique, en particulier parce que la « graine » doit en théorie être elle-même aléatoire, et que 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 engendrée de façon déterministe : on s’oriente donc vers des générateurs hybrides, fondés sur un algorithme robuste de génération de nombres pseudo-aléatoires, et s’initialisant grâce à un moyen physique de production de hasard.
Exemples d'algorithmes connus La méthode de Von Neumann En 1946, John von Neumann propose un générateur pseudo-aléatoire connu sous le nom de la méthode du carré médian. Très simple, elle consiste à prendre un nombre, à l'élever au carré et à prendre les chiffres au milieu comme sortie. Celle-ci est utilisée comme graine pour l'itération suivante.
Exemple Soit le nombre « 1111 ». 11112 = 1234321 on récupère les chiffres du milieu : 3432. C'est la sortie du générateur. 34322 = 11778624 on récupère les chiffres du milieu : 7786.
et ainsi de suite.
Défauts Von Neumann utilisa des nombres comportant 10 chiffres, le principe restant le même. Toutefois, la période du est faible. La qualité des sorties dépend de la graine, « 0000 » produit toujours la même séquence et constitue un « état absorbant » de l'algorithme. Von Neumann en était conscient, mais il craignait que des retouches a priori nécessaires n'apportent d'autres vices cachés. Sur l'ordinateur ENIAC qu'il utilisait avec sa méthode, il obtenait une génération 200 fois plus rapide que les résultats obtenus avec des cartes perforées. Selon Von Neumann, les générateurs basés sur du matériel ne pouvaient pas fonctionner correctement car ils ne stockaient pas les résultats (et on ne pouvait donc pas les vérifier). La méthode de Von Neumann montra vite ses limites lors d'applications utilisant des méthodes statistiques comme celle de Monte Carlo.
Méthode de Fibonacci Cette méthode est basée sur la suite de Fibonacci modulo la valeur maximale désirée :
On peut employer une variante :
La qualité du générateur dépend de et des nombres utilisés pour initialiser la suite. Ce générateur est par contre très simple à implémenter et ne consomme que peu de ressources.
Générateurs congruentiels linéaires