En quoi les nombres pseudo-aléatoires et les nombres véritablement aléatoires sont-ils différents et pourquoi est-ce important?

Je n'ai jamais vraiment eu ça. Dites simplement que vous écrivez un petit programme dans n'importe quelle langue qui lance des dés (en utilisant les dés comme exemple). Après 600 000 lancers, chaque nombre aurait été roulé environ 100 000 fois, ce à quoi je m'attendais.

Pourquoi existe-t-il des sites Web dédiés au «vrai hasard»? Étant donné l'observation ci-dessus, les chances d'obtenir n'importe quel nombre sont presque exactement égales à 1, quel que soit le nombre de nombres qu'il peut choisir.

Je l'ai essayé en Python : voici le résultat de 60 millions de rouleaux. La variation la plus élevée est de 0,15. N'est-ce pas aussi aléatoire que cela va arriver?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

Jouons au poker informatique, juste vous, moi et un serveur auquel nous faisons confiance. Le serveur utilise un générateur de nombre pseudo-aléatoire qui est initialisé avec une graine 32 bits juste avant de jouer. Il y a donc environ quatre milliards de ponts possibles.

J'ai cinq cartes dans la main - apparemment, nous ne jouons pas au Texas Hold 'Em. Supposons que les cartes soient distribuées une pour moi, une pour vous, une pour moi, une pour vous, etc. J'ai donc les première, troisième, cinquième, septième et neuvième cartes dans le paquet.

Auparavant, j'avais exécuté le générateur de nombres pseudo-aléatoires quatre milliards de fois, une fois avec chaque graine, et noté la première carte générée pour chacune dans une base de données. Supposons que ma première carte est la reine de pique. Cela ne représente qu'une carte parmi les premières cartes sur 52, nous avons donc réduit le nombre de cartes possibles de quatre à environ 80 millions.

Supposons que ma deuxième carte est le trois de coeurs. Maintenant, je lance mon RNG 80 millions de fois en utilisant les 80 millions de graines qui produisent la reine de pique comme premier chiffre. Cela me prend quelques secondes. J'écris tous les paquets qui produisent les trois coeurs comme la troisième carte - la deuxième carte dans ma main. Encore une fois, cela ne représente que 2% environ des ponts. Nous en sommes maintenant à 2 millions.

Supposons que la troisième carte dans ma main est le 7 des clubs. J'ai une base de données de 2 millions de graines qui distribue mes deux cartes; Je lance mon RNG encore 2 millions de fois pour trouver la troisième carte des 2% de ces decks qui produisent les 7 clubs, et il ne reste plus que 40 000 decks.

Vous voyez comment cela se passe. Je lance plusieurs fois mon RNG 40000 pour trouver toutes les graines qui produisent ma quatrième carte, ce qui nous ramène à 800 decks, puis je le lance encore 800 fois pour obtenir les ~ 20 graines qui produisent ma cinquième carte. générer ces vingt jeux de cartes et je sais que vous avez l'une des vingt mains possibles. De plus, j'ai une très bonne idée de ce que je vais dessiner ensuite.

Maintenant, voyez-vous pourquoi le vrai hasard est important? Selon votre description, la distribution est importante, mais ce n’est pas ce qui rend un processus aléatoire. L’imprévisibilité est ce qui rend un processus aléatoire.

MISE À JOUR

D'après les commentaires (maintenant supprimés en raison de leur nature non constructive), au moins 0,3% des personnes qui ont lu ceci sont confus quant à mon point. Quand les gens vont à l' encontre des points que je ne l' ai pas fait, ou pire, faire valoir des points que je ne fais l'hypothèse que je ne les ai pas, je sais que je dois expliquer plus clairement et soigneusement.

Il semble y avoir une confusion particulière autour de la distribution des mots , je tiens donc à rappeler les usages avec soin.

Les questions à résoudre sont les suivantes:

• Comment les nombres pseudo-aléatoires et les nombres vraiment aléatoires diffèrent-ils?
• Pourquoi la différence est-elle importante?
• Les différences ont-elles quelque chose à voir avec la distribution de la production du PRNG?

Commençons par examiner le moyen idéal pour générer un jeu de cartes aléatoire permettant de jouer au poker. Ensuite, nous verrons en quoi les autres techniques de génération de decks sont différentes et s'il est possible de tirer parti de cette différence.

Commençons par supposer que nous avons une boîte magique étiquetée TRNG. En entrée, nous lui donnons un entier n supérieur ou égal à un et en sortie, un nombre véritablement aléatoire compris entre un et n, inclus. La sortie de la boîte est totalement imprévisible (lorsqu'on lui attribue un nombre autre qu'un) et tout nombre compris entre un et n est aussi probable qu'un autre; c'est-à-dire que la distribution est uniforme . (Nous pourrions effectuer d'autres vérifications statistiques plus poussées de l'aléa statistique; j'ignore ce point car cela ne correspond pas à mon argument. TRNG est parfaitement statistiquement aléatoire par hypothèse.)

Nous commençons avec un jeu de cartes non mélangé. Nous demandons à la case un nombre compris entre un et 52 - c'est-à-dire TRNG(52),. Quel que soit le nombre de cartes rendues, nous comptons le nombre de cartes de notre deck trié et retirons cette carte. Cela devient la première carte du jeu mélangé. Ensuite, nous demandons TRNG(51)et faisons de même pour sélectionner la deuxième carte, et ainsi de suite.

Une autre façon de voir les choses est la suivante: il y en a 52! = 52 x 51 x 50 ... x 2 x 1 ponts possibles, ce qui correspond à environ 2 ²²⁶ . Nous avons choisi l'un d'entre eux au hasard.

Maintenant, nous distribuons les cartes. Quand je regarde mes cartes, je n'ai aucune idée de ce que vous avez. (Mis à part le fait évident que vous n'avez aucune des cartes que j'ai.) Ce pourrait être n'importe quelle carte, avec une probabilité égale.

Alors laissez-moi m'assurer que je l'explique clairement. Nous avons une distribution uniforme de chaque sortie individuelle de TRNG(n); chacun choisit un nombre compris entre 1 et n avec une probabilité de 1 / n. En outre, le résultat de ce processus est que nous avons choisi l'un des 52! ponts possibles avec une probabilité de 1/52 !, de sorte que la distribution sur l’ensemble des ponts possibles est également uniforme.

D'accord.

Supposons maintenant que nous ayons une boîte moins magique, étiquetée PRNG. Avant de pouvoir l' utiliser, il doit être tête de série avec un nombre non signé de 32 bits.

AUSSI: Pourquoi 32 ? Ne pourrait-il pas être associé à un nombre de 64, 256 ou 10 000 bits? Sûr. Mais (1) dans la pratique, la plupart des PRNG disponibles dans le commerce sont associées à un nombre de 32 bits et (2) si vous avez 10 000 bits aléatoires pour créer la graine, pourquoi utilisez-vous un PRNG? Vous avez déjà une source de 10000 bits de hasard!

Quoi qu'il en soit, revenons à la façon dont fonctionne le PRNG: une fois qu’il a été semé, vous pouvez l’utiliser de la même façon TRNG. C'est-à-dire que vous lui attribuez un nombre n et qu'il vous restitue un nombre compris entre 1 et n inclus. De plus, la distribution de cette production est plus ou moins uniforme . Autrement dit, lorsque nous demandons PRNGun nombre compris entre 1 et 6, nous obtenons 1, 2, 3, 4, 5 ou 6 chacun environ un sixième du temps, quelle que soit la graine.

Je tiens à souligner ce point à plusieurs reprises, car il semble que ce soit la source de confusion pour certains commentateurs. La distribution du PRNG est uniforme à au moins deux égards. Premièrement, supposons que nous choisissions une graine en particulier. Nous nous attendions à ce que la séquence PRNG(6), PRNG(6), PRNG(6)...un million de fois produise une distribution uniforme de nombres entre 1 et 6. Et deuxièmement, si nous choisissions un million de semences différentes et appelions PRNG(6) une fois pour chaque graine, nous nous attendrions à une distribution uniforme de nombres de 1 à 6. L'uniformité du GNRP au cours de l'une ou l'autre de ces opérations n'est pas pertinente pour l'attaque que je décris .

Ce processus est dit pseudo-aléatoire car le comportement de la boîte est en réalité totalement déterministe; il choisit parmi l'un des 2 ³² comportements possibles en fonction de la graine. C'est-à-dire qu'une fois qu'il est semé, il PRNG(6), PRNG(6), PRNG(6), ... produit une séquence de nombres avec une distribution uniforme, mais cette séquence est entièrement déterminée par la graine. Par exemple, pour une séquence d'appels donnée, PRNG (52), PRNG (51), etc., il n'y a que 2 ³² séquences possibles. La graine choisit essentiellement celle que nous obtenons.

Pour générer une plate-forme, le serveur génère maintenant une graine. (Comment? Nous reviendrons sur ce point.) Ensuite , ils appellent PRNG(52), PRNG(51)et ainsi de suite pour générer la plate - forme, semblable auparavant.

Ce système est sujet à l'attaque que j'ai décrite. Pour attaquer le serveur, nous devons d'abord, à l'avance, ensemencer notre propre copie de la boîte avec 0, puis demander PRNG(52)et écrire cette information. Ensuite, nous re-semons avec 1, demandons PRNG(52)et notons-le jusqu’à 2 ³² -1.

Maintenant, le serveur de poker qui utilise PRNG pour générer des decks doit générer une graine en quelque sorte. Peu importe comment ils le font. Ils pourraient appeler TRNG(2^32)pour obtenir une graine vraiment aléatoire. Ils pourraient aussi prendre l’heure actuelle comme une graine, ce qui n’est guère aléatoire. Je sais quelle heure il est autant que toi. Le point de mon attaque est que cela n’a aucune importance, car j’ai ma base de données . Quand je vois ma première carte, je peux éliminer 98% des graines possibles. Quand je vois ma deuxième carte, je peux éliminer 98% de plus, et ainsi de suite, jusqu'à ce que je puisse finalement en arriver à une poignée de semences possibles et savoir avec une grande probabilité ce qui est dans votre main.

Maintenant, encore une fois, je tiens à souligner que l’hypothèse retenue ici est que si nous appelions PRNG(6)un million de fois, nous aurions chaque numéro environ un sixième du temps . Cette distribution est (plus ou moins) uniforme , et si l'uniformité de cette distribution est tout ce qui vous intéresse , c'est bien. La question était la suivante: y a-t-il autre chose que la distribution de ce PRNG(6)qui nous intéresse? et la réponse est oui . Nous nous soucions également de l' imprévisibilité .

Une autre façon d’envisager le problème est que, même si la distribution d’un million d’appels PRNG(6)pourrait bien se dérouler, car le PRNG choisit parmi seulement 2 ³² comportements possibles, il ne peut pas générer toutes les réponses possibles. Il ne peut générer que 2 ³² des 2 ²²⁶ ponts possibles; une infime fraction. La distribution sur l’ensemble des decks est donc très mauvaise. Mais là encore, l’attaque fondamentale consiste à pouvoir prédire avec succès le comportement passé et futur d’ PRNGun petit échantillon de ses résultats.

Permettez-moi de dire ceci une troisième ou quatre fois pour m'assurer que cela est bien intégré. Premièrement, la distribution du processus qui produit la graine aléatoire 32 bits. Cela peut être parfaitement aléatoire, imprévisible et uniforme et l’attaque fonctionnera toujours . Deuxièmement, la distribution d'un million d'appels à PRNG(6). Cela peut être parfaitement uniforme et l’attaque fonctionnera toujours. Troisièmement, la distribution des paquets choisie par le processus pseudo-aléatoire que j'ai décrit. Cette distribution est extrêmement pauvre; seule une infime fraction des ponts IRL possibles peut éventuellement être choisie. L'attaque dépend de la prévisibilité du comportement du PRNG sur la base d'une connaissance partielle de ses résultats .

EN DEHORS: Cette attaque nécessite que l'attaquant sache ou soit capable de deviner quel est l'algorithme exact utilisé par le PRNG. Que ce soit réaliste ou non est une question ouverte. Cependant, lors de la conception d'un système de sécurité, vous devez le concevoir pour qu'il soit sécurisé contre les attaques, même si l'attaquant connaît tous les algorithmes du programme . En d'autres termes: la partie d'un système de sécurité qui doit rester secrète pour que le système soit sécurisé s'appelle la "clé". Si votre système dépend pour sa sécurité des algorithmes que vous utilisez étant un secret, votre clé contient ces algorithmes . C'est une position extrêmement faible pour être dans!

Passer à autre chose

Supposons maintenant que nous ayons une troisième boîte magique étiquetée CPRNG. C'est une version de crypto-force de PRNG. Il faut une graine 256 bits plutôt qu'une graine 32 bits. Il partage avec PRNGla propriété que la graine choisit parmi l’un des 2 ²⁵⁶ comportements possibles. Et, à l'instar de nos autres machines, il a la propriété de faire un grand nombre d'appels pour CPRNG(n)produire une distribution uniforme des résultats entre 1 et n: chacune se produit 1 / n des fois. Pouvons-nous lancer notre attaque contre elle?

Notre attaque initiale nécessite que nous stockions 2 ³² cartographies à partir de graines PRNG(52). Mais 2 ²⁵⁶ est un nombre beaucoup plus grand; il est totalement impossible de l'exécuter CPRNG(52)autant de fois et de stocker les résultats.

Mais supposons qu'il y ait un autre moyen de prendre la valeur CPRNG(52)et d'en déduire un fait à propos de la graine? Nous avons été assez stupides jusqu'à présent, nous avons simplement forcé toutes les combinaisons possibles. Pouvons-nous regarder à l'intérieur de la boîte magique, comprendre comment cela fonctionne et déduire des faits sur la graine en fonction de la sortie?

Non . Les détails sont trop compliquées à expliquer, mais CPRNGs sont intelligemment conçus de sorte qu'il est impossible d' en déduire tout fait utile sur la graine de la première sortie CPRNG(52)ou de tout sous - ensemble de la production, peu importe la taille .

OK, supposons maintenant que le serveur utilise CPRNGpour générer des decks. Il faut une graine de 256 bits. Comment choisit-il cette graine? S'il choisit une valeur qu'un attaquant peut prédire , l'attaque redevient soudainement viable . Si nous pouvons déterminer que sur les 2 ²⁵⁶ semences possibles, seuls quatre milliards d'entre elles sont susceptibles d'être choisies par le serveur, nous sommes de retour dans les affaires . Nous pouvons à nouveau monter cette attaque, en ne prêtant attention qu'au petit nombre de graines pouvant éventuellement être générées.

Le serveur doit donc faire en sorte que le nombre de 256 bits soit uniformément distribué - en d’autres termes, chaque graine possible est choisie avec une probabilité de 1/2 ²⁵⁶ . Fondamentalement, le serveur devrait appeler TRNG(2^256)-1pour générer le germe CPRNG.

Que se passe-t-il si je peux pirater le serveur et y jeter un œil pour voir quelle graine a été choisie? Dans ce cas, l'attaquant connaît tout le passé et l'avenir du CPRNG . L'auteur du serveur doit se prémunir contre cette attaque! (Bien sûr, si je réussis à monter cette attaque, je pourrai probablement aussi transférer l'argent directement sur mon compte bancaire, alors ce n'est peut-être pas si intéressant. L'important, c'est que la graine doit être un secret difficile à deviner, et nombre vraiment aléatoire 256 bits est sacrément difficile à deviner.)

Revenons à mon point précédent sur la défense en profondeur: la valeur de départ de 256 bits est la clé de ce système de sécurité. L'idée d'un CPRNG est que le système est sécurisé tant que la clé est sécurisée . Même si tous les autres faits concernant l'algorithme sont connus, tant que vous pouvez garder la clé secrète, les cartes de l'adversaire sont imprévisibles.

OK, la graine doit donc être à la fois secrète et uniformément distribuée, sinon, nous pouvons organiser une attaque. Nous supposons que la distribution des produits CPRNG(n)est uniforme. Qu'en est-il de la distribution sur l'ensemble des decks possibles?

Vous pourriez dire: le CPRNG produit 2 ²⁵⁶ séquences possibles, mais il n’ya que 2 ²²⁶ ponts possibles. Par conséquent, il y a plus de séquences possibles que de decks, donc tout va bien; toutes les cartes IRL possibles sont maintenant (avec une probabilité élevée) possibles dans ce système. Et c'est un bon argument, sauf que ...

2 ²²⁶ n’est qu’une approximation de 52 !. Divisez-le. 2 ^256/52 ! ne peut pas être un nombre entier parce que, d'une part, 52! est divisible par 3 mais aucune puissance de deux n'est! Comme il ne s’agit pas d’un nombre entier, nous sommes dans une situation où tous les ponts sont possibles , mais certains ponts sont plus susceptibles que d’autres .

Si ce n'est pas clair, considérons la situation avec des nombres plus petits. Supposons que nous ayons trois cartes, A, B et C. Supposons que nous utilisions un PRNG avec une graine à 8 bits, il y a donc 256 graines possibles. Il y a 256 sorties possibles de PRNG(3)selon la graine; il est impossible qu'un tiers d'entre eux soit A, un tiers d'entre eux B et un tiers d'entre eux C, car 256 n'est pas également divisible par 3. Il doit y avoir un léger parti pris pour l'un d'eux.

De même, 52 ne se divise pas également en 2 ²⁵⁶ , il doit donc y avoir un biais envers certaines cartes en tant que première carte choisie et un biais par rapport aux autres.

Dans notre système original avec une graine 32 bits, il y avait un biais énorme et la grande majorité des ponts possibles n’ont jamais été produits. Dans ce système, tous les ponts peuvent être produits, mais la distribution des ponts est toujours défectueuse . Certains ponts sont très légèrement plus susceptibles que d'autres.

Maintenant, la question est: avons-nous une attaque basée sur cette faille? et la réponse est en pratique, probablement pas . CPRNGs sont conçus de telle sorte que si la graine est vraiment aléatoire alors il est infaisable de faire la différence entre CPRNGet TRNG.

OK, alors résumons.

Comment les nombres pseudo-aléatoires et les nombres vraiment aléatoires diffèrent-ils?

Ils diffèrent par le niveau de prévisibilité qu'ils présentent.

• Les nombres vraiment aléatoires ne sont pas prévisibles.
• Tous les nombres pseudo-aléatoires sont prévisibles si la graine peut être déterminée ou devinée.

Pourquoi la différence est-elle importante?

Parce qu'il existe des applications où la sécurité du système repose sur l' imprévisibilité .

• Si un TRNG est utilisé pour choisir chaque carte, le système est inattaquable.
• Si un CPRNG est utilisé pour choisir chaque carte, le système est sécurisé si la valeur de départ est imprévisible et inconnue.
• Si un PRNG ordinaire avec un petit espace d’origine est utilisé, le système n’est pas sécurisé, que l’initialisation soit imprévisible ou inconnue; un espace de germination assez petit est susceptible d'attaques par force brute du type que j'ai décrit.

La différence a-t-elle quelque chose à voir avec la distribution de la production du PRNG?

L'uniformité de la distribution ou de l' absence de celle - ci pour des appels individuels à RNG(n)ne concerne pas les attaques que je viens de décrire.

Comme nous l’avons vu, a PRNGet CPRNGproduit de mauvaises distributions de la probabilité de choisir n’importe quel deck de tous les decks possibles. Le PRNGest considérablement pire, mais les deux ont des problèmes.

Encore une question:

Si TRNG est tellement meilleur que CPRNG, qui à son tour est tellement meilleur que PRNG, pourquoi quelqu'un utilise-t-il CPRNG ou PRNG?

Deux raisons.

Premièrement: les dépenses. TRNG est cher . Générer des nombres vraiment aléatoires est difficile. Les CPRNG donnent de bons résultats pour un nombre arbitraire d'appels avec un seul appel à TRNG pour la graine d'origine. L'inconvénient est bien sûr que vous devez garder cette graine secrète .

Deuxièmement: nous voulons parfois de la prévisibilité et la distribution nous importe simplement . Si vous générez des données "aléatoires" en tant qu'entrées de programme pour une suite de tests et que cela indique un bogue, il serait bien que l'exécution de la suite de tests produise à nouveau le bogue!

J'espère que c'est maintenant beaucoup plus clair.

Enfin, si vous appréciez cela, vous pourrez approfondir vos connaissances sur le hasard et les permutations:

• Supposons que je dispose de données aléatoires uniformément réparties. Comment puis-je le transformer en une distribution non uniforme donnée?
• Pourquoi certains GUID sont générés de manière aléatoire? Est-ce que tous leurs bits sont aléatoires? (Non.) Puis-je compter sur un GUID comme source de véritable caractère aléatoire? (Non!)
• Comment puis-je générer de grands nombres aléatoires en utilisant la notation factoradique?
  • Comment puis-je transformer cela en une permutation aléatoire?
• Comment pouvons-nous monter l'attaque décrite ici contre la permutation aléatoire?
• Combien de biais est introduit en utilisant la technique du reste à mettre en œuvre RNG(n)?

Comme le dit Eric Lippert, il ne s'agit pas uniquement de la distribution. Il existe d'autres moyens de mesurer le caractère aléatoire.

L'un des premiers générateurs de nombres aléatoires a une séquence dans le bit le moins significatif - il alterne les 0 et les 1. Par conséquent, le LSB était prévisible à 100%. Mais vous devez vous soucier de plus que cela. Chaque bit doit être imprévisible.

Voici un bon moyen de réfléchir au problème. Disons que vous générez 64 bits de hasard. Pour chaque résultat, prenez les 32 premiers bits (A) et les 32 derniers bits (B), et créez un index dans un tableau x [A, B]. Effectuez maintenant le test un million de fois et, pour chaque résultat, incrémentez le tableau à ce nombre, c’est-à-dire X [A, B] ++;

Dessinez maintenant un diagramme 2D, où plus le nombre est grand, plus le pixel est lumineux à cet endroit.

Si c'est vraiment aléatoire, la couleur devrait être un gris uniforme. Mais vous pourriez avoir des modèles. Prenez par exemple ce diagramme du "caractère aléatoire" dans le numéro de séquence TCP du système Windows NT:

ou même celui-ci sous Windows 98:

Et voici le caractère aléatoire de la mise en œuvre du routeur Cisco (IOS).

Ces diagrammes sont une gracieuseté du papier de Michał Zalewski . Dans ce cas particulier, si on peut prédire ce que sera le numéro de séquence TCP d'un système, on pourra emprunter l'identité de ce système lors de l'établissement d'une connexion à un autre système - ce qui permettrait le détournement de connexions, l'interception de communications, etc. ne peut pas prédire le prochain nombre 100% du temps, si nous pouvons provoquer la création d'une nouvelle connexion sous notre contrôle , nous pouvons augmenter les chances de succès. Et lorsque des ordinateurs peuvent générer 100 000 connexions en quelques secondes, les chances d’une attaque réussie vont d’astronomiques à possibles ou même probables.

Bien que les nombres pseudo-aléatoires générés par les ordinateurs soient acceptables pour la majorité des cas d'utilisation rencontrés par les utilisateurs d'ordinateurs, il existe des scénarios qui nécessitent des nombres aléatoires complètement imprévisibles.

Dans les applications sensibles à la sécurité telles que le cryptage, un générateur de nombres pseudo-aléatoires (PRNG) peut produire des valeurs qui, bien qu'apparemment aléatoires, sont en fait prévisibles par un attaquant. Une personne qui tente de déchiffrer un système de chiffrement peut être en mesure de deviner les clés de chiffrement si un PRNG a été utilisé et que l'attaquant dispose d'informations sur l'état du PRNG. Par conséquent, pour de telles applications, un générateur de nombre aléatoire qui produit des valeurs qui sont vraiment impossibles à deviner est nécessaire. Notez que certains PRNG sont conçus pour être sécurisés de manière cryptographique et sont utilisables pour de telles applications sensibles à la sécurité.

Plus d'informations sur les attaques RNG peuvent être trouvées dans cet article Wikipedia .

Je l'ai essayé en Python: voici le résultat de 60 millions de rouleaux. La variation la plus élevée est de 0,15. N'est-ce pas aussi aléatoire que cela va arriver?

En fait, c'est tellement "bon" que c'est mauvais ... Toutes les réponses existantes se concentrent sur la prévisibilité étant donné une petite séquence de valeurs initiales. Je veux soulever un autre problème:

    votre distribution a un écart-type beaucoup plus petit que les rouleaux aléatoires

Le véritable caractère aléatoire n’est tout simplement pas aussi proche de la moyenne «quasiment exactement 1 sur le nombre de nombres qu’il peut choisir» que vous utilisez comme indication de la qualité.

Si vous regardez cette question de Stack Exchange sur les distributions de probabilité pour plusieurs lancers de dés , vous verrez une formule pour l'écart type de N lancers de dés (en supposant des résultats véritablement aléatoires):

 sqrt(N * 35.0 / 12.0).

En utilisant cette formule, l’ écart type pour:

• 1 million de rouleaux est 1708
• 60 millions de rouleaux, c'est 13229

Si on regarde vos résultats:

• 1 million de rouleaux: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) est égal à 804
• 60 millions de rouleaux: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) est égal à 3827

Vous ne pouvez pas vous attendre à ce que l’écart type d’un échantillon fini corresponde exactement à la formule, mais il devrait être très proche. Pourtant, avec un million de lancers, vous avez moins de la moitié de la valeur normale, et par 60 millions, vous avez moins d'un tiers - la situation empire et ce n'est pas un hasard ...

Les pseudo-RNG ont tendance à se déplacer dans une séquence de nombres distincts, en commençant par la graine et en ne revenant pas sur le numéro d'origine pour une période spécifique. Par exemple, les mises en œuvre de l'ancienne rand()fonction de bibliothèque C ont généralement une période de 2 ^ 32, et elles visitent chaque numéro entre 0 et 2 ^ 32-1 exactement une fois avant de répéter la graine. Donc, si vous simulez 2 ^ 32 dés lance le pré-module (%) les résultats incluraient chaque nombre de 0 à 2 ^ 32, les comptes pour chaque résultat de 1 à 6 seraient 715827883 ou 715827882 (2 ^ 32 n’est pas un multiple de 6), et l’écart-type n’est donc que trivialement supérieur à 0. Utiliser Dans la formule ci-dessus, l'écart-type correct pour 2 ^ 32 rouleaux est 111924. Quoi qu'il en soit, à mesure que votre nombre de rouleaux pseudo-aléatoires augmente, vous convergez vers un écart-type égal à 0. On peut s’attendre à ce que le problème soit important lorsque le nombre de rôles est une fraction importante de la période, mais certains pseudo-RNG peuvent présenter des problèmes plus graves que d’autres, voire des problèmes, même avec un nombre inférieur d’échantillons.

Ainsi, même si vous ne vous souciez pas des vulnérabilités cryptographiques, dans certaines applications, vous pouvez vous préoccuper des distributions qui n'ont pas trop, artificiellement, même des résultats. Certains types de simulation tentent tout particulièrement de déterminer les conséquences des résultats inégaux qui se produisent naturellement avec de grands échantillons de résultats aléatoires individuels, mais ils sont sous-représentés dans certains résultats de pRNG. Si vous essayez de simuler la réaction d'une énorme population à un événement, ce problème pourrait modifier radicalement vos résultats et aboutir à des conclusions extrêmement erronées.

Pour donner un exemple concret, disons qu'un mathématicien dit à un programmeur de machine à poker qu'après 60 millions de rouleaux simulés - utilisés pour scintiller des centaines de petites "lumières" autour de l'écran, s'il y a eu 10 013 229 ou plus, ce que le mathématicien s'attend à être 1 stddev loin de la moyenne, il devrait y avoir un petit paiement. Selon la règle 68–95–99.7 (Wikipedia), cela devrait se produire environ 16% du temps (environ 68% se situent dans un écart-type / seule la moitié en dehors est au-dessus). Avec votre générateur de nombres aléatoires, cela représente environ 3,5 écarts types au-dessus de la moyenne: moins de 0,025% de probabilité - pratiquement aucun client ne bénéficie de cet avantage. Voir le tableau Déviations supérieures sur la page que nous venons de mentionner, en particulier:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

Je viens d'écrire ce générateur de nombres aléatoires pour générer des jets de dés

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

Vous l'utilisez comme ça

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

etc etc. Seriez-vous heureux d'utiliser ce générateur pour un programme qui exécute un jeu de dés? N'oubliez pas que sa distribution correspond exactement à ce que vous attendez d'un générateur "vraiment aléatoire"!

Les générateurs de nombres pseudo-aléatoires font essentiellement la même chose: ils génèrent des nombres prévisibles avec la distribution correcte. Ils sont mauvais pour la même raison que le générateur de nombres aléatoires simpliste ci-dessus est mauvais - ils ne conviennent pas aux situations dans lesquelles vous avez besoin d'une réelle imprévisibilité, pas seulement de la distribution correcte.

La génération de nombres aléatoires que votre ordinateur peut effectuer convient à la plupart des besoins, et il est peu probable que vous rencontriez un moment où vous avez besoin d'un nombre réellement aléatoire.

La véritable génération de nombres aléatoires a cependant ses objectifs. En sécurité informatique, jeu, échantillonnage statistique volumineux, etc.

Si vous êtes intéressé par les applications de nombres aléatoires, consultez l'article de Wikipedia .

Les nombres aléatoires générés par des fonctions typiques dans la plupart des langages de programmation ne sont pas purement des nombres aléatoires. Ce sont des nombres pseudo aléatoires. Puisqu'ils ne sont pas des nombres purement aléatoires, ils peuvent être devinés avec suffisamment d'informations sur les nombres précédemment générés. Ce sera donc un désastre pour la sécurité en cryptographie .

Par exemple, la fonction de générateur de nombre aléatoire suivante utilisée dans glibcne génère pas un nombre purement aléatoire. Le nombre pseudo aléatoire généré par ceci peut être deviné. C'est une gaffe pour les problèmes de sécurité. Il y a une histoire de cela en train de devenir désastreux. Cela ne devrait pas être utilisé en cryptographie.

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

Ce type de générateur de nombres pseudo-aléatoires ne devrait jamais être utilisé dans des endroits sensibles à la sécurité, même s'il est statistiquement significatif.

L’une des attaques les plus connues sur les clés pseudo aléatoires est l’attaque sur le WEP 802.11b . Le WEP a une clé à long terme de 104 bits, concaténée avec un IV (compteur) de 24 bits pour créer une clé de 128 bits, qui est à son tour appliquée à l' algorithme RC4 pour générer une clé pseudo aléatoire.

( RC4( IV + Key ) ) XOR (message)

Les clés étaient étroitement liées les unes aux autres. Ici, seule la IV augmentée de 1 à chaque étape et toutes les autres sont restées les mêmes. Comme ce n'était pas purement aléatoire, c'était désastreux et facile à décomposer. La clé pourrait être récupérée en analysant environ 40000 images, soit quelques minutes. Si le WEP utilisait une IV purement aléatoire à 24 bits, il pourrait être sécurisé jusqu'à environ 2 ^ 24 (près de 16,8 millions) de trames.

Il faut donc utiliser le générateur de nombres aléatoires purs dans les questions sensibles de sécurité, lorsque cela est possible.

La différence est que les nombres générés pseudo-aléatoires sont prévisibles (se répètent) après un certain temps où les vrais nombres aléatoires ne le sont pas. La longueur nécessaire pour répéter dépend de la longueur de la graine utilisée pour sa génération.

Voici une jolie vidéo sur ce sujet: http://www.youtube.com/watch?v=itaMNuWLzJo

Supposons qu'un nombre pseudo aléatoire puisse être deviné par quiconque avant qu'il ne soit généré.

Pour les applications triviales, un pseudo-hasard convient, car avec votre exemple, vous obtiendrez approximativement le pourcentage correct (environ 1/6 du total des résultats) avec une légère variation (que vous verriez si vous lancez un dé 600k fois);

Cependant, lorsqu'il s'agit de choses comme la sécurité informatique; Le véritable caractère aléatoire est requis.

Par exemple, l'algorithme RSA commence lorsque l'ordinateur choisit deux nombres aléatoires (P et Q), puis effectue plusieurs étapes pour générer ces nombres spéciaux, appelés clés publique et clé privée. (L'important dans une clé privée est qu'il est privé, et personne d'autre ne le sait!)

Si un attaquant peut savoir quels sont les deux nombres «aléatoires» choisis par votre ordinateur, il peut suivre la même procédure pour calculer votre clé privée (celle que personne d'autre n'est censée connaître!)

Avec votre clé privée, un attaquant peut: a) Parler à votre banque en se faisant passer pour vous, b) Écouter votre trafic Internet "sécurisé" et pouvoir le décoder, c) Se faire passer pour quelqu'un d'autre sur Internet.

C'est là que le véritable caractère aléatoire (c'est-à-dire ne pas pouvoir être deviné / calculé) est requis.

Le premier nombre aléatoire que j'ai jamais utilisé possédait l'excellente propriété que de deux nombres aléatoires consécutifs, le second était plus grand avec une probabilité de 0,6. Pas 0.5. Et le troisième était plus grand que le second avec une probabilité de 0,6, et ainsi de suite. Vous pouvez imaginer à quel point cela simule une simulation.

Certaines personnes ne me croiraient pas que c'était même possible avec les nombres aléatoires distribués de manière égale, mais c'est évidemment possible si vous regardez la séquence (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ...) où le deuxième des deux nombres est plus grand avec une probabilité de 0,6.

D'autre part, pour les simulations, il peut être important de pouvoir reproduire des nombres aléatoires. Supposons que vous effectuez une simulation de trafic et que vous souhaitiez savoir comment certaines actions que vous pourriez entreprendre pourraient améliorer le trafic. Dans ce cas, vous voulez pouvoir recréer exactement les mêmes données de trafic (comme des personnes essayant d'entrer dans une ville) avec différentes actions pour améliorer le trafic.

La réponse courte est que les gens ont généralement besoin du "vrai hasard" pour une mauvaise raison, à savoir qu'ils ne comprennent pas la cryptographie.

Les primitives cryptographiques telles que les chiffrements de flux et les CSPRNG sont utilisées pour produire d’énormes flux de bits imprévisibles une fois qu’ils ont été alimentés par quelques bits imprévisibles.

Le lecteur attentif aura maintenant compris qu'il existe un problème d'amorçage: nous devons rassembler quelques bits d'entropie pour tout lancer. Ensuite, ils peuvent alimenter un CSPRNG qui, à son tour, fournira avec bonheur tous les bits imprévisibles dont nous avons besoin. Ainsi, un RNG matériel est requis pour initialiser un CSPRNG . C'est le seul cas où l'entropie est requise en vérité.

(Je pense que cela aurait dû être posté dans Sécurité ou Cryptographie.)

Éditer: Au final, il faut sélectionner un générateur de nombres aléatoires assez bon pour la tâche envisagée et, en ce qui concerne la génération de nombres aléatoires, le matériel ne signifie pas nécessairement bon. Tout comme les mauvais PRNG, les sources aléatoires matérielles ont généralement des biais.

Edit: Certaines personnes ici supposent un modèle de menace dans lequel un attaquant pourrait lire l’état interne d’un CSPRNG et à partir de là, conclure que les CSPRNG ne constituent pas une solution sûre. Ceci est un exemple de mauvaise modélisation de thread. Si un attaquant possède votre système, le jeu est terminé, simplement. Que vous utilisiez un TRNG ou un CSPRNG à ce stade ne fait aucune différence.

Edit: Donc, pour résumer tout cela… Entropie est nécessaire pour générer un CSPRNG. Une fois que cela est fait, un CSPRNG fournira tous les bits imprévisibles dont nous avons besoin pour les applications de sécurité beaucoup plus rapidement que nous ne pouvons (généralement) collecter l'entropie. Si l'imprévisibilité n'est pas nécessaire, par exemple pour la simulation, un Twister Mersenne fournira des nombres avec de bonnes propriétés statistiques à un taux beaucoup plus élevé.

Edit: Toute personne désireuse de comprendre le problème de la génération sécurisée de nombres aléatoires devrait lire ceci: http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf

Tous les PRNG ne conviennent pas à toutes les utilisations. Par exemple, Java.util.SecureRandom utilise le hachage SHA1, dont la taille de sortie est de 160 bits. Cela signifie que 2 ¹⁶⁰ flux possibles de nombres aléatoires peuvent en découler. Aussi simple que cela. Vous ne pouvez pas obtenir plus de 2 ¹⁶⁰ valeurs de l'état interne. Ainsi, vous ne pouvez pas obtenir plus de 2 ¹⁶⁰ flux uniques de nombres aléatoires à partir d’une seule graine, quelle que soit l’origine de votre graine. Windows CryptGenRandom est censé utiliser un état de 40 octets, il a 2 ³²⁰ flux possibles de nombres aléatoires.

Le nombre de façons de mélanger un paquet standard de 52 cartes est de 52 !, ce qui correspond à environ 2 ²²⁶ . Ainsi, quel que soit l'ensemencement, vous ne pouvez pas utiliser Java.util.SecureRandom pour mélanger un jeu de cartes. Il y a environ 2 ⁶⁶ mélanges possibles qu'il ne peut pas produire. Bien sûr, nous ne savons pas lesquels ils sont ...

Donc, si j’avais une source de 256 bits de véritable caractère aléatoire (par exemple, d’une carte Quantis RNG), je pourrais ensemencer un PRNG comme CryptGenRandom () avec cette graine, puis utiliser le PRNG pour mélanger un paquet de cartes. Si je réensemence avec un véritable hasard à chaque lecture aléatoire, tout ira bien: imprévisible et statistique. Si je faisais la même chose avec Java.util.SecureRandom, il y aurait des remaniements qui ne pourraient probablement pas être produits car il ne peut pas être semé avec 256 bits d'entropie et son état interne ne peut pas représenter tous les remaniements possibles.

Notez que les résultats de java.util.SecureRandom seraient à la fois imprévisibles et statistiquement aléatoires. Aucun test statistique ne permettrait jamais d'identifier un problème! Mais la sortie du RNG n’est pas assez grande pour couvrir l’ensemble des sorties possibles pour simuler un jeu de cartes.

Et rappelez-vous, si vous ajoutez les jokers, c'est 54! que vous devez couvrir, ce qui nécessite environ 2 ²³⁸ possibilités.

Les nombres pseudo-aléatoires sont générés à l'aide d'une fonction mathématique et d'une valeur initiale (appelée graine ), alors que les nombres aléatoires ne le sont pas. Leur prévisibilité les rend incroyablement utiles pour les répétitions de jeu, car il vous suffit de sauvegarder la graine et l'entrée du joueur - l'IA répondra exactement de la même manière "aléatoire" à chaque fois.

La différence entre "vrai" nombre aléatoire et "pseudo" nombre aléatoire est la prévisibilité. Cette réponse a déjà été fournie.

Cependant, la prévisibilité n'est pas nécessairement une mauvaise chose, comme le montrent la plupart des exemples. Voici un exemple pratique d’un des rares cas où la prévisibilité est bonne: le système de positionnement global.

Chaque satellite utilise un code PRN distinct (les codes Gold ) adapté à la corrélation automatique ou à la corrélation croisée nécessaire pour la mesure du temps de propagation du signal. Pour ces codes de Gold, la corrélation entre eux est particulièrement faible, ce qui permet une identification sans équivoque du satellite, mais permet le calcul de distance par la corrélation entre la séquence émise et le récepteur.

Pour un contrôle rapide de l’aléatoire, vous prenez des points avec des coordonnées aléatoires dans [0; 1), puis vous les placez dans un cube de dimension k. Ensuite, vous effectuez la procédure pour découper ce cube en sous-cubes - chaque volume de sous-cube (ou sous-sphère) doit être mesuré correctement par cette procédure avec des fluctuations selon le théorème bien connu.

La qualité du hasard est importante lorsque vous vous rencontrez ...

1. des fins de sécurité. Lorsque vous générez un nombre à utiliser comme paramètre pour la génération de votre clé, et que c'est bien prévisible, l'ennemi le détectera avec une probabilité de 100% et réduira le champ de recherche de manière beaucoup plus réduite.

2. à des fins scientifiques. En science, il faut non seulement avoir la moyenne moyenne en bon état, mais également éliminer les corrélations entre différents nombres aléatoires. Donc, si vous prenez (a_i - a) (a_ {i + 1} -a) et trouvez sa distribution, elle doit correspondre à des statistiques.

La corrélation de paires est appelée "aléatoire faible". Si vous voulez un caractère aléatoire réel, vous devez avoir une corrélation d’ordre élevé avec plus de 2 variances.

Aujourd'hui, seuls les générateurs de la mécanique quantique offrent un véritable caractère aléatoire.

Pourquoi le vrai hasard est-il important?

Il existe essentiellement deux raisons pour lesquelles le véritable caractère aléatoire est nécessaire:

1. Si vous utilisez le RNG pour la cryptographie (y compris des choses comme le jeu en argent réel et une loterie), alors un PRNG vous rendra le chiffrement beaucoup plus faible que son analyse mathématique (qui suppose un TRNG) vous ferait croire. Le PRNG ne sera pas réellement aléatoire, mais aura un motif - les adversaires peuvent exploiter ce motif pour déchiffrer un chiffre qui aurait dû être insaisissable.
2. Si vous utilisez le RNG pour simuler des entrées "aléatoires", par exemple pour un test de bogue ou une simulation, un PRNG affaiblit votre approche. Lorsque vous ne découvrirez aucun bug, il y aura toujours ce doute lancinant: existe-t-il un bug qui ne se remarque pas avec le modèle de mon PRNG, mais qui serait apparu si je n'avais utilisé qu'un TRNG? Les résultats de ma simulation décrivent-ils avec exactitude la réalité ou le phénomène que j'ai découvert est-il simplement un artefact du modèle du PRNG?

En dehors de ces zones, cela n'a pas vraiment d'importance. Mise en garde: Si votre PRNG est vraiment très mauvais, il se peut qu'il ne soit toujours pas adapté - vous ne voulez pas faire un jeu de Craps où les dés reviennent toujours même, vos joueurs ne l'aimeraient pas.

Comment le PRNG de Python n'est-il pas assez bon?

Il est très peu probable que vous soyez capable de détecter les pièges d'un vrai PRNG en utilisant une méthodologie aussi simple. L'analyse statistique des RNG est un domaine scientifique à part entière, et des tests très sophistiqués sont disponibles pour évaluer le "caractère aléatoire" d'un algorithme. Celles-ci sont beaucoup plus avancées que votre simple tentative.

Tous les développeurs de logiciels qui créent des bibliothèques du monde réel, tels que les développeurs Python, utilisent ces tests statistiques pour déterminer si leur implémentation PRNG est suffisante. Par conséquent, il est très peu probable que vous soyez en mesure de détecter facilement un modèle dans un PRNG du monde réel, à l'exception des cas de supervision réelle de la part du développeur. Cela ne signifie pas qu'il n'y a pas de modèle - un PRNG a un modèle par définition.

Fondamentalement, vous ne pouvez pas prouver qu'une source est aléatoire par une analyse mathématique de la sortie, vous avez par exemple besoin d'un modèle physique qui dit que la source est aléatoire (comme dans le cas de la désintégration radioactive).

Vous pouvez simplement exécuter des tests par lots pour trouver une corrélation statistique dans les données de sortie. Dans ce cas, il est prouvé que les données ne sont pas aléatoires (mais une source aléatoire peut également générer des sorties non aléatoires. Sinon, elle ne sera pas vraiment aléatoire si elle ne peut pas donner de données spécifiques. sortie). Sinon, si les tests sont réussis, vous pouvez dire que les données sont pseudo aléatoires.

Passer quelques tests aléatoires signifie seulement que vous avez un bon PRNG (générateur de nombres pseudo aléatoires), ce qui peut être utile pour les applications où la sécurité n’est pas impliquée.

Si la sécurité est en jeu (chiffrement, génération d'une clé, génération de nombres aléatoires pour le jeu, etc.), il ne suffit pas d'avoir un bon PRNG, il doit avoir des qualités supplémentaires, comme la sortie de la fonction ne pouvant pas être facilement déduite des sorties précédentes, la fonction doit avoir un coût de calcul souhaitable (suffisamment limité pour être utilisable, mais suffisamment élevée pour empêcher les tentatives de forçage brutal), le matériel qui exécute la fonction - ou le périphérique, dans le cas étrange où il s’agit d’un périphérique analogique - ne devrait pas être facilement altéré, etc.

Avoir un bon PRNG peut être utile dans les jeux pour créer de nouveaux modèles imprévisibles, et dans le cryptage - trop lourd à expliquer dans un seul post, il suffit de penser à un rôle de pouce quelle sortie de la procédure de cryptage doit être pseudo-aléatoire, ne montrant pas de modèles qui pourraient associer des données cryptées précédentes aux données cryptées suivantes, ou associer des données en texte brut à des données cryptées, ou associer deux cryptographes différents l'un à l'autre (pour que des suppositions puissent être faites sur les textes bruts) ....

Histoire courte:

Génère une graine aléatoire en utilisant la microseconde actuelle du système.

Cette astuce est assez ancienne et est toujours fonctionnelle.

En excluant le facteur brut de force, où je peux déterminer chaque combinaison en "pariant" sur tous les nombres possibles et ce n’est pas le but de cette question, en particulier lorsque la plupart des nombres aléatoires sont arrondis avant son utilisation.

Disons un exemple, je peux déterminer la graine utilisée en utilisant seulement 10 valeurs. Donc, connaissant la graine, je peux deviner la valeur suivante.

Si je voudrais utiliser la graine = 1 alors je pourrais obtenir la séquence suivante:

1, 2, 3, 4, 5, 6, 7, 8, 9 ... (et j'en déduis que la graine utilisait id 1 et la valeur suivante 10)

Mais que se passera-t-il si, si on change l’envoi toutes les "nièmes" valeurs ?. Changer le germe par les microsecondes actuelles est une astuce peu coûteuse (c’est-à-dire qu’elle ne nécessite pas beaucoup de cycles de processeur).

La séquence est donc la suivante: (graine = 1) 1, 2, 3, 4, 5 ((graine = 2), 7, 9, 11, 13 ... (15?)

Dans ce cas:

a) Je ne peux pas déduire quelle graine a été utilisée.

b) Ergo, je ne peux pas deviner la valeur suivante.

c) La seule hypothèse que je puisse faire est de déduire que la prochaine graine pourrait être un nombre majeur.

Quoi qu'il en soit, la plupart des algorithmes générateurs d'aléas modernes utilisent déjà cette astuce sous le capot.

Le fait est que nous n’avons pas besoin d’un ordinateur quantique pour créer un «vrai» nombre aléatoire, l’imprécision de notre cristal de quartz de notre ordinateur fait office de générateur aléatoire, de même que l’efficacité aléatoire de notre processeur varie également sans tenir compte que le processeur effectue généralement plusieurs tâches à la fois.