Frage Wie unterscheiden sich Pseudozufallszahlen und echte Zufallszahlen und warum ist das wichtig?


Ich habe das nie ganz verstanden. Sag einfach, du schreibst ein kleines Programm in irgendeiner Sprache, das würfelt (nur mit Würfel als Beispiel). Nach 600.000 Rollen wäre jede Zahl rund 100.000 mal gerollt worden, was ich erwarten würde.

Warum gibt es Websites, die sich "echter Zufälligkeit" widmen? Angesichts der obigen Beobachtung sind die Chancen, eine Zahl zu bekommen, fast genau 1, gegenüber vielen Zahlen, aus denen sie wählen können.

Ich habe es versucht Python: Hier ist das Ergebnis von 60 Millionen Rollen. Die höchste Variation ist wie 0,15. Ist das nicht so zufällig wie es wird?

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


Ursprung


Sehen Sie sich den Wikipedia-Artikel an Hardware erzeugte Zufallszahlen Sieh das auch - stats.stackexchange.com/questions/32794/ ... - steadyfish
Was meinst du mit "würfelt"? Hat es einen Roboterarm und eine Kamera? - starblue
Während ich mit dem allgemeinen Kern deines Tones übereinstimme, dass wir uns oft zu viele Gedanken darüber machen, wurde es im wirklichen Leben ausgenutzt: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
Sehen Dies Artikel über ein Online Poker Spiel fehlt wahre Zufälligkeit für warum es wichtig ist. - Varaquilex
Wenn Sie einfach einen 0-5-Zähler behalten und entsprechend 666 milliardenfach würfeln, erhalten Sie eine gleichmäßige Verteilung. - jcora


Antworten:


Lass uns etwas Computer Poker spielen, nur du, ich und ein Server, dem wir beide vertrauen. Der Server verwendet einen Pseudozufallszahlengenerator, der direkt vor dem Abspielen mit einem 32-Bit-Seed initialisiert wird. Also gibt es ungefähr vier Milliarden mögliche Decks.

Ich bekomme fünf Karten in der Hand - anscheinend spielen wir nicht Texas Hold 'Em. Angenommen, die Karten werden mir ausgeteilt, einer für dich, einer für mich, einer für dich und so weiter. Also habe ich die erste, dritte, fünfte, siebte und neunte Karte im Stapel.

Früher habe ich den Pseudozufallszahlengenerator vier Milliarden Mal ausgeführt, einmal mit jedem Seed, und die erste Karte, die für jeden generiert wurde, in eine Datenbank geschrieben. Angenommen, meine erste Karte ist die Pik-Dame. Das zeigt nur eins von 52 möglichen Decks als erste Karte, also haben wir die möglichen Decks von vier auf rund 80 Millionen reduziert.

Angenommen, meine zweite Karte ist die Drei der Herzen. Jetzt renne ich meinen RNG 80 Millionen mehr Male mit den 80 Millionen Samen, die die Pik-Dame als erste Zahl produzieren. Das dauert ein paar Sekunden. Ich schreibe alle Decks auf, die die drei Herzen als dritte Karte produzieren - die zweite Karte in meiner Hand. Das sind wieder nur etwa 2% der Decks, jetzt sind es nur noch 2 Millionen Decks.

Angenommen, die dritte Karte in meiner Hand ist die 7 der Vereine. Ich habe eine Datenbank von 2 Millionen Samen, die meine zwei Karten austeilen; Ich betreibe meinen RNG weitere 2 Millionen Mal, um die 2% der Decks zu finden, die die 7 der Schläger als dritte Karte produzieren, und wir sind nur noch 40.000 Decks.

Du siehst, wie das geht. Ich renne meinen RNG 40000 mehrmals, um alle Samen zu finden, die meine vierte Karte produzieren, und das bringt uns auf 800 Decks, und dann 800 weitere Male, um die ~ 20 Samen zu bekommen, die meine fünfte Karte produzieren, und jetzt bin ich einfach erzeuge diese zwanzig Kartendecks und ich weiß, dass du eine von zwanzig möglichen Händen hast. Außerdem habe ich eine sehr gute Vorstellung davon, was ich als nächstes zeichnen werde.

Siehst du jetzt, warum wahre Zufälligkeit wichtig ist? So wie du es beschreibst, denkst du das Verteilung ist wichtig, aber Verteilung ist nicht das, was einen Prozess zufällig macht. Unvorhersehbarkeit macht einen Prozess zufällig.

AKTUALISIEREN

Basierend auf den (jetzt wegen ihrer unkonstruktiven Natur gelöschten) Kommentaren sind mindestens 0,3% der Menschen, die das gelesen haben, meiner Meinung nach verwirrt. Wenn Leute gegen Punkte argumentieren, die ich nicht gemacht habe, oder noch schlimmer, argumentiere zum weist darauf hin, dass ich hat getan machen auf die Annahme, dass ich sie nicht gemacht habe, dann weiß ich, dass ich klarer und vorsichtiger erklären muss.

Es scheint besondere Verwirrung um das Wort zu geben Verteilung also möchte ich die Gebräuche sorgfältig aufrufen.

Die Fragen sind:

  • Wie unterscheiden sich Pseudozufallszahlen und echte Zufallszahlen?
  • Warum ist der Unterschied wichtig?
  • Haben die Unterschiede etwas mit der Verteilung des Outputs des PRNG zu tun?

Beginnen wir mit der Betrachtung der perfekt Möglichkeit, ein zufälliges Kartenspiel zu generieren, mit dem man Poker spielen kann. Dann werden wir sehen, wie andere Techniken zum Erzeugen von Decks unterschiedlich sind, und ob es möglich ist, diesen Unterschied auszunutzen.

Beginnen wir mit der Annahme, dass wir eine magische Box haben TRNG. Als Eingabe geben wir ihm eine ganze Zahl n größer oder gleich eins, und als Ausgabe gibt er uns eine wirklich zufällige Zahl zwischen eins und n inklusive. Die Ausgabe der Box ist völlig unvorhersehbar (wenn eine Zahl ungleich eins gegeben wird) und eine Zahl zwischen eins und n ist so wahrscheinlich wie eine andere; das heißt, dass die Verteilung ist Uniform. (Es gibt andere fortgeschrittene statistische Prüfungen der Zufälligkeit, die wir durchführen könnten; ich ignoriere diesen Punkt, da er für meine Argumentation nicht relevant ist. TRNG ist statistisch zufällig nach Annahme.)

Wir beginnen mit einem unzusammenhängenden Kartenspiel. Wir fragen die Box nach einer Zahl zwischen eins und 52 - also TRNG(52). Egal welche Nummer es zurück gibt, wir zählen so viele Karten aus unserem sortierten Deck und entfernen diese Karte. Es wird die erste Karte im gemischten Deck. Dann fragen wir nach TRNG(51) und dasselbe tun, um die zweite Karte auszuwählen, und so weiter.

Eine andere Betrachtungsweise ist: Es gibt 52! = 52 x 51 x 50 ... x 2 x 1 mögliche Decks, das ist ungefähr 2226. Wir haben einen von ihnen zufällig ausgewählt.

Jetzt machen wir die Karten aus. Wenn ich mir meine Karten anschaue, habe ich keine Ahnung, was auch immer Welche Karten hast du? (Abgesehen von der offensichtlichen Tatsache, dass Sie keine der Karten haben, die ich habe.) Sie könnten jede Karte sein, mit gleicher Wahrscheinlichkeit.

Lassen Sie mich also sicherstellen, dass ich das klar erkläre. Wir haben gleichmäßige Verteilung von jedem einzelnen Ausgang von TRNG(n); jeder wählt eine Zahl zwischen 1 und n mit der Wahrscheinlichkeit 1 / n aus. Das Ergebnis dieses Prozesses ist auch, dass wir einen von 52 gewählt haben! mögliche Decks mit einer Wahrscheinlichkeit von 1/52 !, also die Verteilung über die Menge der möglichen Decks ist ebenfalls Uniform.

Gut.

Nehmen wir nun an, dass wir eine weniger magische Box haben, beschriftet PRNG. Bevor Sie es verwenden können, muss es sein gesät mit einer vorzeichenlosen 32-Bit-Nummer.

BEISEITE: Warum 32? Könnte es nicht mit einer 64 oder 256 oder 10000 Bit Nummer gesetzt werden? Sicher. Aber (1) in der Praxis sind die meisten Standard-PRNGs mit einer 32-Bit-Nummer versehen, und (2) wenn Sie 10000 Bits an Zufälligkeit haben, um den Keim zu bilden, warum verwenden Sie überhaupt einen PRNG? Sie haben bereits eine Quelle von 10000 Bits der Zufälligkeit!

Wie auch immer, zurück zur Funktionsweise des PRNG: Nachdem es gesetzt wurde, kannst du es genauso verwenden wie du es benutzt TRNG. Das heißt, Sie übergeben ihm eine Zahl n und geben Ihnen eine Zahl zwischen 1 und n zurück. Außerdem, die Verteilung dieser Ausgabe ist mehr oder weniger einheitlich. Das heißt, wenn wir fragen PRNG für eine Zahl zwischen 1 und 6 erhalten wir 1, 2, 3, 4, 5 oder 6 jeweils etwa ein Sechstel der Zeit, egal was der Same ist.

Ich möchte diesen Punkt mehrmals betonen, weil er so aussieht, als würde er bestimmte Kommentatoren verwirren. Die Verteilung des PRNG ist auf mindestens zwei Arten einheitlich. Angenommen, wir wählen einen bestimmten Samen aus. Wir würden diese Sequenz erwarten PRNG(6), PRNG(6), PRNG(6)... eine Million Mal würde eine gleichmäßige Verteilung der Zahlen zwischen 1 und 6 erzeugen. Und zweitens, wenn wir eine Million verschiedene Samen auswählten und anriefen PRNG(6)  Einmal für jeden Samen würden wir wiederum eine gleichmäßige Verteilung der Zahlen von 1 bis 6 erwarten. Die Gleichförmigkeit der PRNG über beide Operationen ist für den von mir beschriebenen Angriff nicht relevant.

Dieser Prozess wird gesagt pseudozufällig weil das Verhalten der Box tatsächlich vollständig deterministisch ist; es wählt aus einem von 232 mögliches Verhalten basierend auf dem Seed. Das heißt, sobald es gesät ist, PRNG(6), PRNG(6), PRNG(6), ...  produziert a Sequenz von Zahlen mit einer gleichmäßigen Verteilung, aber diese Sequenz ist vollständig bestimmt durch den Samen. Für eine gegebene Folge von Anrufen, sagen wir, PRNG (52), PRNG (51) ... und so weiter, gibt es nur 232 mögliche Sequenzen. Der Samen wählt im Wesentlichen, welchen wir bekommen.

Um ein Deck zu generieren, generiert der Server nun einen Seed. (Wie? Wir kommen zu diesem Punkt zurück.) Dann rufen sie an PRNG(52), PRNG(51) und so weiter, um das Deck zu erzeugen, ähnlich wie zuvor.

Dieses System ist anfällig für den beschriebenen Angriff. Um den Server anzugreifen, säen wir zuerst unsere eigene Kopie der Box mit 0 und bitten darum PRNG(52) und schreibe das nieder. Dann re-säen wir mit 1, fragen nach PRNG(52)und schreibe das auf den ganzen Weg bis zu 232-1.

Jetzt muss der Poker-Server, der PRNG verwendet, um Decks zu generieren, irgendwie einen Startwert generieren. Es spielt keine Rolle, wie sie das machen. Sie könnten anrufen TRNG(2^32) um einen wirklich zufälligen Samen zu bekommen. Oder sie könnten die aktuelle Zeit als einen Samen nehmen, der überhaupt nicht zufällig ist; Ich weiß wie spät es ist, genauso wie du. Der Punkt meines Angriffs ist, dass es egal ist, weil ich meine Datenbank habe. Wenn ich meine erste Karte sehe, kann ich 98% der möglichen Samen eliminieren. Wenn ich meine zweite Karte sehe, kann ich 98% mehr eliminieren, und so weiter, bis ich schließlich zu einer Handvoll möglicher Samen komme und mit großer Wahrscheinlichkeit weiß, was in deiner Hand ist.

Nun möchte ich nochmals betonen, dass die Annahme hier ist wenn wir anriefen PRNG(6) Millionen Mal würden wir jede Zahl ungefähr ein Sechstel der Zeit bekommen. Diese Verteilung ist (mehr oder weniger) Uniform, und wenn die Einheitlichkeit dieser Verteilung alles ist, was Ihnen wichtig ist, das ist gut. Der Punkt der Frage war Gibt es andere Dinge als diese Verteilung von PRNG(6) Das ist uns wichtig? und die Antwort ist Ja. Wir kümmern uns darum Unvorhersehbarkeit auch.

Eine andere Möglichkeit, das Problem zu betrachten, ist, dass trotz der Verteilung von einer Million Anrufe an PRNG(6) könnte in Ordnung sein, weil die PRNG nur aus 2 wählt32 Mögliche Verhaltensweisen, es kann nicht jedes mögliche Deck erzeugen.  Es kann nur 2 generieren32 von der 2226 mögliche Decks; ein winziger Bruchteil. Also die Verteilung über die Menge aller Decks ist sehr schlecht. Aber auch hier basiert der fundamentale Angriff darauf, dass wir erfolgreich sind vorhersagen das vergangene und zukünftige Verhalten von PRNG von einer kleinen Probe seiner Ausgabe.

Lassen Sie mich dies ein drittes oder vier Mal sagen, um sicherzustellen, dass dies eintritt. Es gibt drei Verteilungen hier. Erstens, die Verteilung des Prozesses, der den 32-Bit-Zufallssatz erzeugt. Das kann vollkommen zufällig, unvorhersehbar und einheitlich sein Der Angriff wird noch funktionieren. Zweitens, die Verteilung von einer Million Anrufe an PRNG(6). Das kann vollkommen einheitlich sein und der Angriff wird immer noch funktionieren. Drittens, die Verteilung der Decks, die durch den pseudozufälligen Prozess, den ich beschrieben habe, ausgewählt wurden. Diese Verteilung ist extrem schlecht; nur ein winziger Bruchteil der IRL möglichen Decks kann möglicherweise gewählt werden. Der Angriff hängt von der ab Vorhersagbarkeit des Verhaltens der PRNG basierend auf Teilwissen über seine Ausgabe.

ASIDE: Dieser Angriff erfordert, dass der Angreifer weiß oder in der Lage ist zu erraten, was genau der vom PRNG verwendete Algorithmus ist. Ob das realistisch ist oder nicht, ist eine offene Frage. Jedoch, Beim Entwurf eines Sicherheitssystems müssen Sie es so konzipieren, dass es gegen Angriffe geschützt ist, auch wenn der Angreifer alle Algorithmen im Programm kennt. Anders ausgedrückt: Der Teil eines Sicherheitssystems, der geheim bleiben muss, damit das System sicher ist, wird als "Schlüssel" bezeichnet. Wenn Ihr System für seine Sicherheit auf die Algorithmen angewiesen ist, die Sie verwenden, ist es ein Geheimnis Ihr Schlüssel enthält diese Algorithmen. Das ist ein äußerst schwache Position, um darin zu sein!

Weitergehen.

Nehmen wir nun an, dass wir eine dritte magische Box haben CPRNG. Es ist eine krypto-starke Version von PRNG. Es braucht einen 256-Bit-Seed anstelle eines 32-Bit-Seeds. Es teilt mit PRNG die Eigenschaft, die der Samen aus einem von 2 wählt256 mögliche Verhaltensweisen. Und wie unsere anderen Maschinen hat es die Eigenschaft, dass eine große Anzahl von Anrufen zu CPRNG(n) erzeugen Sie eine gleichmäßige Verteilung der Ergebnisse zwischen 1 und n: jede passiert 1 / n der Zeit. Können wir unseren Angriff dagegen führen?

Unser ursprünglicher Angriff erfordert, dass wir 2 speichern32 Abbildungen von Samen zu PRNG(52). Aber 2256 ist eine viel größere Anzahl; Es ist völlig unmöglich zu laufen CPRNG(52)so viel Zeit und speichern Sie die Ergebnisse.

Aber angenommen, es gibt welche andere Weg, den Wert von zu nehmen CPRNG(52) und daraus eine Tatsache über den Samen abzuleiten? Bis jetzt waren wir ziemlich dumm, nur brutal alle möglichen Kombinationen zu erzwingen. Können wir in die Zauberkiste schauen, herausfinden, wie es funktioniert, und basierend auf der Ausgabe Fakten über den Samen ableiten?

Nein. Die Details sind zu kompliziert, um sie zu erklären, aber CPRNGs sind geschickt konstruiert, so dass es unmöglich ist, daraus abzuleiten irgendein nützliche Tatsache über den Samen von der ersten Ausgabe von CPRNG(52) oder von irgendein Teilmenge der Ausgabe, egal wie groß.

OK, nehmen wir jetzt an, der Server benutzt CPRNG Decks generieren. Es benötigt einen 256-Bit-Seed. Wie wählt es diesen Samen? Wenn es einen Wert auswählt, den ein Angreifer vorhersagen kann dann wird der Angriff plötzlich wieder lebensfähig. Wenn wir das der 2 bestimmen können256 mögliche Samen, nur vier Milliarden von ihnen werden wahrscheinlich dann vom Server gewählt werden wir sind zurück im Geschäft. Wir können diesen Angriff erneut durchführen, wobei wir nur auf die geringe Anzahl der möglichen Samen achten.

Der Server sollte daher arbeiten, um sicherzustellen, dass die 256-Bit-Nummer ist gleichmäßig verteilt Das heißt, jeder mögliche Samen wird mit einer Wahrscheinlichkeit von 1/2 gewählt256. Grundsätzlich sollte der Server anrufen TRNG(2^256)-1 um den Samen für zu generieren CPRNG.

Was ist, wenn ich den Server hacken und hineinspähen kann, um zu sehen, welcher Seed ausgewählt wurde? In diesem Fall kennt der Angreifer die gesamte Vergangenheit und Zukunft des CPRNG. Der Autor des Servers muss sich vor diesem Angriff schützen! (Natürlich, wenn ich diesen Angriff erfolgreich durchführen kann, kann ich das Geld wahrscheinlich auch direkt auf mein Bankkonto überweisen, also ist das vielleicht nicht so interessant. Punkt ist: der Samen muss ein schwer zu erratendes Geheimnis sein, und a wirklich zufällige 256-Bit-Nummer ist verdammt schwer zu erraten.)

Zurück zu meinem früheren Punkt über Defense-in-Depth: Der 256-Bit-Seed ist der Schlüssel zu diesem Sicherheitssystem. Die Idee eines CPRNG ist, dass das System sicher ist solange der Schlüssel sicher ist; selbst wenn jede andere Tatsache über den Algorithmus bekannt ist, solange der Schlüssel geheim gehalten werden kann, sind die Karten des Gegners unvorhersehbar.

OK, also sollte der Keim sowohl geheim als auch gleichmäßig verteilt sein, denn wenn nicht, können wir einen Angriff starten. Wir haben angenommen, dass die Verteilung der Ausgaben von CPRNG(n) ist einheitlich. Was ist mit der Verteilung über alle möglichen Decks?

Sie könnten sagen: Es gibt 2256 mögliche Sequenzen ausgegeben von der CPRNG, aber es gibt nur 2226 mögliche Decks. Daher gibt es mehr mögliche Sequenzen als Decks, also geht es uns gut; Jedes mögliche IRL-Deck ist jetzt (mit hoher Wahrscheinlichkeit) in diesem System möglich. Und das ist ein gutes Argument, außer ...

2226 ist nur ein Annäherungvon 52 !. Teile es aus. 2256/ 52! kann unmöglich eine ganze Zahl sein, denn zum einen, 52! ist durch 3 teilbar, aber keine Zweierpotenz! Da dies keine ganze Zahl ist, haben wir jetzt die Situation, wo alle Decks sind möglich, aber Einige Decks sind wahrscheinlicher als andere.

Wenn das nicht klar ist, bedenken Sie die Situation mit kleineren Zahlen. Nehmen wir an, wir haben drei Karten, A, B und C. Nehmen wir an, wir verwenden einen PRNG mit einem 8-Bit-Seed, also gibt es 256 mögliche Seeds. Es gibt 256 mögliche Ausgänge von PRNG(3) abhängig vom Samen; es gibt keine Möglichkeit, dass ein Drittel von ihnen A ist, ein Drittel von ihnen ist B und ein Drittel von ihnen ist C, weil 256 nicht durch 3 teilbar ist. Es muss eine kleine Tendenz zu einer von ihnen geben.

Ähnlich teilt sich 52 nicht gleichmäßig in 2 auf256, also muss es eine gewisse Voreingenommenheit gegenüber einigen Karten geben, da die erste Karte gewählt wurde und eine Neigung von anderen entfernt ist.

In unserem ursprünglichen System mit einem 32-Bit-Seed gab es eine massive Verzerrung und die allermeisten möglichen Decks wurden nie produziert. In diesem System können alle Decks produziert werden, aber Die Verteilung der Decks ist immer noch fehlerhaft. Einige Decks sind kaum wahrscheinlicher als andere.

Jetzt ist die Frage: Haben wir einen Angriff auf diesen Fehler? und die Antwort ist in der Praxis wahrscheinlich nicht. CPRNGs sind so konzipiert, dass wenn der Samen wirklich zufällig ist dann es ist rechnerisch unmöglich, den Unterschied zu unterscheiden CPRNG und TRNG.

OK, fassen wir zusammen.

Wie unterscheiden sich Pseudozufallszahlen und echte Zufallszahlen?

Sie unterscheiden sich in der Höhe der Vorhersagbarkeit, die sie aufweisen.

  • Wahre Zufallszahlen sind nicht vorhersehbar.
  • Alle Pseudozufallszahlen sind vorhersagbar, wenn der Keim bestimmt oder erraten werden kann.

Warum ist der Unterschied wichtig?

Weil es Anwendungen gibt, auf die die Sicherheit des Systems angewiesen ist Unvorhersehbarkeit.

  • Wenn ein TRNG verwendet wird, um jede Karte auszuwählen, ist das System nicht anpassbar.
  • Wenn ein CPRNG verwendet wird, um jede Karte auszuwählen, dann ist das System sicher, wenn der Startwert sowohl unvorhersehbar als auch unbekannt ist.
  • Wenn ein gewöhnlicher PRNG mit einem kleinen Keimraum verwendet wird, ist das System nicht sicher, unabhängig davon, ob der Keim unvorhersehbar oder unbekannt ist; ein klein genug Samenraum ist anfällig für Brute-Force-Angriffe der Art, die ich beschrieben habe.

Hat der Unterschied etwas mit der Verteilung des Outputs des PRNG zu tun?

Die Gleichmäßigkeit der Verteilung oder deren Fehlen für einzelne Anrufe zu RNG(n) ist nicht relevant für die Angriffe, die ich beschrieben habe.

Wie wir gesehen haben, a PRNG und CPRNG produzieren schlechte Verteilung der Wahrscheinlichkeit der Auswahl eines einzelnen Decks aller möglichen Decks. Das PRNG ist wesentlich schlechter, aber beide haben Probleme.

Noch eine Frage:

Wenn TRNG so viel besser ist als CPRNG, was wiederum viel besser ist als PRNG, warum benutzt jemand CPRNG oder PRNG?

Zwei Gründe.

Erstens: Kosten. TRNG ist teuer. Das Erzeugen von echten Zufallszahlen ist schwierig. CPRNGs liefern gute Ergebnisse für beliebig viele Anrufe mit nur ein Ruf nach TRNG für den Samen. Die Nachteil ist natürlich, dass Sie müssen diesen Samen geheim halten.

Zweitens: manchmal wir wollen Vorhersagbarkeit und alles, was uns interessiert, ist eine gute Verteilung. Wenn Sie "zufällige" Daten als Programmeingaben für eine Testsuite generieren und ein Fehler angezeigt wird, wäre es schön, wenn Sie die Testsuite erneut ausführen, um den Fehler erneut zu erzeugen.

Ich hoffe, das ist jetzt viel klarer.

Wenn Ihnen das Spaß macht, können Sie sich vielleicht noch etwas zum Thema Zufälligkeit und Permutationen durchlesen:


1371



Ok, Jungs und Mädchen. Das ist genug, um für jetzt zu kommentieren. Wenn du das weiter diskutieren willst, nimm dir einen Chatraum, kthnxbye! - Ivo Flipse♦
@Eric Aber der Seed wird nicht vor jedem neuen Deck zurück gesetzt, oder? So, während Sie richtig sind, gibt es nur relativ wenige Trajektorien Wir probieren aus, Sie wissen nicht genau, wo in der Trajektorie Sie sich gerade befinden und Trajektorien kreuzen sich. - A.S.
Jemand hat tatsächlich so etwas gemacht - EJoshuaS
Eine gute (aber dichte) Behandlung verwandter Themen findet sich in Knuths TAOCP, Band 2, Abschnitt 3.5 "Was ist eine zufällige Sequenz?" (S. 149), beginnend mit aufschlussreichen Definitionen äquidistributierter, k-verteilter und ∞-verteilter Sequenzen. Pseudozufallssequenzen werden in 3.5.F (S. 170) diskutiert. Siehe auch Kriterien der Pseudozufallszahl aus Komplexitätstheorie und Deutsches BSI. - ShreevatsaR


Wie Eric Lippert sagt, ist es nicht nur Vertrieb. Es gibt andere Möglichkeiten, die Zufälligkeit zu messen.

Einer der frühen Zufallszahlengeneratoren hat eine Sequenz im niederwertigsten Bit - abwechselnd 0 und 1. Daher war das LSB zu 100% vorhersagbar. Aber Sie müssen sich um mehr als das kümmern. Jedes Bit muss unvorhersehbar sein.

Hier ist eine gute Möglichkeit, über das Problem nachzudenken. Nehmen wir an, Sie erzeugen 64 Bits an Zufälligkeit. Nehmen Sie für jedes Ergebnis die ersten 32 Bits (A) und die letzten 32 Bits (B) und machen Sie einen Index in ein Array x [A, B]. Führen Sie den Test nun millionenmal durch, und erhöhen Sie für jedes Ergebnis das Array um diese Zahl, d. H. X [A, B] ++;

Zeichnen Sie nun ein 2D-Diagramm. Je größer die Zahl, desto heller ist das Pixel an dieser Stelle.

Wenn es wirklich zufällig ist, sollte die Farbe ein einheitliches Grau sein. Aber Sie könnten Muster bekommen. Nehmen Sie zum Beispiel dieses Diagramm der "Zufälligkeit" in der TCP-Sequenznummer des Windows NT-Systems:

Windows NT 

oder auch dieses von Windows 98:

Windows 98 

Und hier ist die Zufälligkeit der Cisco Router (IOS) Implementierung. Cisco ISO

Diese Diagramme sind mit freundlicher Genehmigung von Michał Zalewskis Papier. In diesem speziellen Fall kann man, wenn man vorhersagen kann, wie die TCP-Sequenznummer von einem System sein wird, dieses System beim Herstellen einer Verbindung zu einem anderen System imitieren, was das Entführen von Verbindungen, das Abfangen von Kommunikation usw. erlauben würde. Und selbst wenn wir die nächste Nummer nicht 100% vorhersagen können, wenn wir eine neue Verbindung erstellen können unter unserer KontrolleWir können die Erfolgschancen erhöhen. Und wenn Computer in wenigen Sekunden 100.000 Verbindungen generieren können, steigt die Wahrscheinlichkeit eines erfolgreichen Angriffs von astronomisch auf möglich oder sogar wahrscheinlich.


155



Das ist so brillant, dass mir Tränen in die Augen kommen. Es sollte eine App geben, die diese für jedes Betriebssystem (mobil / Desktop / Server) und Plattform (JVM / Javascript / etc) erstellt. - HDave
Die Windows rand () Funktion ist ziemlich gut! Es erzeugt eine Wolke, die keine offensichtlichen Muster aufweist. Sehen Sie sich meine Implementierung an, um es (und andere Algorithmen) auszuprobieren: github.com/Zalastax/visualize_random - Zalastax


Während Pseudozufallszahlen, die von Computern erzeugt werden, für die Mehrzahl der Anwendungsfälle, die von Computerbenutzern angetroffen werden, akzeptabel sind, gibt es Szenarien, die dies erfordern vollständig unvorhersehbare Zufallszahlen.

In sicherheitsempfindlichen Anwendungen wie der Verschlüsselung kann ein Pseudozufallszahlengenerator (PRNG) Werte erzeugen, die, obwohl sie zufällig auftreten, tatsächlich von einem Angreifer vorhersagbar sind. Jemand, der versucht, ein Verschlüsselungssystem zu knacken, kann die Verschlüsselungsschlüssel erraten, wenn ein PRNG verwendet wurde und der Angreifer Informationen über den Zustand des PRNG hat. Daher ist für solche Anwendungen ein Zufallszahlengenerator notwendig, der Werte erzeugt, die wirklich nicht zu erkennen sind. Beachten Sie, dass Einige PRNGs sind kryptografisch sicher gestaltet und sind für solche sicherheitsempfindlichen Anwendungen verwendbar.

Weitere Informationen über RNG-Angriffe finden Sie in dieser Wikipedia-Artikel.


91



Kryptographische PRNGs existieren und sind weit verbreitet. Sie können aus einem mittelgroßen Samen einen praktisch unbegrenzten Strom von Zufallszahlen erzeugen. Es ist rechnerisch unmöglich, einen solchen Strom von echten Zufallszahlen zu unterscheiden, daher kann keine zusätzliche Information von irgendeinem Teil eines solchen Stroms gewonnen werden, und für irgendeinen praktischen Zweck sind die Zahlen so gut wie echte Zufallszahlen. - aaaaaaaaaaaa
Ich denke, der einfachste Weg, dies zu erklären, ist, dass Zufallsgenerator-Algorithmen programmiert werden müssen. Das heißt, es gibt eine Reihe von Anweisungen, die befolgt werden. Wenn es eine Reihe von Anweisungen gibt, kann es nicht zufällig sein. - Keltari
@ Keltari Du verpasst das Element der Entropie ... Die meisten RNGs (zumindest kryptographische) sammeln Input von externen Quellen (zB Mausbewegung) und benutzen dies als Teil der Startbedingung - also die Transformation von A zu B ist programmiert, aber der Ausgangszustand von A (sollte) unerforschbar sein. Linux /dev/random wird eine Annäherung an die verfügbare Entropie halten und aufhören, Zahlen auszugeben, wenn sie zu niedrig ist. - Basic
Aus Neugier - warum gelten Lavalampen als "wirklich zufällig"? Ich verstehe, dass es ein ziemlich unberechenbares Verhalten zeigt, aber jemand, der die Fluiddynamik fest im Griff hat und versteht, wie diese Fluide in der Gravitationsumgebung der Erde interagieren, kann sicherlich "vorhersehbare" Ergebnisse liefern, oder? Sicher, Lavalampen sind unberechenbar, aber für mich sind sie nicht zufällig, aber sehr vorhersehbar. - theGreenCabbage
@theGreenCabbage: Ich vermute, dass Lavalampen chaotisch sind. Bei einem Computermodell, das gut genug ist und genügend Genauigkeitsziffern, könnten Sie das Verhalten (im Prinzip) für eine Weile vorhersagen. Aber, weil das System chaotisch ist, werden zwei Lavalampen mit der kleinsten Änderung der Anfangsbedingungen schnell im Verhalten abweichen. (Und dieser Kommentar ignoriert chaotische Attraktoren.) - dmm


Ich habe es in Python versucht: Hier ist das Ergebnis von 60 Millionen Rollen. Die höchste Variation ist wie 0,15. Ist das nicht so zufällig wie es wird?

Eigentlich ist es so so "gut" ist es schlecht... Alle bestehenden Antworten stehen im Mittelpunkt Vorhersagbarkeit eine kleine Folge von Anfangswerten gegeben. Ich möchte ein anderes Problem ansprechen:

Ihre Verteilung hat viel kleinere Standardabweichung als zufällige Rollen sollte

Wahre Zufälligkeit kommt einfach nicht ganz Das nahe bei der Mittelung "fast genau 1 über wie immer viele Zahlen, die es wählen kann", die Sie als ein Hinweis auf Qualität verwenden.

Wenn du es ansiehst Diese Stack Exchange Frage nach Wahrscheinlichkeitsverteilungen für mehrere Würfelwürfe, sehen Sie eine Formel für die Standardabweichung von N Würfelrollen (unter der Annahme wirklich zufällige Ergebnisse):

 sqrt(N * 35.0 / 12.0).

Mit dieser Formel, die Standardabweichung zum:

  • 1 Million Rollen ist 1708
  • 60 Millionen Rollen ist 13229

Wenn wir uns Ihre Ergebnisse ansehen:

  • 1 Million Rollen: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) ist 804
  • 60 Millionen Rollen: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) ist 3827

Sie können nicht erwarten, dass die Standardabweichung einer endlichen Stichprobe genau mit der Formel übereinstimmt, aber sie sollte ziemlich nahe kommen. Doch bei 1 Million Rollen hast du weniger als die Hälfte der richtigen Stddev und bei 60 Millionen bist du unter einem Drittel - es wird immer schlimmer, und das ist kein Zufall ...

Pseudo-RNGs neigen dazu, sich durch eine Sequenz von verschiedenen Zahlen zu bewegen, wobei sie mit dem Keim beginnen und die ursprüngliche Zahl für einen bestimmten Zeitraum nicht erneut aufsuchen. Zum Beispiel Implementierungen der alten C-Bibliothek rand() Funktion haben normalerweise eine Periode von 2 ^ 32, und sie werden jede Zahl zwischen 0 und 2 ^ 32-1 genau einmal besuchen, bevor sie den Samen wiederholen. Wenn Sie also 2 ^ 32 Würfel simulieren, rollen Sie den Vormodul (%) Ergebnisse würden jede Zahl von 0 bis 2 ^ 32 enthalten, die Zählungen für jedes 1-6 Ergebnis wären 715827883 oder 715827882 (2 ^ 32 ist kein Vielfaches von 6) und die Standardabweichung daher nur trivial über 0. Using die obige Formel, die korrekte Standardabweichung für 2 ^ 32 Rollen ist 111924. Wie auch immer, wie Ihre Anzahl der Pseudozufallswalzen zunimmt, konvergieren Sie gegen 0 Standardabweichung. Es kann erwartet werden, dass das Problem signifikant ist, wenn die Anzahl der Rollen ein signifikanter Bruchteil der Periode ist, aber einige Pseudo-Zufallszahlen können schlechtere Probleme - oder Probleme sogar mit weniger Abtastungen - als andere aufweisen.

Selbst wenn Sie sich für kryptografische Schwachstellen nicht interessieren, können Sie in manchen Anwendungen Distributionen verwenden, die nicht übermäßig, künstlich sogar Ergebnisse liefern. Einige Arten von Simulationen versuchen ganz konkret, die Konsequenzen der ungleichmäßig Ergebnisse, die natürlicherweise bei großen Stichproben von einzelnen zufälligen Ergebnissen auftreten, aber in einigen pRNG-Ergebnissen unterrepräsentiert sind. Wenn Sie versuchen zu simulieren, wie eine große Bevölkerung auf ein Ereignis reagiert, könnte dieses Problem auftreten radikal Ändern Sie Ihre Ergebnisse, was zu völlig ungenauen Schlussfolgerungen führt.


Um ein konkretes Beispiel zu geben: Sagen Sie, ein Mathematiker sagt einem Pokermaschinen-Programmierer, dass er nach 60 Millionen simulierten Rollen Hunderte kleiner "Lichter" auf dem Bildschirm flimmern ließ, wenn 10.013.229 oder mehr Sechsen vorhanden waren, was der Mathematiker erwartet 1 Stddev weg von der Mitte, sollte es eine kleine Auszahlung geben. Pro 68-95-99,7 Regel (Wikipedia) das sollte ungefähr passieren 16% der Zeit (~ 68% fallen innerhalb einer Standardabweichung / nur die Hälfte außerhalb ist oben). Bei Ihrem Zufallszahlengenerator liegt dieser ab ca. 3,5 Standardabweichungen über dem Mittelwert: Unter 0,025% Chance - fast keine Kunden erhalten diesen Vorteil. Siehe die Tabelle mit den höheren Abweichungen auf der gerade erwähnten Seite, insbesondere:

| 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



Du vergleichst Äpfel und Orangen hier. Die beiden Standardabweichungen haben absolut nichts miteinander zu tun. - Jbeuh


Ich habe diesen Zufallszahlengenerator geschrieben, um Würfelwürfe zu generieren

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

Du benutzt es so

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

usw. Wären Sie glücklich, diesen Generator für ein Programm zu benutzen, das ein Würfelspiel lief? Denken Sie daran, seine Verteilung ist genau das, was Sie von einem "wirklich zufälligen" Generator erwarten würden!

Pseudozufallszahlengeneratoren machen im Wesentlichen dasselbe - sie erzeugen vorhersagbare Zahlen mit der richtigen Verteilung. Sie sind aus dem gleichen Grund schlecht, weil der obige simple Zufallszahlengenerator schlecht ist - sie sind nicht geeignet für Situationen, in denen Sie echte Unberechenbarkeit brauchen, nicht nur für die korrekte Verteilung.


50



"Pseudozufallszahlengeneratoren ... erzeugen vorhersagbare Zahlen mit der richtigen Verteilung" - Nur weil es ein PRNG ist, garantiert es nicht, dass es eine perfekte Verteilung hat (in der Tat, die kommerziellen im Großen und Ganzen nicht, für genau die in diesen Antworten beschriebene Gründe). Während sie bei ausreichender Information vorhersagbar sein können (Algo verwendet, Samen starten, Ausgabewerte, w / e), haben sie immer noch Varianz. - Brian S
Abgesehen davon, weiß ich, aber get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on ist einfach zu elegant, um nicht zu erwähnen :) - Janus Troelsen
@BrianS Eigentlich wäre eine PRNG, die im Laufe der Zeit Verteilungstests nicht bestanden hat, per Definition vorhersagbar. Wenn Sie also bei N großen N Flügen einen kleinen Weg von N / 2 Köpfen nehmen, können Sie auf Köpfchen setzen, und Sie können mehr gewinnen, als Sie verlieren. Ebenso, wenn Sie eine perfekte Verteilung der Köpfe v. Schwänze bekommen, aber Köpfe immer in Paaren kamen, dann würden Sie wieder ein Rezept haben, um zu gewinnen. Verteilungstests sind, wie Sie wissen, ein PRNG ist gut. - Jon Kiparsky
Du hast vergessen nonlocal next :-). - Kos
Noch besseres Beispiel: Pi wird geglaubt normalDies bedeutet, dass jede Folge von Ziffern beliebiger Länge in einer beliebigen Basis nicht häufiger erscheint als jede andere Folge dieser Länge in dieser Basis. Ein Algorithmus, der, wenn gefragt n zufällige Bits, nimmt die nächste n Bits von pi und gibt sie zurück (der "Keim" ist das Bit, auf dem Sie anfangen), sollte auf lange Sicht eine vollkommen gleichmäßige Verteilung erzeugen. Aber du würdest es immer noch nicht für deinen Generator wollen - jemand, der den letzten Haufen an Bits kennt, den du generiert hast, könnte das erste Mal finden, dass diese Sequenz auftritt, angenommen, dein Seed ist da und wahrscheinlich auch richtig. - cpast


Die Zufallszahlengenerierung, die Ihr Computer ausführen kann, ist für die meisten Bedürfnisse geeignet, und Sie werden wahrscheinlich nicht auf eine Zeit stoßen, in der Sie eine wirklich zufällige Zahl benötigen.

Die Erzeugung echter Zufallszahlen hat jedoch ihre Zwecke. In Computersicherheit, Glücksspiel, große statistische Stichproben, etc.

Wenn Sie sich für die Anwendung von Zufallszahlen interessieren, sehen Sie sich die Wikipedia-Artikel.


26



Das große Problem ist, wenn Sie Zufallszahlen benötigen, die ein Angreifer aus Sicherheitsgründen nicht vorhersagen kann. - David Schwartz
Sie werden sicher eine Zeit finden, wo Sie eine wirklich zufällige Zahl brauchen. Es genügt, eine Webseite zu öffnen, die mit beginnt https://... - Jan Hudec
@ JanHudec: Nun, im täglichen Gebrauch brauchen Sie sichere Zufallszahlen, sobald Sie ein Programm öffnen, lange bevor Sie in eine Adressleiste tippen: see Adressraum-Layout-Randomisierung. Deshalb solche Sachen das passiert. - Reid
@ JanHudec Ich habe speziell in dem Sinne gesprochen, dass Sie einen Online-Zufallszahlengenerator verwenden müssten. Wahre Zufallszahlen werden häufig verwendet, aber nur sehr wenige Menschen müssen sie selbst erzeugen. - Alex McKenzie
Spielautomaten benutzen auch einen PRNG, nicht einen TRNG. Der Generator läuft die ganze Zeit und eine Nummer wird genau zu dem Zeitpunkt ausgewählt, an dem der Drehknopf gedrückt wird. Die Summe von PRNG und der wirklich zufälligen Tastenbetätigungszeit ergibt einen TRNG. - Roger Dahl


Die von typischen Funktionen in den meisten Programmiersprachen erzeugten Zufallszahlen sind keine rein zufälligen Zahlen. Sie sind Pseudozufallszahlen. Da es sich nicht um Zufallszahlen handelt, können sie mit genügend Informationen über vorher erzeugte Zahlen erraten werden. Das wird also ein Katastrophe für die Sicherheit in der Kryptographie.

Für ein Beispiel wird die folgende Zufallsgeneratorfunktion verwendet glibc erzeugt keine reine Zufallszahl. Die dadurch generierte Pseudozufallszahl kann erraten werden. Es ist ein Fehler für Sicherheitsfragen. Es gibt eine Geschichte, die katastrophal wird. Dies sollte nicht in der Kryptographie verwendet werden.

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

Dieser Typ eines Pseudozufallszahlengenerators sollte niemals an sicherheitsempfindlichen Orten verwendet werden, obwohl er statistisch signifikant ist.

Einer der berühmten Angriffe auf Pseudozufallsschlüssel ist Angriff auf 802.11b WEP. WEP hat einen 104-Bit-Langzeitschlüssel, der mit einem 24-Bit-IV (Zähler) verkettet ist, um einen 128-Bit-Schlüssel zu bilden, der seinerseits angewendet wird RC4-Algorithmus um Pseudozufallsschlüssel zu erzeugen.

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

Die Schlüssel waren eng miteinander verwandt. Hier wurde nur IV in jedem Schritt um 1 erhöht und alle anderen blieben gleich. Da dies nicht rein zufällig war, war es katastrophal und leicht zusammenbrechen. Der Schlüssel könnte durch Analysieren von etwa 40000 Rahmen wiederhergestellt werden, was eine Angelegenheit von Minuten ist. Wenn das WEP rein zufällige 24-Bit-IV verwendet, dann könnte es bis etwa 2 ^ 24 (fast 16,8 Millionen) Frames sicher sein.

So sollte man bei sicherheitssensiblen Problemen möglichst mit reinem Zufallsgenerator arbeiten.


26



Ich würde das WEP-Zeug auf einem schlecht entworfenen Protokoll mit einer schwachen Chiffre beschuldigen. Mit modernen Stromverschlüsselungen können Sie einen Zähler als IV verwenden. - CodesInChaos
Das Hauptproblem bei WEP bestand darin, den Schlüssel in 2 ^ 24 (fast 16 Millionen) Frames zu wiederholen. Es war noch schlimmer mit verwandten Schlüsseln, die es ermöglichten, den Code in ungefähr 40000 Rahmen zu knacken. Der Hauptpunkt hier ist, dass der Schlüssel nicht zufällig ist. Es ist eng verwandt, so dass das leicht zu knacken ist. - Prabhu
Pseudozufälligkeit ist in der Kryptographie schlecht nur beim Generieren kryptografischer Schlüssel. Darüber hinaus ist es vollkommen in Ordnung. Tatsächlich ist RC4 wenig mehr als ein Pseudozufallszahlengenerator, der mit der 128-Bit-Erweiterung des XOR-Schlüssels auf den Klartext der Nachricht gesetzt wird. - Matt


Der Unterschied besteht darin, dass Pseudozufallszahlen nach einiger Zeit vorhersagbar (wiederholend) sind, wo dies keine echten Zufallszahlen sind. Die Länge, die für die Wiederholung benötigt wird, hängt von der Länge des Samens ab, das für seine Erzeugung verwendet wird.

Hier ist ein ziemlich nettes Video zu diesem Thema: http://www.youtube.com/watch?v=itaMNuWLzJo 


12



Vorhersagbarkeit! = Wiederholung. Mersenne Twister ist ein gutes Beispiel dafür. Bei den meisten Implementationen nach 624 Int32 kann man die nächste Zahl vorhersagen, aber die Mersenne Twister Sequenz ist viel länger als diese (2 ^ 19937 - 1). - HoLyVieR
Ich verstehe nicht, warum diese Antwort nicht auf den Stapel gebracht wird, da mir scheint, dass dies die genaue und prägnante Antwort auf die Frage ist, zumindest teilweise. Pseudozufallszahlen können nach einigen Ziehungen leicht vorhergesagt werden, wobei die Anzahl der Ziehungen mit dem Pseudozufallsalgorithmus "Qualität" variiert. Bei der Auswahl eines "guten" Algorithmus werden Aspekte berücksichtigt: 1. jeder Wert wird in gleicher Häufigkeit (Verteilung) gezeichnet, 2. es dauert eine "lange Zeit", um die Sequenz am Anfang neu zu starten und wieder die gleichen Zahlen in die zu zeichnen die selbe Reihenfolge. - mins
"Wahre Zufallszahlen sind nicht [vorhersehbar]". Für heute ist das wahr. Nun, wenn wir an die Urknalltheorie glauben und wir viel Kraft haben, um den Zustand des Universums jederzeit nach dem BB zu berechnen, basierend auf Physik dann ... können wir die Zukunft vorhersagen, einschließlich der Tatsache, dass Ich schreibe diesen sehr genauen Kommentar. Recht? - mins
Das ist hypothetisch richtig, aber angesichts der enormen Entropie, die bei den tatsächlichen Aktionen der realen Körper involviert ist, wäre die benötigte Rechenleistung lächerlich groß. Denken Sie an Kontinente, die mit Computern bedeckt sind. Wegen der Abhängigkeit vom vorherigen Zustand müsste außerdem der Zustand jedes Körpers im Universum zu jedem Zeitpunkt gespeichert werden, was definitionsgemäß mehr Platz erfordern würde, als im Universum verfügbar ist, vollständig gefüllt mit einem Speicherapparat - TheEnvironmentalist
@TheEnvironmentalist - Ah! "Kontinente, die mit Computern bedeckt sind" ... ist es nicht "Per Anhalter durch die Galaxis"? ;-) - ysap