Question En quoi les nombres pseudo-aléatoires et vraiment aléatoires sont-ils différents et pourquoi sont-ils importants?


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

Pourquoi y a-t-il des sites Web dédiés au «vrai hasard»? Étant donné l’observation ci-dessus, les chances d’obtenir un numéro sont presque exactement 1 sur le nombre de chiffres qu’il peut choisir.

Je l'ai essayé Python: Voici le résultat de 60 millions de rouleaux. La variation la plus élevée est comme 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

651


origine


Jetez un oeil à l'article de Wikipedia sur nombres aléatoires générés par le matériel Voir aussi ceci - stats.stackexchange.com/questions/32794/ - steadyfish
Que voulez-vous dire par "lance des dés"? At-il un bras de robot et une caméra attachés? - starblue
alors que je suis d'accord avec l'essentiel de votre ton, nous nous en préoccupons souvent trop, mais il a été exploité dans la vraie vie: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
Voir ce article sur un jeu de poker en ligne qui manque de vrai hasard pour ce qui compte. - Varaquilex
Si vous gardez juste un compteur 0-5 et lancez un dé en conséquence, 666 fois plus de fois, vous obtiendrez également une distribution égale. - jcora


Réponses:


Jouons au poker sur ordinateur, juste vous, moi et un serveur auquel nous faisons confiance tous les deux. Le serveur utilise un générateur de nombres pseudo-aléatoires qui est initialisé avec une graine de 32 bits juste avant la lecture. Il y a donc environ quatre milliards de decks possibles.

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

Auparavant, j'ai 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 chacun d'eux dans une base de données. Supposons que ma première carte soit la reine des piques. Cela ne représente qu'une carte sur une de ces 52 cartes possibles, nous avons donc réduit les possibilités de quatre milliards à environ 80 millions.

Supposons que ma deuxième carte soit le trois de cœur. Maintenant, je lance mon RNG 80 millions de fois de plus en utilisant les 80 millions de graines qui produisent la reine des piques comme premier numéro. Cela me prend quelques secondes. J'écris tous les decks qui produisent les trois coeurs comme troisième carte - la deuxième carte de ma main. Ce n'est encore que 2% des decks, alors nous sommes maintenant à 2 millions de decks.

Supposons que la troisième carte de ma main soit le 7 des clubs. J'ai une base de données de 2 millions de graines qui distribuent mes deux cartes; Je lance mon RNG 2 millions de fois supplémentaires pour trouver les 2% de ces decks qui produisent les 7 clubs comme troisième carte, et nous ne sommes plus qu'à 40 000 decks.

Vous voyez comment ça se passe. Je lance mon RNG 40000 plus de fois pour trouver toutes les graines qui produisent ma quatrième carte, ce qui nous amène à 800 decks, puis le lance 800 fois de plus 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? La façon dont vous le décrivez, vous pensez que Distribution est important, mais la distribution n'est pas ce qui rend un processus aléatoire. Imprévisibilité est ce qui rend un processus aléatoire.

METTRE À JOUR

Sur la base des 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 se disputent contre les points que je n’ai pas exprimés, ou pire, argumentent pour les points que je fait faire sur le supposer que je ne les ai pas faites, alors je sais que je dois expliquer plus clairement et plus soigneusement.

Il semble y avoir une confusion particulière autour du mot Distribution Je veux donc appeler les usages avec précaution.

Les questions sont les suivantes:

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

Commençons par considérer le parfait manière de générer un jeu de cartes aléatoire avec lequel jouer au poker. Ensuite, nous verrons comment les autres techniques de génération de deck 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, nous obtenons un nombre vraiment aléatoire compris entre un et n, inclus. La sortie de la boîte est entièrement imprévisible (quand on lui donne un nombre autre que un) et n'importe quel nombre entre un et n est aussi probable qu'un autre; c'est à dire que le Distribution est uniforme. (Nous pouvons effectuer d’autres vérifications statistiques plus avancées du caractère aléatoire; j’ignore ce point car il n’est pas pertinent pour mon argument. TRNG est parfaitement statistiquement aléatoire par hypothèse.)

Nous commençons avec un jeu de cartes non brassé. Nous demandons la boîte pour un nombre entre un et 52 - c'est à dire, TRNG(52). Quel que soit le nombre donné, nous comptons autant de cartes de notre deck trié et retirons cette carte. Il devient la première carte du jeu mélangé. Ensuite, nous demandons TRNG(51) et faites 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 decks possibles, soit environ 2226. Nous avons choisi l'un d'entre eux au hasard.

Maintenant, nous distribuons les cartes. Quand je regarde mes cartes, j'ai aucune idée que ce soit Quelles cartes avez-vous? (Mis à part le fait évident que vous n’avez aucune des cartes que je possède). Celles-ci peuvent être des cartes, avec une probabilité égale.

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

D'accord.

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

DE CÔTÉ: Pourquoi 32? Ne pourrait-il pas être doté d'un numéro 64 ou 256 ou 10000 bits? Sûr. Mais (1) dans la pratique, la plupart des PRNG standard sont dotés d'un numéro 32 bits et (2) si vous avez 10000 bits aléatoires pour créer la graine, alors 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 la graine terminée, vous pouvez l’utiliser de la même façon que vous l’utilisez. TRNG. C'est-à-dire que vous passez un nombre n et cela vous ramène à un nombre compris entre 1 et n inclus. De plus, la distribution de cette production est plus ou moins uniforme. C'est à dire quand on demande PRNG pour un nombre entre 1 et 6, nous obtenons 1, 2, 3, 4, 5 ou 6 environ un sixième du temps, quelle que soit la graine.

Je tiens à souligner ce point à plusieurs reprises, car il semble que ce soit celui qui déroute certains commentateurs. La distribution du PRNG est uniforme de deux manières au moins. Tout d'abord, supposons que nous choisissions une graine particulière. On s'attendrait à ce que la séquence PRNG(6), PRNG(6), PRNG(6)... un million de fois produirait une distribution uniforme des nombres entre 1 et 6. Et deuxièmement, si nous choisissions un million de graines différentes et appelées PRNG(6)  une fois que pour chaque graine, on s'attendrait à une distribution uniforme des nombres de 1 à 6. L'uniformité du PRNG dans l'une ou l'autre de ces opérations n'est pas pertinente pour l'attaque que je décris.

Ce processus est dit être pseudo-aléatoire parce que le comportement de la boîte est en fait entièrement déterministe; il choisit de l'un des 232 comportements possibles basés sur la graine. C'est, une fois qu'il est ensemencé, PRNG(6), PRNG(6), PRNG(6), ...  produit un séquence des nombres avec une distribution uniforme, mais cette séquence est entièrement déterminé par la graine. Pour une séquence d'appels donnée, par exemple, PRNG (52), PRNG (51) ... et ainsi de suite, il n'y a que 232 séquences possibles. La graine choisit essentiellement celle que nous obtenons.

Pour générer un deck, le serveur génère désormais une graine. (Comment? Nous reviendrons sur ce point.) Puis ils appellent PRNG(52), PRNG(51) et ainsi de suite pour générer le deck, similaire à avant.

Ce système est sensible à l'attaque que j'ai décrite. Pour attaquer le serveur, nous avons d’abord à l’avance semé notre propre copie de la boîte avec 0 et demander PRNG(52) et écris ça. Puis on re-graine avec 1, demande PRNG(52)et notez-le jusqu'à 232-1.

Maintenant, le serveur de poker qui utilise PRNG pour générer des decks doit générer une graine. Peu importe comment ils le font. Ils pourraient appeler TRNG(2^32) pour obtenir une graine vraiment aléatoire. Ou ils pourraient prendre l'heure actuelle comme une graine, ce qui est à peine aléatoire du tout; Je sais à quelle heure c'est autant que toi. Le point de mon attaque est que ce n'est pas grave, parce que 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 en arriver à une poignée de graines possibles et savoir avec une grande probabilité ce qui est entre vos mains.

Maintenant, encore une fois, je tiens à souligner que l'hypothèse ici est que si on appelait 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 compte pour vous, C'est très bien. Le point de la question était y a-t-il des choses autres que la distribution de PRNG(6) qui nous intéresse? et la réponse est Oui. Nous nous soucions de l'imprévisibilité ainsi que.

Une autre façon d’examiner le problème est que même si la distribution d’un million PRNG(6) pourrait être bien, parce que le PRNG choisit de seulement 232 comportements possibles, il ne peut pas générer tous les ponts possibles.  Il ne peut générer que 232 du 2226 ponts possibles; une infime fraction. Donc la distribution sur l'ensemble de tous les ponts est très mauvais. Mais là encore, l’attaque fondamentale repose sur le fait que nous pouvons réussir prédire le comportement passé et futur de PRNG à partir d'un petit échantillon de sa sortie.

Permettez-moi de vous dire ceci une troisième ou quatre fois pour vous assurer que cela entre. Il y a trois distributions ici. Premièrement, la distribution du processus qui produit la graine aléatoire de 32 bits. Cela peut être parfaitement aléatoire, imprévisible et uniforme et l'attaque fonctionnera encore. 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 decks choisis par le processus pseudo-aléatoire que j'ai décrit. Cette distribution est extrêmement pauvre; seule une infime fraction des possibilités de transfert IRL peut éventuellement être choisie. L'attaque dépend de la prévisibilité du comportement du PRNG basé sur la connaissance partielle de sa sortie.

ASIDE: Cette attaque nécessite que l'attaquant sache ou devine 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 le protéger 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 de sa sécurité sur les algorithmes que vous utilisez, vous devez être un secret votre clé contient ces algorithmes. C'est un extrêmement position faible pour être dans!

Passer à autre chose

Maintenant, supposons que nous avons une troisième boîte magique étiquetée CPRNG. C'est une version cryptée de PRNG. Il faut une graine de 256 bits plutôt qu'une graine de 32 bits. Il partage avec PRNG la propriété que la graine choisit parmi 2256 comportements possibles. Et comme nos autres machines, il a la propriété qu'un grand nombre d'appels à CPRNG(n) produire une distribution uniforme des résultats entre 1 et n: chacun se produit 1 / n du temps. Pouvons-nous lancer notre attaque contre elle?

Notre attaque initiale nous oblige à stocker 232 cartographie des graines à PRNG(52). Mais 2256 est un nombre beaucoup plus grand; il est complètement impossible de courir CPRNG(52)que beaucoup de temps et stocker les résultats.

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

Non, les détails sont trop compliqués à expliquer, mais les CPRNG sont intelligemment conçus pour qu’il soit impossible de déduire tout fait utile sur la graine de la première sortie de CPRNG(52) ou de tout sous-ensemble de la sortie, peu importe la taille.

OK, supposons maintenant que le serveur utilise CPRNG pour 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 alors soudain l'attaque redevient viable. Si nous pouvons déterminer celle des 2256 semences possibles, seulement quatre milliards d’entre eux sont susceptibles d’être choisis par le serveur, nous sommes de retour dans les affaires. Nous pouvons rééditer cette attaque, en ne faisant attention qu'au petit nombre de graines pouvant être générées.

Le serveur devrait donc travailler pour s’assurer que le numéro 256 bits est uniformément distribué - c'est-à-dire que chaque graine possible est choisie avec une probabilité de 1/2256. Fondamentalement, le serveur devrait appeler TRNG(2^256)-1 pour générer la graine pour CPRNG.

Que faire si je peux pirater le serveur et le regarder pour voir quelle graine a été choisie? Dans ce cas, l’attaquant connaît le passé et l’avenir complets du CPRNG.. L'auteur du serveur doit se prémunir contre cette attaque! (Bien sûr, si je réussis à monter cette attaque, je peux probablement transférer l’argent directement sur mon compte bancaire, alors peut-être que ce n’est pas très intéressant. Le point essentiel est que la graine doit être un nombre vraiment aléatoire de 256 bits est assez difficile à deviner.)

Revenant à mon point précédent sur la défense en profondeur: la graine de 256 bits est la clé à ce système de sécurité. L'idée d'un CPRNG est que le système soit 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 le secret, les cartes de l'adversaire sont imprévisibles.

OK, donc la graine doit être à la fois secrète et uniformément distribuée car si ce n’est pas le cas, nous pouvons lancer une attaque. Nous supposons que la distribution des extrants de CPRNG(n) est uniforme. Qu'en est-il de la distribution sur l'ensemble des jeux possibles?

Vous pourriez dire: il y a 2256 séquences possibles sorties par le CPRNG, mais il n'y en a que 2226 decks possibles. Il y a donc plus de séquences possibles que de decks, donc nous sommes bien. chaque paquet IRL possible est maintenant (avec une forte probabilité) possible dans ce système. Et c'est un bon argument sauf ...

2226 est seulement un approximationde 52 !. Divisez-le. 2256/ 52! ne peut pas être un nombre entier car pour une chose, 52! est divisible par 3 mais pas de puissance de deux! Puisque ce n’est pas un nombre entier, nous avons maintenant la situation où tous les ponts sont possible, mais certains decks sont plus susceptibles que d'autres.

Si ce n'est pas clair, considérez 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 de 8 bits, il y a donc 256 graines possibles. Il y a 256 sorties possibles de PRNG(3) en fonction de la graine; il n'y a aucun moyen d'en avoir un tiers, un tiers d'entre eux étant B et un tiers d'entre eux étant C parce que 256 n'est pas divisible par 3. Il doit y avoir un léger biais envers l'un d'entre eux.

De même, 52 ne se divise pas uniformément en 2256, il doit donc y avoir une certaine partialité envers certaines cartes en tant que première carte choisie et un biais loin des autres.

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

Maintenant la question est: Avons-nous une attaque basée sur cette faille? et la réponse est dans la pratique, probablement pas. Les CPRNG sont conçus pour que si la graine est vraiment aléatoire puis il est impossible sur le plan informatique de faire la différence entre CPRNG et TRNG.

OK, alors résumons.

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

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 graine est à la fois imprévisible et inconnue.
  • Si un PRNG ordinaire avec un petit espace de semences est utilisé, le système n'est pas sécurisé, que la graine soit imprévisible ou inconnue; un espace de graine assez petit est susceptible d'attaques de force brute du type que j'ai décrit.

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

L'uniformité de la distribution ou son absence pour appels individuels à RNG(n) n'est pas pertinent pour les attaques que j'ai décrites.

Comme nous avons vu, à la fois un PRNG et CPRNG produire de faibles distibutions de la probabilité de choisir un deck individuel de tous les decks possibles. le PRNG est considérablement pire, mais les deux ont des problèmes.

Encore une question:

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

Deux raisons.

Premier: dépense. TRNG est coûteux. Générer des nombres vraiment aléatoires est difficile. Les CPRNG donnent de bons résultats pour de nombreux appels avec seulement un appel à TRNG pour la graine. L'inconvénient est bien sûr que vous devez garder cette graine un secret.

Deuxièmement: parfois nous vouloir la prévisibilité et tout ce qui nous intéresse, c’est une bonne distribution. 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 présente un bogue, alors il serait intéressant que le redémarrage de la suite de tests génère à nouveau le bogue!

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

Enfin, si cela vous a plu, vous pourrez peut-être en savoir plus sur le caractère aléatoire et les permutations:


1371



Ok, les garçons et les filles. C'est assez de commentaires pour le moment. Si vous voulez en discuter davantage, allez vous chercher un chat, kthnxbye! - Ivo Flipse♦
@Eric Mais la graine n'est pas réinitialisée avant chaque nouveau tirage, n'est-ce pas? Donc, alors que vous avez raison, il n'y a que relativement peu trajectoires nous échantillonnons, vous ne savez pas exactement dans quelle trajectoire vous vous trouvez et les trajectoires se croisent. - A.S.
Quelqu'un a fait quelque chose comme ça - EJoshuaS
Un bon (mais dense) traitement des problèmes connexes est dans le TAOCP vol 2 de Knuth, section 3.5 "Qu'est-ce qu'une séquence aléatoire?" (P. 149), en commençant par des définitions éclairantes de séquences équidistribuées Les séquences pseudo-aléatoires sont discutées en 3.5.F (p. 170). Voir aussi les critères de pseudo-aléatoire de théorie de la complexité et BSI allemand. - ShreevatsaR


Comme le dit Eric Lippert, ce n'est pas simplement la distribution. Il existe d'autres moyens de mesurer le caractère aléatoire.

Un des premiers générateurs de nombres aléatoires a une séquence du bit le moins significatif - il a alterné 0 et 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 caractère aléatoire. 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]. Maintenant, effectuez le test un million de fois, et pour chaque résultat, incrémentez le tableau à ce numéro, à savoir X [A, B] ++;

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

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

Windows NT 

ou même celui de Windows 98:

Windows 98 

Et voici le caractère aléatoire de l'implémentation du routeur Cisco (IOS). Cisco ISO

Ces diagrammes sont une gracieuseté de Le papier de Michał Zalewski. Dans ce cas particulier, si l'on peut prédire quel sera le numéro de séquence TCP d'un système, on peut usurper l'identité de ce système lors d'une connexion à un autre système - ce qui permettrait le détournement des connexions, l'interception des communications, etc. Et même si nous ne pouvons pas prédire le prochain chiffre 100% du temps, si nous pouvons créer une nouvelle connexion sous notre contrôle, nous pouvons augmenter les chances de succès. Et lorsque les ordinateurs peuvent générer 100 000 connexions en quelques secondes, les chances de réussite d'une attaque vont de l'astronomie au possible ou même à la probabilité.


155



C'est tellement brillant que ça me fait pleurer. Il devrait y avoir une application qui les crée pour chaque système d'exploitation (mobile / bureau / serveur) et plate-forme (JVM / Javascript / etc). - HDave
La fonction Windows rand () est assez bonne! Il produit un nuage qui n'a pas de motif apparent. Voir mon implémentation pour l'essayer (et d'autres algorithmes): github.com/Zalastax/visualize_random - Zalastax


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, certains scénarios nécessitent complètement nombres aléatoires imprévisibles.

Dans les applications sensibles à la sécurité, telles que le chiffrement, un générateur de nombres pseudo-aléatoires (PRNG) peut produire des valeurs qui, bien que aléatoires, sont en fait prévisibles par un attaquant. Quelqu'un essayant de pirater 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’agresseur possède des informations sur l’état du PRNG. Par conséquent, pour de telles applications, un générateur de nombres aléatoires qui produit des valeurs réellement impossibles à déterminer est nécessaire. Notez que certains PRNG sont conçus pour être cryptographiquement sécurisés et sont utilisables pour de telles applications sensibles à la sécurité.

Vous trouverez plus d'informations sur les attaques RNG dans cet article Wikipedia.


91



Les PRNG cryptographiques existent et sont largement utilisés. Ils peuvent à partir d'une graine de taille modeste générer un flux pratiquement illimité de nombres aléatoires. Il est impossible sur le plan informatique de distinguer un tel flux des vrais nombres aléatoires, de sorte qu'aucune information supplémentaire ne peut être obtenue à partir d'une partie quelconque d'un tel flux, et pour des raisons pratiques, les nombres sont aussi vrais que les vrais nombres aléatoires. - aaaaaaaaaaaa
Je pense que la façon la plus simple de l'expliquer est de programmer des algorithmes générateurs de nombres aléatoires. Cela signifie qu'il y a un ensemble d'instructions qui sont suivies. S'il y a un ensemble d'instructions, cela ne peut pas être aléatoire. - Keltari
@Keltari L'élément d'entropie vous manque ... La plupart des RNG (du moins cryptographiques) recueillent des données provenant de sources externes (par exemple, le mouvement de la souris) et les utilisent dans le cadre de la condition de départ. A à B est programmé mais l'état initial de A (devrait) être imparable. Linux /dev/random gardera une approximation de la quantité d'entropie disponible et cessera de donner des nombres si elle tombe trop bas. - Basic
Par curiosité, pourquoi les lampes à lave sont-elles considérées comme «vraiment aléatoires»? Je comprends que cela montre un comportement plutôt imprévisible, mais quelqu'un avec une compréhension assez solide de la dynamique des fluides et de la manière dont ces fluides interagissent dans l'environnement gravitationnel de la Terre peut sûrement produire des résultats "prévisibles", non? Bien sûr, les lampes à lave sont imprévisibles, mais pour moi, elles ne sont pas du tout aléatoires, mais hautement prévisibles. - theGreenCabbage
@ theGreenCabbage: Je soupçonne que les lampes à lave sont chaotiques. Avec un bon modèle informatique et suffisamment de chiffres de précision, vous pouvez (en principe) prévoir le comportement pendant un certain temps. Mais comme le système est chaotique, deux lampes à lave avec le moindre changement dans les conditions initiales divergent rapidement. (Et ce commentaire ignore les attracteurs chaotiques.) - dmm


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

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

votre Distribution a beaucoup plus petit écart-type que les rouleaux aléatoires devraient

Le vrai hasard ne vient pas tout à fait cette proche de la moyenne "presque exactement 1 sur le nombre de chiffres possibles" que vous utilisez comme indication de qualité.

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

 sqrt(N * 35.0 / 12.0).

En utilisant cette formule, le déviation standard pour:

  • 1 million de rouleaux est 1708
  • 60 millions de rouleaux est 13229

Si nous regardons vos résultats:

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

Vous ne pouvez pas vous attendre à ce que l'écart-type d'un échantillon fini corresponde exactement à la formule, mais il devrait être assez proche. Pourtant, à 1 million de jetons, vous avez moins de la moitié du bon stddev, et de 60 millions vous avez moins d’un tiers - cela s’aggrave, 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 revisitant pas le numéro d'origine pour une période donnée. Par exemple, les implémentations de l'ancienne bibliothèque C rand() fonction ont généralement une période de 2 ^ 32, et ils visitent chaque nombre 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 légèrement supérieur à 0. la formule ci-dessus, l'écart type correct pour 2 ^ 32 rouleaux est 111924. De toute façon, à mesure que votre nombre de jets pseudo-aléatoires augmente, vous convergez vers 0 écart-type. On peut s'attendre à ce que le problème soit significatif lorsque le nombre de rouleaux représente une fraction significative de la période, mais que certains pseudo-GNA peuvent présenter des problèmes plus graves - ou même des problèmes avec moins d'échantillons - que d'autres.

Donc, même si vous ne vous souciez pas des vulnérabilités cryptographiques, dans certaines applications, vous pouvez vous soucier d'avoir des distributions qui n'ont pas des résultats excessifs, même artificiels. Certains types de simulation tentent tout particulièrement d’élaborer les conséquences de la inégal les résultats se produisent naturellement avec de grands échantillons de résultats aléatoires individuels, mais ils sont sous-représentés dans les résultats de certains pRNG. Si vous essayez de simuler comment une énorme population réagit à un événement, ce problème pourrait radicalement modifier vos résultats conduisant à des conclusions extrêmement imprécises.


Pour donner un exemple concret: Disons qu'un mathématicien dit à un programmeur de machine à poker qu'après 60 millions de jets simulés, il scintillait des centaines de petites "lumières" autour de l'écran, s'il y avait eu 10 013 229 ou plus 1 stddev loin de la moyenne, il devrait y avoir un petit paiement. Par le Règle 68-95-99.7 (Wikipedia) cela devrait arriver à propos de 16% du temps (~ 68% tombent dans un écart-type / la moitié seulement à l’extérieur). Avec votre générateur de nombres aléatoires, il s’agit d’environ 3,5 écarts-types au-dessus de la moyenne: Under 0,025% chance - presque aucun client ne reçoit cet avantage. Voir le tableau des écarts supérieurs 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                |

75



Vous comparez des pommes et des oranges ici. Les deux écarts types n'ont absolument rien à voir. - Jbeuh


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 exécutant un jeu de dés? N'oubliez pas que sa distribution est 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 sont pas adaptés aux situations où vous avez besoin d'une réelle imprévisibilité, pas seulement la distribution correcte.


50



"Les générateurs de nombres pseudo-aléatoires ... génèrent des nombres prévisibles avec la distribution correcte" - Le simple fait que ce soit un PRNG ne garantit pas une distribution parfaite (en fait, ce n’est pas le cas pour les raisons exposées dans ces réponses). Bien qu'ils puissent être prévisibles avec suffisamment d'informations (l'algo utilisé, le germe de départ, les valeurs de sortie, w / e), ils ont toujours une variance. - Brian S
Outre le point, je sais, mais get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on est juste trop élégant pour ne pas mentionner :) - Janus Troelsen
@BrianS En fait, un PRNG qui aurait échoué aux tests de distribution au fil du temps serait prévisible par définition. Ainsi, sur certains gros N, si vous vous écartez un peu des N / 2 têtes dans N flips, vous pouvez commencer à miser sur des têtes et vous pouvez gagner plus que vous ne perdez. De même, si vous avez une répartition parfaite des têtes contre les queues, mais que les têtes sont toujours en paires, vous avez à nouveau une recette pour gagner. Les tests de distribution sont la façon dont vous savez qu'un PRNG est bon. - Jon Kiparsky
Tu as oublié nonlocal next :-). - Kos
Encore meilleur exemple: on pense que Pi est Ordinaire, ce qui signifie que toute séquence de chiffres d'une longueur donnée dans une base quelconque n'apparaît pas plus souvent que toute autre séquence de cette longueur dans cette base. Un algorithme qui, lorsqu'on lui demande n bits aléatoires, prend la prochaine n bits de pi et les retourne (la "graine" est le bit que vous commencez), devrait à terme produire une distribution parfaitement uniforme. Mais vous ne le voudriez toujours pas pour votre générateur - quelqu'un qui connaît le dernier groupe de bits que vous avez généré pourrait trouver la première fois que cette séquence se produit, supposez que votre graine est présente et probablement correcte. - cpast


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 vraiment aléatoire.

La véritable génération de nombres aléatoires a cependant ses objectifs. Dans la sécurité informatique, le jeu, l'échantillonnage statistique important, etc.

Si vous êtes intéressé par les applications de nombres aléatoires, consultez le Article de Wikipedia.


26



Le gros problème est lorsque vous avez besoin de nombres aléatoires qu'un attaquant ne peut pas prédire pour des raisons de sécurité. - David Schwartz
Vous êtes sûr de tomber sur un moment où vous avez besoin d'un nombre vraiment aléatoire. Il suffit d'ouvrir une page Web qui commence par https://... - Jan Hudec
@JanHudec: Eh bien, en utilisation quotidienne, vous aurez besoin de nombres aléatoires sécurisés au moment où vous ouvrez un programme, bien avant de taper dans une barre d'adresse: voir randomisation de la disposition de l'espace d'adressage. C'est pourquoi des choses comme ça arrive. - Reid
@JanHudec Je parlais spécifiquement dans le sens où vous auriez besoin d'utiliser un générateur de nombres aléatoires en ligne. Les vrais nombres aléatoires sont fréquemment utilisés, mais très peu de personnes ont besoin de les générer elles-mêmes. - Alex McKenzie
Les machines à sous utilisent également un PRNG, pas un TRNG. Le générateur fonctionne tout le temps et un nombre est prélevé à l'heure exacte où le bouton de rotation est enfoncé. La somme du PRNG et du temps d’appui véritablement aléatoire revient à un TRNG. - Roger Dahl


Les nombres aléatoires générés par les fonctions typiques dans la plupart des langages de programmation ne sont pas des nombres purement aléatoires. Ce sont des nombres pseudo-aléatoires. Comme 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. Donc ce sera un désastre pour la sécurité en cryptographie.

Pour un exemple, la fonction de générateur de nombres aléatoires suivante utilisée dans glibc ne génère pas de 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 ce désastre. 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 sur le plan de la sécurité, même s’il est statistiquement très significatif.

L'une des attaques les plus connues sur la pseudo-clé aléatoire est l'attaque sur 802.11b WEP. WEP a une clé à long terme de 104 bits, concaténée avec un IV IV (compteur) pour créer une clé de 128 bits, qui est à son tour appliquée à 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, seulement IV a augmenté de 1 à chaque étape et tous les autres sont restés les mêmes. Comme ce n'était pas purement aléatoire, il était désastreux et facilement décomposé. La clé pourrait être récupérée en analysant environ 40000 trames, ce qui représente une question de minutes. Si le WEP utilisait purement aléatoire le IV à 24 bits, alors il pourrait être sûr jusqu’à environ 2 ^ 24 (près de 16,8 millions) de trames.

Donc, si possible, il faut utiliser un générateur de nombres aléatoires purs pour les problèmes de sécurité.


26



Je blâme les choses WEP sur un protocole mal conçu en utilisant un chiffrement faible. Avec les chiffrements de flux modernes, vous pouvez utiliser un compteur comme IV. - CodesInChaos
Le principal problème avec WEP était de répéter la clé dans 2 ^ 24 (près de 16 millions) de trames. C'était encore pire avec les clés associées qui permettaient de déchiffrer le code en environ 40000 images. Le point principal ici est que la clé n'est pas aléatoire. C'est étroitement lié, donc c'est facile à casser. - Prabhu
Le pseudo-hasard est mauvais en cryptographie uniquement lors de la génération de clés cryptographiques. C'est parfaitement bien au-delà de ça. En effet, RC4 est un peu plus qu'un générateur de nombres pseudo-aléatoires doté de l'extension 128 bits de la clé XORed sur le texte en clair du message. - Matt