Générateur de nombres aléatoires, gratuit

Une brève histoire de l'aléatoire en informatique

Les ordinateurs sont des machines déterministes, ce qui rend l'« aléatoire » étrange à produire. L'histoire des générateurs de nombres pseudo-aléatoires (PRNG) sur ordinateur commence avec la méthode du carré médian de John von Neumann en 1946, élever au carré le nombre précédent, prendre les chiffres du milieu comme nouvelle valeur, recommencer. L'avertissement que von Neumann a lui-même prononcé au symposium RAND de 1949 était plus tranchant que la méthode : « Quiconque envisage des méthodes arithmétiques de production de chiffres aléatoires se trouve, bien entendu, en état de péché. » Le carré médian a des modes de défaillance évidents (il revient à zéro, ses périodes sont courtes). Le générateur congruentiel multiplicatif de Lehmer (présenté à Berkeley en 1949, publié en 1951), x_(n+1) = (a × x_n) mod m, est la première famille de PRNG aux propriétés statistiques raisonnables ; Thomson et Rotenberg (1958) ont ensuite généralisé la famille avec une constante additive pour donner le x_(n+1) = (a × x_n + c) mod m complet, le générateur congruentiel linéaire (LCG). La rand() de la bibliothèque standard C utilise toujours typiquement une variante LCG. Le Mersenne Twister (Matsumoto et Nishimura, 1997-1998) nous a donné un générateur d'une période de 2¹⁹⁹³⁷−1 (un nombre à 6 000 chiffres) et d'une équidistribution à 623 dimensions ; il est devenu le défaut en Python, R, MATLAB, PHP et de nombreux autres langages. La famille xorshift de Marsaglia (2003) est bien plus rapide et assez petite pour tenir dans un registre matériel ; le V8 moderne (le moteur JavaScript de Chrome) utilise une variante xorshift128+ pour Math.random(). PCG (Permuted Congruential Generator) de Melissa O'Neill (2014) est l'état de l'art statistique actuel pour les PRNG non cryptographiques, combinant l'avancement d'état façon LCG avec une permutation de sortie pour d'excellentes propriétés statistiques à faible coût.

Les PRNG cryptographiquement sûrs (CSPRNG) sont une autre bête. Propriété définissant : même si un attaquant connaît chaque sortie produite par le générateur, il ne peut pas prédire la sortie suivante avec mieux qu'un avantage négligeable. L'appel système getrandom() de Linux (ajouté dans le noyau 3.17, octobre 2014) et le /dev/urandom sous-jacent utilisent un générateur basé sur ChaCha20 amorcé par des sources d'entropie matérielles (RDRAND, timing d'interruptions, bruit audio). BCryptGenRandom de Windows utilise une construction AES-CTR-DRBG (NIST SP 800-90A) amorcée à partir de plusieurs sources d'entropie. macOS / iOS utilisent la famille arc4random, à l'origine un CSPRNG fondé sur RC4 et réécrit autour de ChaCha20 vers 2013. La différence entre PRNG et CSPRNG compte énormément : un PRNG convient pour l'aléatoire de jeu, le bucketing d'A/B testing ou les simulations ; pour tout ce qu'un attaquant pourrait essayer de prédire (jetons de session, génération de mots de passe, identifiants de sécurité), seul un CSPRNG est sûr.

Les deux API aléatoires de JavaScript

Math.random() est l'API plus ancienne et plus simple, elle renvoie un nombre à virgule flottante approximativement uniformément distribué dans [0, 1). La spécification ECMAScript laisse délibérément l'algorithme sous-jacent non spécifié (« approximately uniform distribution between 0 and 1, exclusive »), et les moteurs ont changé ce qu'ils utilisent au fil des années. V8 (Chrome) a utilisé un générateur multiplicatif avec retenue (MWC1616) pendant des années, puis est passé à xorshift128+ en 2015 pour de meilleures propriétés statistiques. SpiderMonkey (Firefox) et JavaScriptCore (Safari) utilisent des générateurs non cryptographiques rapides similaires. Math.random() est suffisamment rapide et uniforme pour les mécaniques de jeu, les simulations et toute application où l'imprévisibilité n'est pas une exigence de sécurité. Il n'est pas cryptographiquement sûr, la période est définie par l'implémentation, l'état peut être récupéré à partir d'un petit nombre de sorties, et la séquence n'est pas sûre pour la génération de mots de passe ou les cas d'usage sensibles à la sécurité. crypto.getRandomValues() est le CSPRNG de la Web Crypto API. Il remplit un tableau typé d'octets aléatoires cryptographiquement sûrs tirés du CSPRNG du système d'exploitation (la même source que TLS utilise pour les clés de session). Disponible dans tous les navigateurs modernes depuis environ 2014 ; la taille maximale du tampon en un seul appel est de 65 536 octets. Le bon choix pour tout nombre aléatoire qui compte, génération de jeton, identifiants de sécurité, génération de mots de passe, tout ce qu'un attaquant pourrait essayer de prédire.

Le piège du biais de modulo

Générer un entier uniforme dans une plage spécifique à partir d'un CSPRNG est plus difficile qu'il n'y paraît. L'approche naïve, crypto.getRandomValues(new Uint8Array(1))[0] % 6 pour un lancer de dé, produit une distribution biaisée parce que 256 ne se divise pas de façon égale par 6. Les valeurs 0-3 apparaissent chacune 43 fois dans la plage 0-255 ; les valeurs 4-5 apparaissent 42 fois. Le biais est faible pour les petites plages mais réel, et détectable sur de longues séries. La correction standard est l'échantillonnage par rejet : générer un octet aléatoire, tester s'il tombe dans le plus grand multiple de votre plage qui rentre (ici, 252 = 42 × 6), l'utiliser si oui, le jeter et réessayer si non. Le taux de rejet est borné par (plage / prochaine puissance de 2), donc pour « 1-6 » vous gaspillez environ 1,5 % des octets ; pour « 1-1000000 » contre un entier aléatoire 32 bits, vous gaspillez environ 0,02 %. Toute bibliothèque aléatoire sérieuse implémente l'échantillonnage par rejet ; le Math.floor(Math.random() * (max - min + 1)) + min à base de Math.random() évite le biais parce que la précision de Math.random() est suffisamment élevée (53 bits de mantisse) pour que le biais soit en dessous des niveaux humainement détectables sur toute plage raisonnable. Ce générateur utilise la sortie CSPRNG avec échantillonnage par rejet, sortie uniforme sur n'importe quelle plage entière demandée.

Cas d'usage et niveau d'aléatoire requis pour chacun

• Tirages de loterie et tombolas. Pour les tirages non monétaires (échanges de bureaux, attribution d'équipes pour un hackathon, plan de classe), Math.random() convient. Pour les tirages monétaires ou tout ce qui est régulé, utilisez un CSPRNG et idéalement publiez la graine pour la vérifiabilité.
• Mécaniques de jeu. Lancers de dés, mélanges de cartes, butin, génération procédurale. Math.random() est le choix standard, rapide, suffisamment uniforme, suffisamment imprévisible pour que les joueurs ne remarquent pas de motifs. Les CSPRNG sont réservés aux jeux de cartes en ligne où le serveur doit empêcher la triche.
• Attribution de buckets pour A/B testing. Hasher l'identifiant utilisateur avec un secret stable pour placer chaque utilisateur dans un bucket de manière déterministe ; utiliser Math.random() signifierait qu'un utilisateur atterrit dans des buckets différents au fil des chargements de page, ce qui ruinerait l'expérience. L'attribution par hachage est le bon motif ; l'aléatoire ne sert qu'à choisir la graine de l'expérience, une seule fois.
• Échantillonnage aléatoire pour des sondages. Tirer un sous-ensemble représentatif d'une population. Math.random() convient ; la question statistique est de savoir si votre échantillon est assez grand, pas si la source aléatoire est cryptographique.
• Génération de données de test. Faker, données de maquette, fixtures synthétiques de base de données. Math.random() avec une graine fixe (pour la reproductibilité) est le bon choix.
• Clés cryptographiques, jetons de session, génération de mots de passe. CSPRNG uniquement, crypto.getRandomValues() dans le navigateur, le module secrets en Python, crypto/rand en Go, jamais l'aléatoire par défaut du langage. Un bug dans cette couche compromet tout ce qui en dépend ; les conséquences vont de « la session de chacun est piratable » à « la clé de chiffrement est récupérable ».

RANDOM.ORG et la distinction du véritable aléatoire

RANDOM.ORG a été lancé en 1998 par Mads Haahr au Trinity College Dublin et reste la référence du « vrai aléatoire » en ligne. Là où chaque CSPRNG dérive en dernier ressort ses bits de transformations algorithmiques d'un état amorcé matériellement (un processus déterministe, même si imprévisible pour un attaquant), RANDOM.ORG mesure le bruit atmosphérique capté par des récepteurs radio et convertit ce bruit analogique directement en bits. Cela en fait un True Random Number Generator (TRNG) plutôt qu'un Pseudo-Random Number Generator : les bits viennent d'un processus physique authentiquement non-déterministe, pas d'un algorithme déterministe. RANDOM.ORG est utilisé par des opérateurs de loterie, des chercheurs académiques menant des études en double aveugle et des jeux où l'aléa vérifiable compte. Le compromis : un aller-retour réseau par requête, un quota journalier pour le palier gratuit, et la question philosophique de savoir si vous faites confiance à la source d'entropie revendiquée par RANDOM.ORG plutôt qu'à votre CSPRNG local. Pour la plupart des usages, le CSPRNG local suffit ; pour les cas où une tierce partie doit vérifier l'aléatoire indépendamment, RANDOM.ORG fournit des certificats d'aléa signés en service payant.

Échantillonnage sans remise, le mélange de Fisher-Yates

Lorsque vous avez besoin de N nombres uniques dans une plage, tirer 6 numéros entre 1 et 49 pour une loterie, sélectionner 10 gagnants parmi 1 000 inscrits, le naïf « générer et rejeter si doublon » fonctionne pour de petits N mais se dégrade fortement quand N approche la taille de la plage (la chance de tirer un nombre frais baisse à mesure que le pool rétrécit). L'algorithme standard est le mélange de Fisher-Yates, originaire des tables statistiques de Fisher et Yates de 1938 et mis sous sa forme moderne en informatique par Donald Knuth en 1969 (parfois appelé Knuth shuffle). L'algorithme est extrêmement simple : écrire les nombres 1 à N dans un tableau ; pour i de N-1 à 1, échanger l'élément i avec un élément aléatoire entre 0 et i (inclus) ; le tableau est maintenant uniformément mélangé. Prendre les K premiers éléments pour K nombres aléatoires uniques. Le détail crucial : l'indice aléatoire doit être dans [0, i], inclus, utiliser [0, i-1] donne plutôt l'algorithme de Sattolo (Sandra Sattolo, 1986), qui produit des permutations cycliques uniformes plutôt que des permutations aléatoires uniformes et est parfois confondu à tort avec le vrai Fisher-Yates. Pour des plages très grandes où allouer un tableau de toutes les N valeurs n'est pas pratique (par exemple choisir 100 valeurs uniques entre 1 et 10⁹), l'échantillonnage par réservoir (Vitter, 1985) gère les entrées en flux ou non bornées en une seule passe avec mémoire bornée.

Conventions de lancers de dés

Les générateurs de nombres aléatoires sont des dés déguisés. Le D6 (dé à six faces) est le défaut universel des jeux de plateau, plage 1-6. Le D20 (dé à vingt faces) est le dé iconique de Donjons et Dragons utilisé pour les tests de capacité, les jets d'attaque et les jets de sauvegarde, le système de modificateurs de D&D fait qu'un seul jet de D20 plus un bonus de stat détermine l'issue de la plupart des actions. Le D100 (centile, 1-100) est utilisé pour les jets en pourcentage dans L'Appel de Cthulhu, Warhammer Roleplay et de nombreux systèmes de chance critique. La notation NdM signifie « lancer N dés à M faces chacun et sommer » ; NdM+B ajoute un bonus. 3d6 lance trois dés à six faces et somme (plage 3-18, la plage classique des scores de capacité D&D, avec une distribution triangulaire centrée autour de 10-11). Pour une simulation équitable, générer un entier uniforme dans [1, M] pour chaque dé et sommer est exactement équivalent à lancer des dés physiques, la distribution CSPRNG sous-jacente est plus uniforme que tout dé physique que vous puissiez acheter. Les casinos et les jeux régulés utilisent des RNG certifiés testés contre des batteries statistiques (BigCrush de TestU01, NIST SP 800-22) pour prouver l'uniformité aux régulateurs ; les mêmes standards s'appliquent aux RNG de loterie.

Graines et reproductibilité

Une propriété subtile mais importante des PRNG : ils sont déterministes pour une graine donnée. Fixez la graine à une valeur connue, et la séquence des nombres « aléatoires » est exactement reproductible. C'est inestimable pour les tests (un test unitaire qui utilise des données aléatoires devrait fixer une graine pour que les échecs soient reproductibles) et pour les tirages vérifiables (publier la graine avant le tirage, puis n'importe qui peut vérifier le résultat). Le module random de Python a random.seed(value) pour cela ; Random de Java prend une graine dans le constructeur. Le Math.random() de JavaScript n'expose délibérément pas d'API d'amorçage, les moteurs traitent la graine comme un état interne, mais plusieurs bibliothèques pures-JS (seedrandom, pcg-random) fournissent des PRNG amorcés. Les CSPRNG sont par conception différents : ils n'exposent pas d'amorçage car le sens même est l'imprévisibilité. Si vous avez besoin de reproductibilité, utilisez un PRNG avec amorçage explicite ; si vous avez besoin de sécurité, utilisez un CSPRNG et acceptez que vous ne pouvez pas reproduire la séquence ensuite.

Vie privée : pourquoi navigateur uniquement, même pour des nombres aléatoires

Les nombres aléatoires eux-mêmes contiennent rarement des informations sensibles, alors pourquoi l'architecture purement navigateur compte-t-elle ? Deux raisons. D'abord, lorsqu'un nombre aléatoire est utilisé comme jeton de session, clé d'idempotence, défi d'authentification ou toute autre valeur secrète, le générer sur un serveur tiers signifie que ce serveur a vu la valeur avant que vous ne l'utilisiez, une exposition petite mais réelle. Ensuite, les générateurs côté serveur qui promettent de l'« aléa cryptographique » ne peuvent pas être vérifiés par l'utilisateur ; un serveur bogué ou malveillant pourrait renvoyer des valeurs non-aléatoires ou biaisées qui semblent aléatoires, et vous n'auriez aucun moyen de détecter le biais sans un échantillonnage massif. Un générateur navigateur uniquement exécute le même appel crypto.getRandomValues() que votre application exécuterait côté serveur ; l'entropie vient de la même source du système d'exploitation (Linux getrandom(), Windows BCryptGenRandom, macOS) ; aucune tierce partie ne voit la sortie. Vous pouvez vérifier en ouvrant l'onglet Network des DevTools pendant que vous cliquez sur Générer, il n'y a pas de requêtes sortantes. Mettez la page hors ligne (mode avion) après son chargement et le générateur fonctionne toujours.

Questions fréquentes