Wie unterscheiden sich pseudozufällige und wirklich zufällige Zahlen und warum ist das wichtig?

Ich habe das nie ganz verstanden. Sagen Sie einfach, Sie schreiben ein kleines Programm in einer beliebigen Sprache, in dem einige Würfel gewürfelt werden (am Beispiel von Würfeln). Nach 600.000 Würfen wäre jede Zahl ungefähr 100.000 Mal gewürfelt worden, was ich erwarten würde.

Warum gibt es Websites, die der "wahren Zufälligkeit" gewidmet sind? Angesichts der obigen Beobachtung ist die Wahrscheinlichkeit, eine Zahl zu erhalten, fast genau 1, je nachdem, aus wie vielen Zahlen sie wählen kann.

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

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

Lass uns ein bisschen Computerpoker spielen, nur du, ich und ein Server, dem wir beide vertrauen. Der Server verwendet einen Pseudozufallszahlengenerator, der unmittelbar vor dem Spielen mit einem 32-Bit-Startwert initialisiert wird. Es gibt also ungefähr vier Milliarden mögliche Decks.

Ich habe fünf Karten auf der Hand - anscheinend spielen wir nicht Texas Hold'em. Angenommen, die Karten werden mir, Ihnen, mir, Ihnen usw. ausgeteilt. Ich habe also die erste, dritte, fünfte, siebte und neunte Karte im Stapel.

Früher habe ich den Pseudozufallszahlengenerator vier Milliarden Mal mit jedem Startwert ausgeführt und die jeweils erste erzeugte Karte in eine Datenbank geschrieben. Angenommen, meine erste Karte ist die Pik Dame. Das zeigt nur eine von 52 möglichen Decks als erste Karte. Daher haben wir die möglichen Decks von vier Milliarden auf ungefähr 80 Millionen reduziert.

Angenommen, meine zweite Karte besteht aus drei Herzen. Jetzt führe ich meinen RNG noch 80 Millionen Mal aus und benutze dabei die 80 Millionen Samen, aus denen die Pik Dame als erste Zahl hervorgeht. Das dauert ein paar Sekunden. Ich schreibe alle Stapel, aus denen die drei Herzen hervorgehen, als dritte Karte auf - die zweite Karte in meiner Hand. Das sind wieder nur etwa 2% der Decks, und jetzt sind es nur noch 2 Millionen Decks.

Angenommen, die dritte Karte in meiner Hand ist die 7 der Vereine. Ich habe eine Datenbank mit 2 Millionen Samen, die meine beiden Karten austeilen. Ich führe meine RNG weitere 2 Millionen Mal aus, um die 2% der Decks zu finden, aus denen die 7 der Clubs als dritte Karte hervorgehen, und wir haben nur noch 40.000 Decks.

Sie sehen, wie das geht. Ich führe meinen RNG 40000 mehrmals aus, um alle Samen zu finden, aus denen meine vierte Karte hervorgeht, und das bringt uns auf 800 Kartendecks. Dann führe ich den RNG 40000 mehrmals aus, um die ~ 20 Samen zu erhalten, aus denen meine fünfte Karte hervorgeht, und jetzt nur noch Generiere diese zwanzig Kartenspiele 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.

Sehen Sie jetzt, warum echte Zufälligkeit wichtig ist? So wie Sie es beschreiben, denken Sie, dass Verteilung wichtig ist, aber Verteilung ist nicht das, was einen Prozess zufällig macht. Unvorhersehbarkeit macht einen Prozess zufällig.

AKTUALISIEREN

Basierend auf den (aufgrund ihrer unkonstruktiven Natur jetzt gelöschten) Kommentaren sind mindestens 0,3% der Leute, die dies gelesen haben, in Bezug auf meinen Punkt verwirrt. Wenn Leute gegen Punkte argumentieren, die ich nicht gemacht habe, oder noch schlimmer, für Punkte argumentieren , die ich gemacht habe , unter der Annahme, dass ich sie nicht gemacht habe, dann weiß ich, dass ich klarer und sorgfältiger erklären muss.

Es scheint eine besondere Verwirrung um die Wortverteilung zu geben , daher möchte ich die Verwendung sorgfältig herausstellen.

Die anstehenden Fragen sind:

• Wie unterscheiden sich Pseudozufallszahlen von echten Zufallszahlen?
• Warum ist der Unterschied wichtig?
• Haben die Unterschiede etwas mit der Verteilung der PRNG-Ausgabe zu tun?

Betrachten wir zunächst den perfekten Weg, um ein zufälliges Kartenspiel zu generieren, mit dem Sie Poker spielen können. 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 Schachtel haben, die beschriftet ist TRNG. Als Eingabe geben wir ihm eine ganze Zahl n, die größer oder gleich eins ist, und als Ausgabe gibt es uns eine echte Zufallszahl zwischen eins und n, einschließlich. Die Ausgabe der Box ist völlig unvorhersehbar (wenn eine andere Zahl als eins angegeben wird) und jede Zahl zwischen eins und n ist genauso wahrscheinlich wie eine andere. das heißt, die Verteilung ist gleichmäßig . (Es gibt andere fortgeschrittenere statistische Überprü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 gesehen vollkommen zufällig.)

Wir beginnen mit einem nicht gemischten Kartenspiel. Wir bitten die Box um eine Zahl zwischen eins und 52 - das heißt TRNG(52),. Unabhängig von der Zahl, die es zurückgibt, zählen wir so viele Karten von unserem sortierten Stapel ab und entfernen diese Karte. Es wird die erste Karte im gemischten Deck. Dann bitten wir um TRNG(51)und tun dasselbe, um die zweite Karte auszuwählen und so weiter.

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

Jetzt geben wir die Karten aus. Wenn ich mir meine Karten ansehe, habe ich keine Ahnung, welche Karten Sie haben. (Abgesehen von der offensichtlichen Tatsache, dass Sie keine der Karten haben, die ich habe.) Es können alle Karten sein, mit gleicher Wahrscheinlichkeit.

Lassen Sie mich also sicherstellen, dass ich dies klar erkläre. Wir haben eine gleichmäßige Verteilung jedes einzelnen Outputs von TRNG(n); Jeder wählt eine Zahl zwischen 1 und n mit einer Wahrscheinlichkeit von 1 / n. Das Ergebnis dieses Prozesses ist, dass wir eines von 52 ausgewählt haben! möglich Decks mit einer Wahrscheinlichkeit von 1/52 !, so die Verteilung über die Menge der möglichen Decks sind auch einheitlich.

Gut.

Nehmen wir nun an, wir haben eine weniger magische Box mit der Bezeichnung PRNG. Bevor Sie es verwenden können, müssen sie werden ausgesät mit einem 32-Bit - Zahl ohne Vorzeichen.

ASIDE: Warum 32 ? Könnte es nicht mit einer 64- oder 256- oder 10000-Bit-Zahl geimpft werden? Sicher. Aber (1) in der Praxis werden die meisten handelsüblichen PRNGs mit einer 32-Bit-Zahl geimpft, und (2) wenn Sie 10000 zufällige Bits haben, um den Keim zu bilden, warum verwenden Sie dann überhaupt einen PRNG? Sie haben bereits eine Quelle von 10000 Zufälligkeiten!

Wie auch immer, zurück zur Funktionsweise des PRNG: Nachdem es ausgesät wurde, können Sie es genauso verwenden, wie Sie es verwenden TRNG. Das heißt, Sie übergeben ihm eine Zahl, n, und es gibt Ihnen eine Zahl zwischen 1 und n, einschließlich, zurück. Darüber hinaus ist die Verteilung dieser Ausgabe mehr oder weniger gleichmäßig . Das heißt, wenn wir PRNGnach einer Zahl zwischen 1 und 6 fragen , erhalten wir ungefähr jeweils ein Sechstel der Zeit 1, 2, 3, 4, 5 oder 6, unabhängig davon, um welchen Samen es sich handelt.

Ich möchte diesen Punkt mehrmals hervorheben, da er einige Kommentatoren verwirrt. Die Verteilung des PRNG ist auf mindestens zwei Arten gleichmäßig. Nehmen wir zunächst an, wir wählen einen bestimmten Samen. Wir würden erwarten , dass die Sequenz PRNG(6), PRNG(6), PRNG(6)...eine Million mal eine gleichmäßige Verteilung von Zahlen zwischen 1 erzeugen würde und 6. Und zweitens, wenn wir eine Million verschiedene Samen gewählt und rief PRNG(6) einmal für jeden Samen, wieder würden wir eine gleichmäßige Verteilung von Zahlen erwarten von 1 bis 6. Die Gleichförmigkeit des PRNG über beide dieser Operationen hinweg ist für den Angriff, den ich beschreibe, nicht relevant .

Dieser Prozess wird als pseudozufällig bezeichnet, da das Verhalten der Box tatsächlich vollständig deterministisch ist. es wählt aus 2 ³² möglichen Verhaltensweisen basierend auf dem Samen aus. Das heißt, sobald es ausgesät ist, PRNG(6), PRNG(6), PRNG(6), ... wird eine Folge von Zahlen mit einer gleichmäßigen Verteilung erzeugt, aber diese Folge wird vollständig durch den Samen bestimmt. Für eine bestimmte Folge von Aufrufen, z. B. PRNG (52), PRNG (51) usw., gibt es nur 2 ³² mögliche Folgen. Der Same entscheidet im Wesentlichen, welchen wir bekommen.

Um ein Deck zu generieren, generiert der Server jetzt einen Seed. (Wie? Wir kommen wieder zu diesem Punkt.) Dann rufen sie PRNG(52), PRNG(51)und so auf das Deck, ähnlich wie vor zu erzeugen.

Dieses System ist anfällig für den von mir beschriebenen Angriff. Um den Server anzugreifen, müssen wir zuerst unsere eigene Kopie der Box mit 0 ausstatten und danach fragen PRNG(52)und notieren. Dann setzen wir wieder 1 ein, fragen nach PRNG(52)und schreiben dies auf bis zu 2 ³² -1.

Jetzt muss der Pokerserver, der PRNG verwendet, um Decks zu generieren, irgendwie einen Startwert generieren. Es spielt keine Rolle, wie sie das tun. 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 kaum zufällig ist; Ich weiß genau wie Sie, wie spät es ist. Der Punkt meines Angriffs ist, dass es keine Rolle spielt, 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 hoher Wahrscheinlichkeit weiß, was in Ihrer Hand ist.

Ich möchte noch einmal betonen, dass wirPRNG(6) hier davon ausgehen, dass wir , wenn wir eine Million Mal anrufen würden, jede Zahl ungefähr ein Sechstel der Zeit erhalten würden . Diese Verteilung ist (mehr oder weniger) gleichmäßig , und wenn Sie sich nur für die Gleichmäßigkeit dieser Verteilung interessieren , ist das in Ordnung. Der Punkt der Frage war, ob es noch andere Dinge gibt PRNG(6), die uns interessieren? und die antwort ist ja . Uns liegt auch die Unvorhersehbarkeit am Herzen.

Eine andere Möglichkeit, das Problem zu betrachten, besteht darin, dass die Verteilung von einer Million Anrufen PRNG(6)möglicherweise in Ordnung ist, da der PRNG aus nur 2 ³² möglichen Verhaltensweisen auswählt , jedoch nicht jedes mögliche Deck generieren kann. Es können nur 2 ³² der 2 ²²⁶ möglichen Decks generiert werden . ein winziger Bruchteil. Die Verteilung auf alle Decks ist also sehr schlecht. Aber auch hier beruht der grundlegende Angriff darauf, dass wir das vergangene und zukünftige Verhalten einer kleinen Stichprobe ihrer Ergebnisse erfolgreich vorhersagen könnenPRNG .

Lassen Sie mich dies ein drittes oder viermal sagen, um sicherzustellen, dass dies eintritt. Hier gibt es drei Verteilungen. Erstens die Verteilung des Prozesses, der den zufälligen 32-Bit-Startwert erzeugt. Das kann vollkommen zufällig, unvorhersehbar und einheitlich sein und der Angriff wird immer noch funktionieren . Zweitens, die Verteilung von einer Million Anrufen an PRNG(6). Das kann vollkommen gleichmäßig sein und der Angriff wird immer noch funktionieren. Drittens die Verteilung der Decks, die nach dem von mir beschriebenen Pseudozufallsprozeß ausgewählt wurden. Diese Verteilung ist extrem schlecht; nur ein winziger Bruchteil der möglichen IRL-Decks kann möglicherweise ausgewählt werden. Der Angriff hängt von der Vorhersagbarkeit des Verhaltens des PRNG ab, basierend auf der teilweisen Kenntnis seines Outputs .

ASIDE: Für diesen Angriff muss der Angreifer den genauen vom PRNG verwendeten Algorithmus kennen oder erraten können. Ob das realistisch ist oder nicht, ist eine offene Frage. Allerdings , wenn ein Sicherheitssystem entwerfen Sie entwerfen müssen sie sicher vor Angriffen sein , 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 aus Sicherheitsgründen davon abhängt, dass die von Ihnen verwendeten Algorithmen geheim sind, enthält Ihr Schlüssel diese Algorithmen . Das ist eine extrem schwache Position!

Weitermachen.

Nehmen wir nun an, wir haben eine dritte beschriftete magische Kiste CPRNG. Es ist eine Krypto-Version von PRNG. Es wird ein 256-Bit-Startwert anstelle eines 32-Bit-Startwerts benötigt. Es teilt sich PRNGdie Eigenschaft, die der Startwert aus 2 ²⁵⁶ möglichen Verhaltensweisen auswählt . Und wie bei unseren anderen Maschinen hat es die Eigenschaft, dass eine große Anzahl von Aufrufen zu CPRNG(n)einer gleichmäßigen Verteilung der Ergebnisse zwischen 1 und n führt: jede geschieht 1 / n der Zeit. Können wir unseren Angriff dagegen führen?

Unser ursprünglicher Angriff erfordert, dass wir 2 ³² Zuordnungen von Samen zu speichern PRNG(52). 2 ²⁵⁶ ist jedoch eine viel größere Zahl; Es ist völlig unmöglich CPRNG(52), so oft auszuführen und die Ergebnisse zu speichern.

Angenommen, es gibt einen anderen Weg, um den Wert des CPRNG(52)Samens zu ermitteln und daraus eine Tatsache abzuleiten. Wir waren bisher ziemlich dumm und haben alle möglichen Kombinationen brachial erzwungen. Können wir in die magische Kiste schauen, herausfinden, wie sie funktioniert, und anhand der Ausgabe Fakten über den Samen ableiten?

Nein . Die Details sind zu kompliziert zu erklären, aber CPRNGs sind geschickt so konstruiert, dass es unmöglich ist , abzuleiten , jede nützliche Tatsache über die Samen aus dem ersten Ausgang CPRNG(52)oder von jeder Teilmenge des Ausgangs, egal wie groß .

Angenommen, der Server CPRNGgeneriert jetzt Decks. Es benötigt einen 256-Bit-Startwert. Wie wählt es diesen Samen aus? Wenn es einen Wert wählt, den ein Angreifer vorhersagen kann, wird der Angriff plötzlich wieder realisierbar . Wenn wir feststellen können, dass von den 2 ²⁵⁶ möglichen Startwerten wahrscheinlich nur vier Milliarden vom Server ausgewählt werden, sind wir wieder im Geschäft . Wir können diesen Angriff erneut starten, wobei wir nur auf die geringe Anzahl von Samen achten, die möglicherweise erzeugt werden können.

Der Server sollte daher sicherstellen, dass die 256-Bit-Zahl gleichmäßig verteilt ist, dh, jeder mögliche Startwert wird mit einer Wahrscheinlichkeit von 1/2 ^{256 ausgewählt} . Grundsätzlich sollte der Server anrufen TRNG(2^256)-1, um den Startwert für zu generieren CPRNG.

Was ist, wenn ich den Server hacken und in ihn hineinsehen kann, um zu sehen, welcher Startwert 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! (Wenn ich diesen Angriff erfolgreich ausführen kann, kann ich das Geld wahrscheinlich auch direkt auf mein Bankkonto überweisen. Das ist also vielleicht nicht so interessant. Der Punkt ist: Der Keim muss ein schwer zu erratendes Geheimnis sein, und a wirklich zufällige 256-Bit-Zahl ist verdammt schwer zu erraten.)

Zurück zu meinem früheren Punkt über die Tiefenverteidigung: Der 256-Bit-Startwert ist der Schlüssel für dieses 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, sind die Karten des Gegners unvorhersehbar, solange Sie den Schlüssel geheim halten können.

OK, also sollte der Samen sowohl geheim als auch gleichmäßig verteilt sein, denn wenn dies nicht der Fall ist, können wir einen Angriff starten. Wir gehen davon aus, dass die Verteilung der Outputs von CPRNG(n)gleichmäßig ist. Was ist mit der Aufteilung auf alle möglichen Decks?

Sie könnten sagen: Es gibt 2 ²⁵⁶ mögliche Sequenzen, die vom CPRNG ausgegeben werden, aber es gibt nur 2 ²²⁶ mögliche Decks. Daher gibt es mehr mögliche Sequenzen als Decks. In diesem System ist jetzt (mit hoher Wahrscheinlichkeit) jedes mögliche IRL-Deck möglich. Und das ist ein gutes Argument, außer ...

2 ²²⁶ ist nur eine Annäherung an 52 !. Teilen Sie es aus. 2 ^256/52 ! kann unmöglich eine ganze Zahl sein, weil zum einen 52! ist durch 3 teilbar, aber keine Potenz von zwei ist! Da dies jetzt keine ganze Zahl ist, haben wir die Situation, in der alle Decks möglich sind , aber einige Decks sind wahrscheinlicher als andere .

Wenn das nicht klar ist, betrachten Sie die Situation mit kleineren Zahlen. Angenommen, wir haben drei Karten, A, B und C. Angenommen, wir verwenden ein PRNG mit einem 8-Bit-Startwert, sodass 256 mögliche Startwerte vorhanden sind. Es gibt 256 mögliche Ausgaben, PRNG(3)abhängig von der Saat; Es gibt keine Möglichkeit, ein Drittel von ihnen A, ein Drittel von ihnen B und ein Drittel von ihnen C zu haben, da 256 nicht gleichmäßig durch 3 teilbar ist. Es muss eine geringe Tendenz zu einem von ihnen bestehen.

In ähnlicher Weise teilt sich 52 nicht gleichmäßig in 2 ²⁵⁶ , so dass es eine gewisse Neigung zu einigen Karten als der zuerst gewählten Karte und eine Neigung zu anderen geben muss.

In unserem ursprünglichen System mit einem 32-Bit-Startwert gab es eine massive Verzerrung, und die große Mehrheit der möglichen Decks wurde nie produziert. In diesem System können alle Decks produziert werden, aber die Verteilung der Decks ist immer noch fehlerhaft . Einige Decks sind etwas wahrscheinlicher als andere.

Die Frage ist nun: Haben wir einen Angriff, der auf diesem Fehler beruht? und die Antwort ist in der Praxis wahrscheinlich nicht . CPRNGs sind so ausgelegt, dass , wenn die Samen wirklich zufällig ist dann es rechnerisch unmöglich ist , den Unterschied zwischen zu sagen , CPRNGund TRNG.

OK, also lassen Sie uns zusammenfassen.

Wie unterscheiden sich Pseudozufallszahlen von echten Zufallszahlen?

Sie unterscheiden sich in der Berechenbarkeit, die sie aufweisen.

• Wirklich zufällige Zahlen sind nicht vorhersehbar.
• Alle Pseudozufallszahlen sind vorhersehbar, wenn der Keim bestimmt oder erraten werden kann.

Warum ist der Unterschied wichtig?

Weil es Anwendungen gibt, bei denen die Sicherheit des Systems auf Unvorhersehbarkeit beruht .

• Wenn eine TRNG zur Auswahl jeder Karte verwendet wird, ist das System nicht verfügbar.
• Wenn eine CPRNG verwendet wird, um jede Karte auszuwählen, ist das System sicher, wenn der Startwert sowohl unvorhersehbar als auch unbekannt ist.
• Wenn ein gewöhnliches PRNG mit einem kleinen Saatgutraum verwendet wird, ist das System nicht sicher, unabhängig davon, ob das Saatgut unvorhersehbar oder unbekannt ist. Ein ausreichend kleiner Saatraum ist anfällig für Brute-Force-Angriffe der von mir beschriebenen Art.

Hat der Unterschied etwas mit der Verteilung der PRNG-Ausgabe zu tun?

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

Wie wir gesehen haben, ergibt sich sowohl eine PRNGals auch CPRNGeine schlechte Verteilung der Wahrscheinlichkeit, ein einzelnes Deck aller möglichen Decks zu wählen. Das PRNGist erheblich schlimmer, aber beide haben Probleme.

Noch eine Frage:

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

Zwei Gründe.

Erstens: Aufwand. TRNG ist teuer . Es ist schwierig, wirklich Zufallszahlen zu generieren. CPRNGs liefern gute Ergebnisse für beliebig viele Anrufe mit nur einem Anruf bei TRNG für den Startwert. Der Nachteil ist natürlich, dass Sie diesen Samen geheim halten müssen .

Zweitens: Manchmal wollen wir Berechenbarkeit, und alles, was uns wichtig ist, ist eine gute Verteilung. Wenn Sie "zufällige" Daten als Programmeingaben für eine Testsuite generieren und ein Fehler auftritt, ist es schön, wenn die Testsuite erneut ausgeführt wird und der Fehler erneut auftritt!

Ich hoffe das ist jetzt viel klarer.

Wenn Ihnen das gefallen hat, können Sie vielleicht weitere Informationen zum Thema Zufälligkeit und Permutationen lesen:

• Angenommen, ich habe zufällige Daten gleichmäßig verteilt. Wie wandle ich es in eine gegebene ungleichmäßige Verteilung um?
• Warum werden einige GUIDs zufällig generiert? Sind alle ihre Teile zufällig? (Nein.) Kann ich mich auf eine GUID als Quelle wahrer Zufälligkeit verlassen? (Nein!)
• Wie kann ich große Zufallszahlen mit faktoradischer Notation erzeugen?
  • Wie kann ich daraus eine zufällige Permutation machen?
• Wie können wir den hier beschriebenen Angriff gegen die zufällige Permutation montieren?
• Wie viel Verzerrung wird durch die Verwendung der Resttechnik eingeführt RNG(n)?

Wie Eric Lippert sagt, handelt es sich nicht nur um Distribution. Es gibt andere Möglichkeiten, die Zufälligkeit zu messen.

Einer der frühen Zufallszahlengeneratoren hat eine Sequenz im niedrigstwertigen Bit - es wechselten Nullen und Einsen. Daher war das LSB zu 100% vorhersehbar. Aber Sie müssen sich um mehr Sorgen machen. Jedes Bit muss unvorhersehbar sein.

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

Zeichnen Sie nun ein 2D-Diagramm. Je größer die Zahl, desto heller 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:

oder sogar dieses von Windows 98:

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

Diese Diagramme wurden mit freundlicher Genehmigung von Michał Zalewski erstellt . In diesem speziellen Fall kann man, wenn man die TCP-Sequenznummer eines Systems vorhersagen kann, beim Herstellen einer Verbindung zu einem anderen System die Identität dieses Systems annehmen - was die Entführung von Verbindungen, das Abfangen der Kommunikation usw. ermöglichen würde. Und selbst wenn wir Ich kann die nächste Zahl nicht in 100% der Fälle vorhersagen. Wenn wir unter unserer Kontrolle eine neue Verbindung herstellen , können wir die Erfolgschancen erhöhen. Und wenn Computer in wenigen Sekunden 100.000 Verbindungen herstellen können, ändert sich die Wahrscheinlichkeit eines erfolgreichen Angriffs von astronomisch zu möglich oder sogar wahrscheinlich.

Während von Computern generierte Pseudozufallszahlen für die meisten Anwendungsfälle von Computernutzern akzeptabel sind, gibt es Szenarien, die völlig unvorhersehbare Zufallszahlen erfordern .

In sicherheitsrelevanten Anwendungen wie der Verschlüsselung kann ein Pseudozufallszahlengenerator (Pseudorandom Number Generator, PRNG) Werte erzeugen, die zwar zufällig aussehen, von einem Angreifer jedoch tatsächlich vorhersehbar sind. Jemand, der versucht, ein Verschlüsselungssystem zu knacken, kann möglicherweise die Verschlüsselungsschlüssel erraten, wenn ein PRNG verwendet wurde und der Angreifer Informationen über den Status des PRNG hat. Daher ist für solche Anwendungen ein Zufallszahlengenerator erforderlich, der Werte erzeugt, die wirklich nicht zu erraten sind. Beachten Sie, dass einige PRNGs kryptografisch sicher sind und für solche sicherheitsrelevanten Anwendungen verwendet werden können.

Weitere Informationen zu RNG-Angriffen finden Sie in diesem Wikipedia-Artikel .

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

Eigentlich ist es so "gut" , dass es so schlecht ist ... Alle vorhandenen Antworten konzentrieren sich auf Vorhersagbarkeit bei einer kleinen Folge von Anfangswerten. Ich möchte ein anderes Problem ansprechen:

    Ihre Verteilung weist eine viel geringere Standardabweichung auf, als dies bei Zufallsrollen der Fall sein sollte

Echte Zufälligkeit kommt nur nicht ganz , dass die Nähe „fast genau 1 über wie immer viele Zahlen sie können wählen , von“ zu durchschnittlich , dass man als Hinweis auf der Qualität verwenden.

Wenn Sie sich diese Stapelaustausch-Frage zu Wahrscheinlichkeitsverteilungen für mehrere Würfelwürfe ansehen, sehen Sie eine Formel für die Standardabweichung von N Würfelwürfen (unter der Annahme wirklich zufälliger Ergebnisse):

 sqrt(N * 35.0 / 12.0).

Mit dieser Formel wird die Standardabweichung für:

• 1 Million Rollen ist 1708
• 60 Millionen Rollen sind 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, sie sollte jedoch ziemlich nahe kommen. Bei 1 Million Würfeln haben Sie jedoch weniger als die Hälfte des richtigen stddev, und bei 60 Millionen sind Sie unter einem Drittel - es wird schlimmer, und das ist kein Zufall.

Pseudo-RNGs bewegen sich in der Regel durch eine Folge unterschiedlicher Nummern, wobei sie mit dem Startwert beginnen und die ursprüngliche Nummer für einen bestimmten Zeitraum nicht erneut aufrufen. Beispielsweise haben Implementierungen der alten C-Bibliotheksfunktion rand()normalerweise eine Periode von 2 ^ 32, und sie besuchen jede Zahl zwischen 0 und 2 ^ 32-1 genau einmal, bevor sie den Startwert wiederholen. Wenn Sie also 2 ^ 32 Würfel simuliert haben, würfelt der Vormodul (%) die 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 würde daher nur geringfügig über 0 liegen In der obigen Formel ist die korrekte Standardabweichung für 2 ^ 32 Rollen 111924. Wie auch immer, wenn Ihre Anzahl von Pseudozufallsrollen zunimmt, konvergieren Sie gegen 0 Standardabweichung. Es ist zu erwarten, dass das Problem erheblich ist, wenn die Anzahl der Rollen einen erheblichen Teil des Zeitraums ausmacht. Einige Pseudo-RNGs können jedoch schlimmere Probleme aufweisen - oder sogar Probleme mit weniger Proben - als andere.

Selbst wenn Sie sich nicht um kryptografische Schwachstellen kümmern, ist es in einigen Anwendungen wichtig, dass Distributionen keine übermäßigen, künstlich gleichmäßigen Ergebnisse erzielen. Einige Simulationstypen versuchen ganz spezifisch, die Konsequenzen der ungleichmäßigen Ergebnisse zu ermitteln, die natürlich bei großen Stichproben einzelner zufälliger Ergebnisse auftreten, sind jedoch in einigen pRNG-Ergebnissen unterrepräsentiert. Wenn Sie versuchen zu simulieren, wie eine große Population auf ein Ereignis reagiert, kann dieses Problem Ihre Ergebnisse radikal verändern und zu äußerst ungenauen Schlussfolgerungen führen.

Um ein konkretes Beispiel zu nennen: Ein Mathematiker sagt einem Programmierer eines Pokerautomaten, dass nach 60 Millionen simulierten Würfeln Hunderte von kleinen "Lichtern" auf dem Bildschirm flackern, wenn es 10.013.229 oder mehr Sechser gegeben hat, was der Mathematiker erwartet 1 stddev vom Mittelwert entfernt, sollte es eine kleine Auszahlung geben. Nach der 68–95–99.7-Regel (Wikipedia) sollte dies in etwa 16% der Fälle der Fall sein (~ 68% liegen innerhalb einer Standardabweichung / nur die Hälfte außerhalb liegt darüber). Mit Ihrem Zufallsgenerator liegt dies ab etwa 3,5 Standardabweichungen über dem Mittelwert: Unter 0,025% Chance - fast keine Kunden erhalten diesen Vorteil. Siehe die Tabelle "Höhere 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                |

Ich habe gerade 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

etc etc. Würden Sie diesen Generator gerne für ein Programm verwenden, das ein Würfelspiel ausführt? Denken Sie daran, dass die Verteilung genau das ist, was Sie von einem "wirklich zufälligen" Generator erwarten würden!

Pseudozufallszahlengeneratoren machen im Wesentlichen dasselbe - sie generieren vorhersagbare Zahlen mit der richtigen Verteilung. Sie sind aus dem gleichen Grund schlecht, wie der oben genannte vereinfachte Zufallszahlengenerator schlecht ist - sie eignen sich nicht für Situationen, in denen echte Unvorhersehbarkeit erforderlich ist, nicht nur die richtige Verteilung.

Die Zufallszahlengenerierung, die Ihr Computer ausführen kann, ist für die meisten Anforderungen geeignet, und es ist unwahrscheinlich, dass Sie auf eine Zeit stoßen, in der Sie eine wirklich zufällige Zahl benötigen.

Echte Zufallszahlengenerierung hat jedoch ihre Absichten. In Bezug auf Computersicherheit, Glücksspiele, umfangreiche statistische Stichproben usw.

Wenn Sie an der Anwendung von Zufallszahlen interessiert sind, lesen Sie den Wikipedia-Artikel .

Die von typischen Funktionen in den meisten Programmiersprachen erzeugten Zufallszahlen sind keine reinen Zufallszahlen. Sie sind Pseudozufallszahlen. Da es sich nicht nur um Zufallszahlen handelt, können sie mit genügend Informationen zu zuvor generierten Zahlen erraten werden. Dies wird also eine Katastrophe für die Sicherheit in der Kryptographie sein .

Zum Beispiel erzeugt die folgende Zufallszahlengeneratorfunktion, die in glibcverwendet wird, keine reine Zufallszahl. Die dabei erzeugte Pseudozufallszahl kann erraten werden. Es ist ein Fehler für Sicherheitsfragen. Es gibt eine Geschichte, in der dies 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

Diese Art von Pseudozufallszahlengenerator sollte niemals an sicherheitsrelevanten Orten verwendet werden, auch wenn sie statistisch weit verbreitet sind.

Einer der bekanntesten Angriffe auf Pseudozufallsschlüssel ist der Angriff auf 802.11b WEP . WEP verfügt über einen 104-Bit-Langzeitschlüssel, der mit 24-Bit-IV (Zähler) verknüpft ist, um einen 128-Bit-Schlüssel zu erstellen , der wiederum auf den RC4-Algorithmus angewendet wird, um einen Pseudozufallsschlüssel zu generieren.

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

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

Deshalb sollte man bei sicherheitsrelevanten Themen möglichst auf einen reinen Zufallsgenerator setzen.

Der Unterschied besteht darin, dass pseudozufällig generierte Zahlen nach einiger Zeit vorhersehbar sind (sich wiederholen), wenn echte Zufallszahlen dies nicht tun. Die Länge der Wiederholung hängt von der Länge des Samens ab, der für seine Erzeugung verwendet wird.

Hier ist ein hübsches Video zu diesem Thema: http://www.youtube.com/watch?v=itaMNuWLzJo

Angenommen, eine Pseudozufallszahl kann von jedem erraten werden, bevor sie generiert wird.

Für triviale Anwendungen ist eine Pseudozufälligkeit in Ordnung. Wie in Ihrem Beispiel erhalten Sie ungefähr den richtigen Prozentsatz (ungefähr 1/6 der gesamten Ergebnismenge) mit geringfügigen Abweichungen (die Sie sehen würden, wenn Sie 600.000 würfeln würden) mal);

Wenn es jedoch um Dinge wie Computersicherheit geht; Echte Zufälligkeit ist erforderlich.

Der RSA-Algorithmus beginnt beispielsweise damit, dass der Computer zwei Zufallszahlen (P und Q) auswählt und diese Zahlen dann in mehreren Schritten verarbeitet, um die als öffentliche und private Schlüssel bekannten Spezialzahlen zu generieren. (Der wichtige Teil eines privaten Schlüssels ist, dass er privat ist und niemand sonst weiß es!)

Wenn ein Angreifer wissen kann, welche der beiden "Zufallszahlen" Ihr Computer auswählen wird, kann er die gleichen Schritte ausführen, um Ihren privaten Schlüssel zu berechnen (die, die sonst niemand wissen soll!).

Mit Ihrem privaten Schlüssel kann ein Angreifer Folgendes tun: a) Sprechen Sie mit Ihrer Bank, um vorzutäuschen, Sie zu sein. B) Hören Sie auf Ihren "sicheren" Internetverkehr und können Sie ihn entschlüsseln. C) Maskieren Sie sich zwischen Ihnen und anderen Parteien im Internet.

Das ist der Punkt, an dem echte Zufälligkeit erforderlich ist (dh nicht erraten / berechnet werden kann).

Die erste Zufallszahl, die ich jemals verwendet habe, hatte die hervorragende Eigenschaft, dass von zwei aufeinander folgenden Zufallszahlen die zweite mit einer Wahrscheinlichkeit von 0,6 größer war. Nicht 0,5. Und der dritte war größer als der zweite mit einer Wahrscheinlichkeit von 0,6 und so weiter. Sie können sich vorstellen, wie sich das auf eine Simulation auswirkt.

Einige Leute würden mir nicht glauben, dass dies überhaupt möglich ist, wenn die Zufallszahlen gleich verteilt sind, aber es ist offensichtlich möglich, wenn Sie sich die Sequenz ansehen (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ...) wobei die zweite von zwei Zahlen mit einer Wahrscheinlichkeit von 0,6 größer ist.

Andererseits kann es für Simulationen wichtig sein, Zufallszahlen reproduzieren zu können. Angenommen, Sie führen eine Verkehrssimulation durch und möchten herausfinden, wie Sie durch bestimmte Maßnahmen den Verkehr verbessern können. In diesem Fall möchten Sie in der Lage sein, mit verschiedenen Aktionen, die Sie zur Verbesserung des Verkehrs unternommen haben, exakt dieselben Verkehrsdaten (wie bei Personen, die versuchen, eine Stadt zu betreten) wiederherzustellen.

Die kurze Antwort lautet, dass Menschen normalerweise "echte Zufälligkeit" aus einem schlechten Grund fordern, nämlich, dass sie kein Verständnis für Kryptographie haben.

Kryptografische Grundelemente wie Stream-Chiffren und CSPRNGs werden verwendet, um riesige Streams unvorhersehbarer Bits zu erzeugen, sobald sie mit einigen unvorhersehbaren Bits versorgt wurden.

Der aufmerksame Leser wird nun bemerkt haben, dass es hier ein Bootstrapping-Problem gibt: Wir müssen ein paar Entropiebits sammeln, um alles zu starten. Dann kann be sie einem CSPRNG zuführen, der wiederum alle unvorhersehbaren Bits bereitstellt, die wir benötigen. Daher ist ein Hardware-RNG erforderlich, um einen CSPRNG zu erzeugen . Dies ist der einzige Fall, in dem Entropie in Wahrheit erforderlich ist.

(Ich denke, das hätte in Sicherheit oder Kryptografie gepostet werden sollen.)

Bearbeiten: Am Ende muss man einen Zufallszahlengenerator auswählen, der für die vorgesehene Aufgabe gut genug ist, und was die Zufallszahlengenerierung betrifft, muss die Hardware nicht unbedingt gut sein. Genauso wie schlechte PRNGs weisen zufällige Hardwarequellen normalerweise Vorurteile auf.

Bearbeiten: Einige Leute hier nehmen ein Bedrohungsmodell an, in dem ein Angreifer den internen Status eines CSPRNG lesen und daraus den Schluss ziehen kann, dass CSPRNGs keine sichere Lösung sind. Dies ist ein Beispiel für eine schlechte Thread-Modellierung. Wenn ein Angreifer Ihr System besitzt, ist das Spiel einfach vorbei. Es spielt keine Rolle, ob Sie an dieser Stelle einen TRNG oder einen CSPRNG verwenden.

Edit: Also, um alles zusammenzufassen ... Entropie ist erforderlich, um ein CSPRNG zu setzen. Sobald dies erledigt ist, liefert ein CSPRNG alle unvorhersehbaren Bits, die wir für Sicherheitsanwendungen benötigen, viel schneller, als wir (normalerweise) Entropie sammeln können. Wenn keine Unvorhersehbarkeit erforderlich ist, z. B. für die Simulation, liefert ein Mersenne-Twister Zahlen mit guten statistischen Eigenschaften mit einer viel höheren Rate.

Bearbeiten: Jeder, der das Problem der sicheren Zufallszahlengenerierung verstehen möchte, sollte dies lesen: http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf

Nicht alle PRNGs sind für alle Verwendungszwecke geeignet. Beispielsweise verwendet Java.util.SecureRandom den SHA1-Hash mit einer Ausgabegröße von 160 Bit. Das heißt, es gibt 2 ¹⁶⁰ mögliche Zufallszahlenströme, die daraus entstehen können. So einfach ist das. Sie können nicht mehr als 2 ¹⁶⁰ Werte des internen Status abrufen. Somit können Sie nicht mehr als 2 ¹⁶⁰ eindeutige Zufallszahlenströme aus einem einzelnen Samen erhalten, unabhängig davon, woher Ihr Samen stammt. Es wird angenommen, dass Windows CryptGenRandom einen 40-Byte-Status verwendet und über 2 ³²⁰ mögliche Zufallszahlenströme verfügt.

Die Anzahl der Möglichkeiten, ein Standardkartenspiel mit 52 Karten zu mischen, beträgt 52 !, was ungefähr 2 ^{226 entspricht} . Unabhängig vom Seeding können Sie daher Java.util.SecureRandom nicht verwenden, um ein Kartenspiel zu mischen. Es gibt ungefähr 2 ⁶⁶ mögliche Mischvorgänge, die es nicht produzieren kann. Natürlich wissen wir nicht, welche es sind ...

Wenn ich also eine Quelle von beispielsweise 256 Bit wahrer Zufälligkeit hätte (z. B. von einer Quantis RNG-Karte), könnte ich einen PRNG wie CryptGenRandom () mit diesem Samen ausstoßen und dann den PRNG zum Mischen eines Decks von verwenden Karten. Wenn ich jeden Shuffle mit echter Zufälligkeit neu einsetze, ist das in Ordnung: unvorhersehbar und statistisch zufällig. Wenn ich dasselbe mit Java.util.SecureRandom machen würde, gäbe es Shuffles, die möglicherweise nicht erzeugt werden könnten, da sie nicht mit 256 Bit Entropie geimpft werden können und ihr interner Zustand nicht alle möglichen Shuffles darstellen kann.

Beachten Sie, dass die Ergebnisse von java.util.SecureRandom sowohl unvorhersehbar als auch statistisch zufällig sind. Kein statistischer Test würde jemals ein Problem identifizieren! Die Ausgabe des RNG ist jedoch nicht groß genug, um den gesamten Bereich aller möglichen Ausgaben abzudecken, die zum Simulieren eines Kartenspiels erforderlich sind.

Und denken Sie daran, wenn Sie die Joker hinzufügen, ist es 54! Das müssen Sie abdecken, was ungefähr 2 ²³⁸ Möglichkeiten erfordert .

Pseudo - Zufallszahlen sind , eine mathematische Funktion und einen Anfangswert erzeugt wird unter Verwendung von (die angerufene seed ), während der Zufallszahlen nicht. Ihre Vorhersehbarkeit macht sie für Spielwiederholungen unglaublich nützlich, da Sie nur den Startwert und die Eingaben des Spielers speichern müssen - die KI reagiert jedes Mal genau gleich "zufällig".

Der Unterschied zwischen "echten" Zufallszahlen und "Pseudo" -Zufallszahlen ist die Vorhersagbarkeit. Diese Antwort wurde bereits gegeben.

Die Vorhersehbarkeit ist jedoch nicht unbedingt eine schlechte Sache, wie die meisten Beispiele zeigen. Hier ist ein praktisches Beispiel für einen der seltenen Fälle, in denen die Vorhersagbarkeit gut ist: Das Global Positioning System.

Jeder Satellit verwendet einen eigenen PRN-Code (die Gold-Codes ), der für die zur Messung der Signallaufzeit erforderliche Autokorrelation oder Kreuzkorrelation geeignet ist. Für diese Goldcodes ist die Korrelation untereinander besonders schwach, was eine eindeutige Identifizierung des Satelliten ermöglicht, aber die Entfernungsberechnung durch die Korrelation zwischen der gesendeten Sequenz und dem Empfänger ermöglicht.

Zur schnellen Überprüfung der Zufälligkeit nehmen Sie Punkte mit zufälligen Koordinaten in [0; 1) und setzen sie dann in einen k-dimensionalen Würfel. Dann führen Sie eine Prozedur durch, um diesen Würfel in Unterwürfel zu schneiden - jedes Volumen des Unterwürfels (oder der Unterwürfel) muss nach dieser Prozedur mit Schwankungen gemäß dem bekannten Theorem korrekt gemessen werden.

Qualität der Zufälligkeit ist wichtig, wo Sie sich treffen ...

1. Sicherheitsgründe. Wenn Sie eine Zahl für die Verwendung als Parameter für Ihre Schlüsselgenerierung generieren und diese gut vorhersehbar ist, wird der Feind sie mit einer Wahrscheinlichkeit von 100% herausfinden und das Suchfeld erheblich verkleinern.

2. wissenschaftliche Zwecke. In der Wissenschaft muss nicht nur der Mittelwert in gutem Zustand sein, sondern es müssen auch Korrelationen zwischen verschiedenen Zufallszahlen beseitigt werden. Wenn Sie also (a_i - a) (a_ {i + 1} -a) nehmen und die Verteilung finden, muss sie der Statistik entsprechen.

Die Paarkorrelation wird als "schwache Zufälligkeit" bezeichnet. Wenn Sie echte Zufälligkeit wünschen, müssen Sie eine Korrelation hoher Ordnung mit mehr als 2 Varianzen aufweisen.

Heute liefern nur Generatoren der Quantenmechanik echte Zufälligkeit.

Warum ist wahre Zufälligkeit wichtig?

Grundsätzlich gibt es zwei Hauptgründe, warum echte Zufälligkeit notwendig ist:

1. Wenn Sie das RNG für die Kryptografie verwenden (einschließlich Echtgeld-Glücksspiel und Lottogewinn), werden Sie durch ein PRNG viel schwächer als durch eine mathematische Analyse (die ein TRNG voraussetzt) ​​angenommen. Der PRNG ist nicht zufällig, sondern weist ein Muster auf. Angreifer können das Muster ausnutzen, um eine Chiffre zu knacken, die nicht geknackt werden sollte.
2. Wenn Sie das RNG verwenden, um "zufällige" Eingaben zu simulieren, zum Beispiel zum Testen von Fehlern oder zur Simulation, macht ein PRNG Ihren Ansatz schwach. Wenn Sie keine Bugs entdecken, wird es immer diesen nagenden Zweifel geben: Gibt es einen Bug, der im PRNG-Muster nicht auffällt, aber aufgetaucht wäre, wenn ich nur einen TRNG verwendet hätte? Beschreiben die Ergebnisse meiner Simulation die Realität genau, oder ist das von mir entdeckte Phänomen einfach ein Artefakt des PRNG-Musters?

Außerhalb dieser Gebiete spielt es keine Rolle. Vorsichtsmaßnahme: Wenn Ihr PRNG sehr, sehr schlecht ist, könnte es dennoch ungeeignet sein - Sie möchten kein Craps-Spiel machen, bei dem die Würfel immer gleich hoch kommen, was Ihren Spielern nicht gefällt.

Wie ist Pythons PRNG nicht gut genug?

Es ist sehr unwahrscheinlich, dass Sie die Fallstricke eines echten PRNG mithilfe einer derart einfachen Methode erkennen können. Die statistische Analyse von RNGs ist ein eigenständiges Wissenschaftsgebiet, und es stehen einige sehr komplexe Tests zur Verfügung, um die "Zufälligkeit" eines Algorithmus zu bewerten. Diese sind viel weiter fortgeschritten als Ihr einfacher Versuch.

Jeder Softwareentwickler, der echte Bibliotheken erstellt, wie z. B. die Python-Entwickler, verwendet diese statistischen Tests als Maßstab, um festzustellen, ob die PRNG-Implementierung gut genug ist. Daher ist es sehr unwahrscheinlich, dass Sie ein Muster in einem realen PRNG leicht erkennen können, außer in Fällen, in denen der Entwickler tatsächlich die Kontrolle hat. Das bedeutet nicht, dass es kein Muster gibt - ein PRNG hat per Definition ein Muster.

Grundsätzlich können Sie nicht beweisen, dass eine Quelle zufällig ist, indem Sie die Ausgabe mathematisch analysieren. Sie benötigen z. B. ein physikalisches Modell, das besagt, dass die Quelle zufällig ist (wie beim radioaktiven Zerfall).

Sie können nur Stapeltests ausführen, um statistische Korrelationen in den Ausgabedaten zu ermitteln. In diesem Fall ist der Nachweis erbracht, dass die Daten nicht zufällig sind (aber auch eine zufällige Quelle kann nicht zufällige Ausgaben haben, oder sie ist nicht wirklich zufällig, wenn sie keine spezifischen Daten enthält Ausgabe). Andernfalls können Sie bei Bestehen von Tests sagen, dass die Daten pseudozufällig sind.

Das Bestehen einiger Zufallstests bedeutet nur, dass Sie über einen guten PRNG (Pseudozufallszahlengenerator) verfügen, der für Anwendungen nützlich sein kann, bei denen die Sicherheit nicht betroffen ist.

Wenn es um Sicherheit geht (z. B. Verschlüsselung, Generierung eines Schlüsselsalzes, Generierung von Zufallszahlen für Glücksspiele ...), ist es nicht ausreichend, ein gutes PRNG zu haben. Es müssen zusätzliche Eigenschaften vorhanden sein, z. B., dass die Funktionsausgabe nicht leicht von vorherigen Ausgaben erraten werden kann. Die Funktion muss einen wünschenswerten Rechenaufwand haben (begrenzt genug, um verwendbar zu sein, aber hoch genug, um brutale Erzwingungsversuche zu verhindern), die Hardware, auf der die Funktion ausgeführt wird - oder das Gerät, im heutigen Fall ist es ein analoges Gerät - sollte es nicht leicht manipuliert werden, etc.

Ein gutes PRNG kann in Spielen nützlich sein, um neue und unvorhersehbare Muster zu erstellen, und bei der Verschlüsselung - zu umständlich, um in einem einzelnen Beitrag erklärt zu werden. Denken Sie nur als Daumenrolle, welcher Ausgang des Verschlüsselungsverfahrens pseudozufällig sein sollte und keine Muster zeigt Dies könnte frühere verschlüsselte Daten mit folgenden verschlüsselten Daten in Beziehung setzen oder Klartextdaten mit verschlüsselten Daten in Beziehung setzen oder zwei verschiedene Chiffretexte miteinander in Beziehung setzen (so können Vermutungen über die Klartexte angestellt werden).

Kurzgeschichte:

Erzeugt einen zufälligen Startwert unter Verwendung der aktuellen Mikrosekunde des Systems.

Dieser Trick ist ziemlich alt und funktioniert immer noch.

Ausgenommen der Force-Brute-Faktor, bei dem ich jede Kombination durch "Setzen" aller möglichen Zahlen bestimmen kann und es nicht auf diese Frage ankommt, insbesondere wenn die meisten Zufallszahlen vor seiner Verwendung gerundet werden.

Angenommen, ich kann den verwendeten Startwert anhand von nur 10 Werten bestimmen. Wenn ich den Samen kenne, kann ich den nächsten Wert erraten.

Wenn ich den Startwert = 1 verwenden würde, könnte ich die nächste Sequenz erhalten:

1, 2, 3, 4, 5, 6, 7, 8, 9 ... (und ich ziehe ab, dass der Startwert id 1 und der nächste Wert 10 verwendet wurden)

Aber was passiert, wenn beim Senden alle "n-ten" Werte geändert werden? Das Ändern des Seeds um die aktuellen Mikrosekunden ist ein billiger Trick (das heißt, es sind nicht viele CPU-Zyklen erforderlich).

Die Reihenfolge lautet also jetzt: (seed = 1) 1, 2, 3, 4, 5, (seed = 2), 7, 9, 11, 13 ... (15?)

In diesem Fall:

a) Ich kann nicht abziehen, welches Saatgut verwendet wurde.

b) Ergo, ich kann den nächsten Wert nicht erraten.

c) Die einzige Vermutung, die ich machen kann, ist zu ziehen, dass der nächste Samen eine große Zahl sein könnte.

Wie auch immer, die meisten modernen Zufallsgenerator-Algorithmen verwenden diesen Trick bereits unter der Haube.

Die wahre Tatsache ist, dass wir keinen Quantencomputer benötigen, um eine "wahre" Zufallszahl zu erzeugen, die Ungenauigkeit unseres Quarzes wirkt wie ein Zufallsgenerator, auch die Zufallseffizienz unserer CPU ist ohne Berücksichtigung ebenfalls variabel dass die CPU in der Regel mehrere Aufgaben gleichzeitig erledigt.