Qu'est-ce qu'un générateur de nombres aléatoires ?
Un générateur de nombres aléatoires (RNG) est un système qui produit des nombres aléatoires ou pseudo-aléatoires. La possibilité de prédire le nombre suivant dépend du type de générateur. Certains générateurs s'appuient sur un processus physique, d'autres calculent leurs valeurs à l'aide d'un algorithme, et certains algorithmes sont conçus de telle sorte que même une personne ayant observé leurs résultats ne peut pas prédire ce qui vient ensuite. Paraître aléatoire et être imprévisible sont deux propriétés différentes, et la majeure partie de cet article est consacrée à cette distinction.
Générateurs matériels de nombres aléatoires
Un générateur matériel de nombres aléatoires (HRNG), également appelé générateur de nombres véritablement aléatoires (TRNG), tire ses valeurs d'un processus physique. Les plus anciens fonctionnent sous nos yeux : une pièce lancée à pile ou face, un dé qu'on jette, une roulette de casino. Les lois de la mécanique décrivent parfaitement chacun d'eux, et pourtant une roulette bien conçue reste imprévisible dans la pratique, car d'infimes variations au départ de chaque lancer se transforment en résultats entièrement différents.
Les générateurs matériels modernes mesurent plutôt des phénomènes microscopiques : le bruit de grenaille et le bruit thermique dans les circuits électroniques, le bruit atmosphérique ou des effets quantiques. Ce sont d'excellentes sources d'entropie — une imprévisibilité qui peut être mesurée —, mais une source physique n'est pas parfaite par nature : elle peut être biaisée, dériver et tomber en panne. Sa qualité doit donc être évaluée et surveillée, et ses valeurs retraitées si nécessaire, comme le décrivent des normes telles que le NIST SP 800-90B. Les sources matérielles sont utilisées là où les garanties sont indispensables — avant tout en cryptographie, où elles fournissent la matière première imprévisible pour les clés des protocoles tels que Transport Layer Security (TLS).
Générateurs de nombres pseudo-aléatoires
L'alternative à un dispositif physique est un algorithme. Un générateur de nombres pseudo-aléatoires (PRNG) produit une séquence qui semble aléatoire mais qui est entièrement déterminée par une valeur initiale appelée graine (seed). Donnez la même graine au même algorithme et vous obtiendrez la même séquence à chaque fois. Il s'agit d'une faiblesse dès lors qu'un résultat doit être imprévisible et que la graine ou l'état interne peut être deviné ou reconstitué, mais c'est un atout lorsqu'un résultat doit être reproductible — une simulation ou un test peut ainsi être rejoué à l'identique. Les PRNG sont également rapides, peu coûteux et faciles à implémenter, c'est pourquoi la plupart des logiciels reposent sur eux. Parmi les algorithmes les plus connus figurent le générateur congruentiel linéaire (LCG), les générateurs xorshift et le Mersenne Twister.
Mersenne Twister
Le Mersenne Twister, publié en 1997 par Makoto Matsumoto et Takuji Nishimura, est l'un des générateurs pseudo-aléatoires les plus répandus et le choix par défaut dans de nombreux langages de programmation. Son nom vient de sa période — la longueur de la séquence avant qu'elle ne se répète —, qui correspond dans sa variante standard, MT19937, au nombre premier de Mersenne 219937 − 1. Il réussit la plupart des tests statistiques d'aléatoire et convient bien aux simulations. Il n'a toutefois pas été conçu pour garder des secrets : à partir de 624 valeurs consécutives de 32 bits, n'importe qui peut reconstituer son état interne et prédire chaque valeur suivante. Il ne doit donc jamais être utilisé pour des clés, des mots de passe ou tout autre élément devant rester imprévisible.
Générateurs cryptographiquement sûrs et entropie
De nombreuses applications ont besoin des deux atouts à la fois : la rapidité d'un algorithme et l'imprévisibilité d'une source physique. La réponse réside dans un générateur de nombres pseudo-aléatoires cryptographiquement sûr (CSPRNG). Il s'agit toujours d'un PRNG, mais conçu de façon à ce que l'observation d'une partie de ses résultats ne permette pas, en pratique, de prédire la suite, et il est alimenté, puis régulièrement réensemencé, à partir d'une source d'entropie réelle. Une graine issue d'une source physique ne rend pas un PRNG ordinaire sécurisé pour autant : l'algorithme doit avoir été conçu pour cela. Une source physique comme le bruit thermique ou l'horodatage précis d'événements matériels fournit une petite quantité de véritable aléa, dont le CSPRNG tire une longue suite de valeurs, à un débit bien supérieur. Cette combinaison est précisément ce qu'un système d'exploitation met à la disposition des logiciels, et c'est généralement ce qu'on appelle aujourd'hui un « générateur de nombres aléatoires ». C'est lui qui produit les clés de chiffrement, les jetons de session et les mots de passe.
Nombres aléatoires dans le navigateur
JavaScript offre à une page web deux manières intégrées d'obtenir des valeurs aléatoires, et elles appartiennent à des catégories différentes. Math.random() est un PRNG ordinaire : la norme du langage laisse le choix de l'algorithme à chaque navigateur et ne garantit aucune sécurité — parfait pour une animation, inapproprié pour un tirage au sort que quelqu'un pourrait contester. L'autre solution est la Web Crypto API. Sa méthode crypto.getRandomValues() renvoie des valeurs aléatoires cryptographiquement sûres, produites par un CSPRNG initialisé avec l'entropie du système d'exploitation.
Notre générateur de nombres aléatoires en ligne utilise la Web Crypto API pour chaque tirage, et les nombres sont générés dans votre navigateur plutôt que sur un serveur. La même source alimente les autres générateurs de ce site, que vous souhaitiez lancer des dés, jouer à pile ou face ou générer un mot de passe.
Des bits aléatoires à un nombre dans votre intervalle
Un générateur cryptographiquement sûr ne représente que la moitié d'un tirage équitable. Il fournit des bits bruts, et le programme doit encore les convertir en un nombre situé dans votre plage de valeurs — et c'est ici qu'un biais peut s'insinuer. Supposons que la source fournisse les valeurs de 0 à 9 avec des chances égales et que vous ayez besoin d'un nombre de 0 à 5. Prendre le reste de la division par 6 semble naturel, mais 0, 1, 2 et 3 peuvent alors apparaître chacun de deux manières différentes, tandis que 4 et 5 n'en ont qu'une seule. Ainsi, chacun des nombres de 0 à 3 a 20 % de chances de sortir, contre seulement 10 % chacun pour 4 et 5. Une méthode pour éliminer ce biais consiste à rejeter les valeurs qui ne conviennent pas et à recommencer le tirage ; les guides du générateur de nombres aléatoires détaillent ce mécanisme.
Deux autres aspects surprennent souvent. Les répétitions sont tout à fait normales : lorsqu'un nombre entier de 1 à 10 est tiré de manière indépendante et que chaque nombre a la même probabilité, le nombre qui vient d'apparaître a exactement la même probabilité de 1 sur 10 de ressortir que n'importe quel autre. Un tirage sans doublon est simplement un autre type de tirage, et non un tirage plus aléatoire. De plus, un générateur équitable ne suffit pas à rendre toute une procédure équitable : la liste des participants et le nombre d'essais comptent tout autant, comme l'explique notre article sur la manière de choisir le gagnant d'un concours au hasard.