Einige Leute sagten folgendes:

Wer versucht, mit deterministischen Mitteln Zufallszahlen zu generieren, lebt natürlich in einem Zustand der Sünde.

Das bedeutet immer, dass Sie mit nur einem Computer keine echten Zufallszahlen generieren können. Und er sagte, dass Computer die gleiche Größe hätten wie ein einzelner Intel 8080-Mikroprozessor (~ 6000 Ventile). Computer sind komplexer geworden, und ich glaube, dass von Von Neumanns Aussage möglicherweise nicht mehr wahr ist. Beachten Sie, dass ein implementierter Algorithmus nur für Software unmöglich ist. Sie laufen auf physischer Hardware. Echte Zufallszahlengeneratoren und ihre Entropiequellen bestehen ebenfalls aus Hardware.

Dieses Java-Fragment in einer Schleife:

      file.writeByte((byte) (System.nanoTime() & 0xff));

kann eine Datendatei erstellen, die ich als Bild dargestellt habe:

Sie können Struktur sehen, aber auch mit viel Zufälligkeit. Interessant ist, dass diese PNG-Datei eine Größe von 232 KB hat und dennoch 250.000 Graustufenpixel enthält. Die PNG-Komprimierungsstufe war maximal. Das ist nur eine Kompressionsrate von 7%, dh. ziemlich nicht komprimierbar. Interessant ist auch, dass die Datei eindeutig ist. Jede Generation dieser Datei ist ein etwas anderes Muster und weist eine ähnliche Komprimierbarkeit von ~ 7% auf. Ich hebe dies als kritisch für mein Argument hervor. Das sind ~ 7 Bit / Byte Entropie. Dies wird sich natürlich bei Verwendung eines stärkeren Kompressionsalgorithmus verringern. Aber nicht auf nahe 0 Bits / Byte reduzieren. Um einen besseren Eindruck zu erhalten, nehmen Sie das obige Bild und ersetzen Sie es durch eine zufällige Farbkarte:

Der größte Teil der Struktur (in der oberen Hälfte) verschwindet, da es sich nur um Sequenzen mit ähnlichen, aber geringfügig unterschiedlichen Werten handelt. Handelt es sich um eine echte Entropiequelle, die nur durch Ausführen eines Java-Programms auf einem Multi-Take-Betriebssystem erstellt wurde? Kein gleichmäßig verteilter Zufallsgenerator, sondern die Entropiequelle für einen? Eine Entropiequelle, die aus Software besteht, die auf physischer Hardware ausgeführt wird und zufällig nur ein PC ist.

Ergänzend

Um zu bestätigen, dass jedes Bild eine frische Entropie ohne ein allen gemeinsames festes Muster erzeugt, wurden 10 aufeinanderfolgende Bilder erzeugt. Diese wurden dann verkettet und mit dem stärksten Archivierungsprogramm komprimiert, das ich kompilieren kann (paq8px). Bei diesem Vorgang werden alle gängigen Daten entfernt, einschließlich der automatischen Korrelation, wobei nur die Änderungen / Entropie übrig bleiben.

Die verkettete Datei wurde auf ~ 66% komprimiert, was zu einer Entropierate von ~ 5,3 Bit / Byte oder 10,5 MBit / Bild führt. Eine überraschende Menge an Entropie$\smile$

Zusatz 2

Es gab negative Kommentare, dass meine Entropie durch die Kompressionstestmethode fehlerhaft ist und nur eine lose Schätzung der oberen Schranke ergibt. Daher habe ich jetzt die verkettete Datei im offiziellen NIST-Test zur Bewertung der kryptografischen Entropie, SP800-90B_EntropyAssessment , ausgeführt . Dies ist so gut wie bei einer Nicht-IID-Entropiemessung. Dies ist der Bericht (Entschuldigung, diese Frage wird lang, aber das Problem ist komplex):

Running non-IID tests...

Entropic statistic estimates:
Most Common Value Estimate = 7.88411
Collision Test Estimate = 6.44961
Markov Test Estimate = 5.61735
Compression Test Estimate = 6.65691
t-Tuple Test Estimate = 7.40114
Longest Reapeated Substring Test Estimate = 8.00305

Predictor estimates:
Multi Most Common in Window (MultiMCW) Test: 100% complete
    Correct: 3816
    P_avg (global): 0.00397508
    P_run (local): 0.00216675
Multi Most Common in Window (Multi MCW) Test = 7.9748
Lag 

Test: 100% complete
    Correct: 3974
    P_avg (global): 0.00413607
    P_run (local): 0.00216675
Lag Prediction Test = 7.91752
MultiMMC Test: 100% complete
    Correct: 3913
    P_avg (global): 0.00407383
    P_run (local): 0.00216675
Multi Markov Model with Counting (MultiMMC) Prediction Test = 7.9394
LZ78Y Test: 99% complete
    Correct: 3866
    P_avg (global): 0.00402593
    P_run (local): 0.00216675
LZ78Y Prediction Test = 7.95646
Min Entropy: 5.61735

Das Ergebnis ist, dass NIST glaubt, ich hätte 5,6 Bit / Byte Entropie erzeugt. Meine DIY-Komprimierungsschätzung geht von 5,3 Bit / Byte aus, etwas konservativer.

-> Der Beweis scheint die Vorstellung zu stützen, dass ein Computer, auf dem nur Software ausgeführt wird, echte Entropie erzeugen kann. Und das von Neumann war falsch (aber vielleicht richtig für seine Zeit).

Ich biete die folgenden Referenzen an, die meine Behauptung stützen könnten:

Gibt es stochastische Modelle des Nichtdeterminismus bei der Programmausführungsrate?

WCET-Analyse probabilistischer Echtzeitsysteme

Gibt es einen Softwarealgorithmus, der ein nicht deterministisches Chaosmuster erzeugen kann? und die Relevanz von chaotischen Effekten.

Parallelen zum Prinzip der quantentropischen Unsicherheit

Aleksey Shipilёvs Blogeintrag zum chaotischen Verhalten von nanoTime (). Sein Streudiagramm ist meinem nicht unähnlich.

Nur weil Sie ein Muster nicht sehen können, heißt das noch lange nicht, dass es kein Muster gibt. Nur weil ein Komprimierungsalgorithmus kein Muster finden kann, heißt das noch lange nicht, dass kein Muster existiert. Kompressionsalgorithmen sind keine Wundermittel, mit denen die wahre Entropie einer Quelle auf magische Weise gemessen werden kann. Alles, was sie dir geben, ist eine Obergrenze für den Entropiebetrag. (Ebenso gibt Ihnen der NIST-Test nur eine Obergrenze.) Chaos ist keine Zufälligkeit.

Es bedarf einer genaueren Analyse und Untersuchung, um ein gewisses Vertrauen in die auf diese Weise erhaltene Qualität der Zufälligkeit zu gewinnen.

Es gibt Gründe zu der Annahme, dass wir durch Ausnutzen des Taktjitters und der Abweichung zwischen zwei Hardware-Taktgebern wahrscheinlich ein gewisses Maß an Zufälligkeit erzielen können , aber dies ist heikel und knifflig, sodass Sie vorsichtig sein müssen. Ich würde nicht empfehlen, zu versuchen, Ihre eigenen zu implementieren. Stattdessen würde ich vorschlagen, dass Sie eine hochwertige Entropiequelle verwenden (normalerweise implementiert in den meisten modernen Betriebssystemen). Weitere Informationen finden Sie auch in Wikipedia , haveged und /crypto//q/48302/351 (was Ihnen anscheinend bereits bekannt ist).

Zum Schluss noch ein Kommentar zu Ihrem Opener:

"Wer versucht, mit deterministischen Mitteln Zufallszahlen zu generieren, lebt natürlich in einem Zustand der Sünde."

Das bedeutet immer, dass Sie mit nur einem Computer keine echten Zufallszahlen generieren können.

Nein, so wird es normalerweise nicht genommen, und es ist nicht das, was es sagt. Es heißt, man kann mit deterministischen Mitteln keine echten Zufallszahlen erzeugen . Ob Sie dies auf einem Computer tun können, hängt davon ab, ob der Computer deterministisch ist oder nicht. Wenn der Computer deterministisch ist oder Ihr Programm nur deterministische Operationen verwendet, ist dies nicht möglich. Viele Computer enthalten jedoch nicht deterministische Elemente. Wenn Ihr Programm diese verwendet, ist eine detailliertere Analyse erforderlich, bevor Sie entscheiden können, ob sie zum Generieren von Zufallszahlen verwendet werden können. In Ihrem Fall nanoTime()ist nicht deterministisch.

Wenn Sie eine Hardwarequelle für Entropie / Zufälligkeit verwenden, "versuchen Sie nicht, Zufälligkeit mit deterministischen Mitteln zu erzeugen " (mein Schwerpunkt). Wenn Sie keine Hardwarequelle für Entropie / Zufälligkeit verwenden, bedeutet ein leistungsfähigerer Computer lediglich, dass Sie mehr Sünden pro Sekunde begehen können.

Ich habe das Zitat immer so verstanden, dass ein deterministischer Algorithmus einen festen Entropiebetrag hat, und obwohl die Ausgabe "zufällig" erscheinen kann, kann sie nicht mehr Entropie enthalten, als die Eingaben liefern. Aus dieser Perspektive sehen wir, dass Ihr Algorithmus über Entropie schmuggelt System.nanoTime()- die meisten Definitionen eines "deterministischen" Algorithmus würden es nicht erlauben, diese Funktion aufzurufen.

Das Zitat - wenn auch markig - ist im Wesentlichen eine Tautologie. Es gibt nichts zu widerlegen, und es ist keine Weiterentwicklung der Hardware möglich, die dies unmöglich macht. Es geht nicht um Hardware, sondern um die Definition eines deterministischen Algorithmus. Er stellt lediglich fest, dass Determinismus und Zufälligkeit unvereinbar sind. Für jeden deterministischen Algorithmus wird sein gesamtes Verhalten durch seine Startbedingungen vorhergesagt. Wenn Sie glauben, eine Ausnahme gefunden zu haben, verstehen Sie falsch, was es bedeutet, deterministisch zu sein.

Es ist richtig, dass ein Prozess, der auf einem gemeinsam genutzten Computer mit einer komplexen Reihe von Caches ausgeführt wird und der verschiedene Netzwerk- und Hardwareeingaben empfängt, auf viel mehr Entropie zugreifen kann als ein Prozess, der auf einfacher, isolierter, dedizierter Hardware ausgeführt wird. Wenn dieser Prozess jedoch auf diese Entropie zugreift, ist er nicht mehr deterministisch, und das Zitat gilt nicht mehr.

Wer versucht, mit deterministischen Mitteln Zufallszahlen zu generieren, lebt natürlich in einem Zustand der Sünde.

Wenn man "in einem Zustand der Sünde leben" als "Unsinn machen" interpretiert, dann ist das vollkommen richtig.

Was Sie getan haben, ist eine ziemlich langsame Methode System.nanoTime(), um eine ziemlich schwache Zufälligkeit zu erzeugen. Sie haben einige gemessen

... Entropierate von ~ 5,3 Bit / Byte ...

aber das ist nur die obere Schranke. Alles, was Sie jemals bekommen können, ist eine Obergrenze. Die reale Entropie kann um Größenordnungen kleiner sein.

Füllen Sie das Array stattdessen mit einem kryptografischen Hash wie MD5. Berechnen Sie eine Sequenz wie md5(0), md5(1), ...(aus jedem Wert, der ein oder mehrere Bytes enthält, spielt dies keine Rolle). Sie erhalten überhaupt keine Komprimierung (ja, MD5 ist defekt, aber immer noch gut genug, um inkomprimierbare Daten zu erzeugen).

Wir können sagen, dass es überhaupt keine Entropie gibt, aber Sie würden 8 Bits / Byte messen.

Wenn Sie wirklich etwas Zufälliges benötigen, müssen Sie nicht nur eine HW-Quelle verwenden, sondern auch eine sichere Untergrenze für die tatsächliche Entropie kennen. Obwohl höchstwahrscheinlich eine gewisse Zufälligkeit nanoTime()vorliegt, sind mir keine nicht trivialen unteren Grenzen bekannt.

Wenn Sie Zufälligkeit für die Kryptografie benötigen, müssen Sie wirklich auf etwas zurückgreifen, das von Ihrem Betriebssystem, Ihrer Sprache oder einer guten Bibliothek bereitgestellt wird. Solche Anbieter sammeln Entropie aus mehreren Quellen und / oder dedizierter Hardware, und es wurde eine ganze Menge Arbeit in solche Entropieschätzungen gesteckt.

Beachten Sie, dass Sie in der Regel kaum Entropie benötigen. Ein guter (deterministischer) PRNG, der mit einigen zufälligen Bytes initialisiert wurde, ist für die Kryptographie und damit auch für alles andere verwendbar.

Ich dachte, ich würde mich auf die Bedeutung von "zufällig" einlassen. Die meisten Antworten beziehen sich auf die Ausgabe zufälliger Prozesse im Vergleich zur Ausgabe deterministischer Prozesse. Das ist eine sehr gute Bedeutung von "zufällig", aber es ist nicht die einzige.

Ein Problem bei der Ausgabe von zufälligen Prozessen besteht darin, dass sie sich nur schwer von der Ausgabe von deterministischen Prozessen unterscheiden lassen: Sie enthalten keine "Aufzeichnung" darüber, wie zufällig ihre Quelle war. Ein extremes Beispiel hierfür ist ein berühmter XKCD-Comic, bei dem ein Zufallszahlengenerator immer zurückkehrt 4und ein Codekommentar angibt , dass er zufällig ist, weil er von einem Würfel stammt.

Ein alternativer Ansatz zur Definition von "Zufälligkeit", genannt Kolmogorov-Komplexität , basiert auf den Daten selbst, unabhängig davon, wie sie generiert wurden. Die Kolmogorov-Komplexität einiger Daten (z. B. eine Folge von Zahlen) ist die Länge des kürzesten Computerprogramms, das diese Daten ausgibt: Daten sind "zufälliger", wenn sie eine höhere Kolmogorov-Komplexität aufweisen.

Ihre Verwendung von Komprimierungsalgorithmen wie PNG und der Vergleich der Länge vor und nach der Komprimierung ähnelt der Idee der Kolmogorov-Komplexität. Aufgrund der Komplexität von Kolmogorov können Daten jedoch als Programm in einer beliebigen Programmiersprache von Turing-complete codiert werden, anstatt in einem eingeschränkten Format wie PNG. Das "Dekomprimieren" solcher Codierungen (Programme) erfolgt durch Ausführen, was beliebig viel Zeit und Speicher in Anspruch nehmen kann (z. B. mehr als in unserem dürftigen Universum verfügbar ist).

Das Theorem von Rice besagt, dass wir im Allgemeinen nicht zwischen Programmen, die sich für immer wiederholen, und Programmen, die unsere Daten ausgeben, unterscheiden können. Daher ist es sehr schwierig, die Kolmogorov-Komplexität einiger Daten zu ermitteln: Wenn wir ein Programm aufschreiben, das diese Daten generiert, gibt es möglicherweise ein kürzeres Programm (dh eine geringere Komplexität), aber wir haben es nicht erkannt, weil wir es nicht konnten Unterscheide es von einer Endlosschleife. Die Kolmogorov-Komplexität ist daher nicht berechenbar. Wenn wir die Busy-Beaver-Zahlen kennen, können wir sie berechnen, indem wir diese verwenden, um die Zeitspanne zu begrenzen, die wir für jedes Programm prüfen.

Um die Kolmogorov-Komplexität (dh die "intrinsische Zufälligkeit") Ihrer Beispieldaten zu ermitteln, müssen Sie das kürzeste deterministische Programm finden, das dieselbe Bytefolge ausgibt, und dessen Länge bestimmen.

Jetzt können wir Ihre Frage aus Sicht der Kolmogorov-Komplexität beantworten und stellen fest, dass das Zitat richtig ist: Wir können keine Zufallszahlen (hohe Kolmogorov-Komplexität) mit deterministischen Mitteln erzeugen.

Warum nicht? Stellen wir uns vor, wir schreiben ein kleines Computerprogramm und erzeugen daraus eine Folge von Zufallszahlen. Eine der folgenden Situationen muss zutreffen:

• Wir erzeugen eine enorme Menge an Output. Da wir jedoch wissen, dass diese Ausgabe von einem kleinen Programm generiert wird, hat die Ausgabe (per Definition) eine geringe Kolmogorov-Komplexität und ist daher in diesem Sinne nicht "zufällig".
• Wir generieren so wenige Zahlen, dass das Aufschreiben derselben oder sogar weniger Bits dauern würde, als das Aufschreiben unseres kurzen Generierungsprogramms. In diesem Fall sind die Zahlen relativ inkompressibel, was darauf hinweist, dass sie im Sinne von Kolmogorov ziemlich zufällig sind. Da die Ausgabemenge jedoch mit der von uns eingegebenen Menge (dem Quellcode für das Programm) vergleichbar ist, kann man mit Recht sagen, dass das Programm nicht die Zufälligkeit "erzeugt" hat, sondern dass wir dieses Programm ausgewählt haben. In diesem Fall könnte unser Erzeugungsprogramm auch nur eine Liste dieser exakten Zahlen (z print([...]). B. ) gewesen sein.

In beiden Fällen "generieren" wir nicht mehr Zufälligkeit als wir eingeben (die "Zufälligkeit" des Quellcodes unseres generierenden Programms). Wir könnten versuchen, dies mit einem längeren Generierungsprogramm zu umgehen, um zu vermeiden, dass die Ausgabe einen kurzen Generator enthält. Es gibt jedoch nur zwei Möglichkeiten, dies zu tun:

• Systematisch den Code auf irgendeine Weise "aufblähen". Die Komplexität von Kolmogorov kümmert sich jedoch nicht um das bestimmte Programm, mit dem wir die Daten generiert haben. Es geht nur darum, welches generierende Programm das kleinste ist. Durch systematisches Aufblähen wird die Komplexität von Kolmogorov nicht erhöht, da solche Muster im Code selbst mit einer sehr geringen Codemenge generiert werden können. Wenn wir zum Beispiel run(shortGenerator)eine ganze Ladung systematisches Aufblähen nehmen und hinzufügen, um zu erhalten run(bloatedGenerator), existiert immer noch ein kurzer Generator der Form run(addBloat(shortGenerator)).
• Fügen Sie bloat nicht systematisch , dh ohne Muster, hinzu, sodass eine addBloatFunktion genauso aufgebläht sein müsste wie der Code selbst. Es ist jedoch genau das, was etwas zufällig macht, wenn es so frei von Mustern ist (hohe Kolmogorov-Komplexität). Daher Blähungen das Erzeugungsprogramm auf diese Weise ist die Zufälligkeit (Kolmogorov Komplexität) der Ausgabe zu erhöhen, sondern es auch erhöht die Menge an Zufälligkeit (Kolmogorov Komplexität) , dass wir in Form von Quellcode zur Verfügung stellen müssen. Daher sind es immer noch wir, die die "Zufälligkeit" und nicht das Programm bereitstellen. Im obigen Beispiel des einfachen Schreibens entspricht das print([...])Hinzufügen von nicht systematischem Aufblähen dem einfachen Schreiben von mehr "Zufallszahlen" in diese fest codierte Liste.

Komprimierung ist kein genauer Test der Zufälligkeit, und es wird auch kein Bild betrachtet, in dem "das sieht zufällig aus" steht.

Die Zufälligkeit wird durch empirische Methoden getestet . Tatsächlich gibt es eine Reihe speziell entwickelter Software / Algorithmen zum Testen der Zufälligkeit, beispielsweise TestU01 und Diehard-Tests .

Darüber hinaus ist Ihr Bild eine 1D-Folge von Zahlen, die auf ein Leerzeichen abgebildet sind, und ist daher keine gute Darstellung bestimmter Muster, die auftreten können.

Wenn Sie Ihr Bild Pixel für Pixel untersuchen würden, würden Sie höchstwahrscheinlich viele kurze Muster mit zunehmendem Wert vor einem plötzlichen Abfall finden. Wenn Sie ein Diagramm mit dem x-Wert als Probennummer und dem y-Wert als Wert der Zufallsfunktion erstellen würden, würden Sie höchstwahrscheinlich feststellen, dass Ihre Daten tatsächlich wie eine Sägezahnwelle aussehen:

Dies ist das Muster, das durch Werte gebildet wird, die unter modularer Arithmetik zunehmen (wofür Ihre Berechnung ein Beispiel ist: zeitliche Zunahme mit nahezu konstanter Rate und & 0xFFHandeln als mod 256).

Sie verwechseln das Konzept von Zufallszahlen mit "Zahlen, die zufällig erscheinen".

Um von Neumanns Zitat zu verstehen, müssen wir verstehen, was es bedeutet, "Zufallszahlen zu generieren". Die Antwort von Warbo verknüpft eine hervorragende XKCD mit diesem Ziel:

Wenn wir über Zufallszahlen sprechen, sprechen wir nicht über die Werte selbst. Offensichtlich ist eine 4 nicht zufälliger als eine 3. Wir sprechen von der Fähigkeit eines Dritten, diesen Wert besser vorherzusagen als eine zufällige Chance. Eine Zufallszahl ist eine, die nicht vorhersehbar ist. Manchmal fügen wir dem Bedingungen hinzu. Ein kryptografisch sicherer Pseudozufallszahlengenerator (CSPRNG) generiert Zahlen, die nur zufällig vorhergesagt werden können, wenn ein Angreifer den Startwert / Schlüssel nicht kennt. Es wird normalerweise als eine Zahl definiert, die nicht vorhersehbar ist, selbst wenn das System einschließlich aller Schlüssel vollständig bekannt ist.

Nun ist Ihr Beispiel, wie viele darauf hingewiesen haben, nicht deterministisch. Das Programm gibt nicht an, aus welchem ​​Wert der Wert stammt System.nanoTime(). Daher gehört es nicht zur selben Klasse wie die Verwendung eines CSPRNG zur Erzeugung von Pseudozufallszahlen. Ersteres kann nicht deterministisch sein, während Letzteres deterministisch ist, wenn der Wert des Schlüssels deterministisch ist. Ersteres enthält Operationen, für die keine deterministischen Werte definiert sind.

Sie werden jedoch feststellen, dass ich sagte, dass es möglicherweise nicht deterministisch ist. Beachten Sie, dass System.nanoTime()keine Werte für diesen Zweck bereitgestellt werden sollen. Es kann nicht deterministisch genug sein oder auch nicht. Eine Anwendung passt die Systemuhr möglicherweise so an, dass die Aufrufe an System.nanoTime()alle mit einem Vielfachen von 256 Nanosekunden (oder in der Nähe) erfolgen. Möglicherweise arbeiten Sie auch in Javascript, wo die jüngsten Exploits von Spectre dazu geführt haben, dass große Browser die Auflösung ihrer Timer absichtlich verringern. In diesen Fällen können Ihre "Zufallszahlen" in Umgebungen, die Sie nicht geplant haben, sehr gut vorhersehbar sein.

• Also Zufallszahlen mit deterministischen Prozessen erzeugen ... sin.
• Zufallszahlen mit dedizierter Zufallshardware generieren ... keine Sünde.
• Zufallszahlen mit nichtdeterministischen Aspekten von Computern generieren ... vielleicht Sünde.

Es hängt alles davon ab, was Sie vorhaben. Wenn Sie Ihre Liebesbriefe an Sponge Bob verschlüsseln, damit Ihre Schwester sie nicht lesen kann, sind die Anforderungen an Ihre sogenannten Zufallszahlen ziemlich gering. System.nanoTime()benutzt wie du es getan hast ist wahrscheinlich gut genug. Wenn Sie nukleare Geheimnisse vor einem fortgeschrittenen ausländischen Staat schützen, der sie aktiv sucht, sollten Sie die Verwendung von Hardware in Betracht ziehen, die für diese Herausforderung ausgelegt ist.

Ich glaube nicht, dass Sie die Behauptung verstanden haben. Der Punkt ist, dass, wenn es ein deterministisches Verfahren zum Erzeugen einer 'Zufalls'-Zahlenreihe (oder irgendetwas wirklich) gibt, das Finden des Musters nur die Aufgabe ist, dieses Verfahren zu finden!

Daher gibt es immer eine deterministische Methode, um die nächste ganze Zahl vorherzusagen. Genau das erwarten wir nicht, wenn wir von Zufälligkeit ausgehen!

Jede hinreichend komplexe Deterministik ist von Stochastizität nicht zu unterscheiden.

--Von Wrzlprmfts Benutzerseite

Also, selbst wenn etwas zufällig aussieht , warum um alles in der Welt würden wir es als "zufällig" modellieren, wenn wir ein deterministisches Verfahren haben, um es zu erzeugen?

Dies ist meines Erachtens das Hauptproblem. Sie haben nur eine Form der Ununterscheidbarkeit des PRNG und "echte Zufälligkeit" gezeigt.

Es folgt jedoch nicht, dass diese Konzepte gleich sind. Insbesondere ist Zufälligkeit ein mathematisch- theoretisches Konzept. Wir haben oben bereits gezeigt, dass es theoretisch zu einem Widerspruch kommt, wenn man PRNG als „echte Zufälligkeit“ betrachtet. Daher können sie nicht gleich sein.

Ich denke, dass andere bereits darauf hingewiesen haben, aber es wurde nicht so betont, also lassen Sie mich auch auf die Diskussion eingehen.

Wie bereits erwähnt, geht es um die Messung der Entropie. Komprimierungsalgorithmen können Ihnen etwas mitteilen, sind jedoch quellenunabhängig. Da Sie mehr darüber wissen, wie die Daten generiert wurden, könnten Sie wahrscheinlich einen viel besseren Algorithmus zum Komprimieren der Daten entwickeln , was bedeutet, dass die wahre Entropie viel geringer ist.

Außerdem verwechseln Sie die Bedeutungen der Phrasen "am Computer" und "deterministisch". Sie können auf jeden Fall nicht deterministische Operationen auf dem Computer ausführen .

Außerdem haben Sie es gerade getan , aber das ist auf den ersten Blick nicht so offensichtlich.

Ein typischer deterministischer Algorithmus für eine Zufallszahlengenerierung ist z. PRNG wie linearer Kongruenzgenerator. Sie sind staatlich. Innerer Zustand bedeutet weniger Entropie, da der nächste Zustand durch den vorherigen bestimmt wird. Darauf werde ich nicht näher eingehen, das ist Ihnen wahrscheinlich klar. Ein wichtiger Punkt ist, dass ein vollständig deterministischer Algorithmus nur vom vorherigen Zustand abhängt, was auch immer er sein mag.

Schauen Sie sich jetzt Ihren Algorithmus an. Worauf basiert es? Wie viel Staat hast du? Ist es deterministisch?

  file.writeByte((byte) (System.nanoTime() & 0xff));

Lassen Sie uns file.writedie Probleme mit dem Leeren von Puffern und dem Warten auf E / A ignorieren (haben Sie für einen Moment versucht, den Festplattenkabeln starke Geräusche zuzufügen? Nein? Hey, Sie könnten das tun. Hey, es ist dann nicht deterministisch! :)) und Konzentrieren wir uns auf die Quelle, es ist wichtiger.

Die Zeit ist eine Art Staat. Es ist unterschiedlich, aber das meiste davon ist das gleiche. Aus diesem Grund haben Sie versucht, es zu umgehen, und & 0xFF verwendet, um den größten Teil des Status zu löschen . Aber Sie haben noch nicht alles gelöscht. Ein Teil des vorherigen Lesevorgangs kann bis zum nächsten auslaufen. Es ist also sicherlich nicht vollständig nicht deterministisch. *)

Das interessiert uns aber nicht. Um zu "beweisen", dass das Zitat falsch ist:

Wer versucht, mit deterministischen Mitteln Zufallszahlen zu generieren, lebt natürlich in einem Zustand der Sünde.

Sie müssen es mit deterministischen Mitteln beweisen.
Was uns interessiert, ist: Ist Ihr Algo sicher voll deterministisch ?

..und es ist offensichtlich, dass es nicht ist.

  System.nanoTime() & 0xff

Das ist eine Zeitmessung. Zeit und Messung . Das Maßteil kann es deterministisch machen, wenn der Wert zwischengespeichert wird. Ich nehme an es ist nicht, sonst hätte diese Funktion keinen Sinn. Wenn es dann direkt aus der Quelle gelesen wird, haben wir einen zeitbasierten Wert. Da ( ich nehme wieder an ) Sie dies nicht auf einer dedizierten Hardware für einzelne Tasks ausgeführt haben, kann es vorkommen , dass Sie gelegentlich eine Kontextumschaltung durchführen. Selbst wenn Sie eine dedizierte Hardware für einzelne Aufgaben hatten, ist die Zeitmessung möglicherweise immer noch nicht deterministisch, da Temperatur- / Feuchtigkeitsverschiebungen in der Zeitquelle, Bus-Taktzeiten usw. auftreten.

Ich stimme vollkommen zu, dass ich hier übertreibe. Drifts werden nicht so groß sein, um viel Einfluss zu haben (obwohl nanotimesie real sein könnten). Noch wichtiger nanotimeist, soll schnell sein. Es liest nicht aus der Echtzeitquelle. Es basiert auf dem inneren Befehl / der Zykluszahl des Prozessors. Das ist eigentlich deterministisch, wenn Sie keine Kontextwechsel sicherstellen.

Mein Punkt ist, dass es tatsächlich sehr schwierig sein kann, einen wirklich 100% deterministischen Algorithmus auszuführen, wenn Sie ihn auf die Zeit stützen und Sie kein Recht haben, dieses Zitat zu widerlegen, es sei denn, Sie verfügen über vollständig deterministische Mittel.

*) Interessanterweise könnten Sie wahrscheinlich die tatsächliche Zufälligkeit erhöhen, wenn Sie den Hardcore-Weg gehen. Führen Sie & 0x01 nach und nach aus, und warten Sie eine beachtliche Zeit, bevor Sie die einzelnen Bits lesen. Das Generieren von Daten auf diese Weise wäre lächerlich lang, aber ich würde tatsächlich argumentieren, dass dies als nahezu zufällig angesehen werden könnte. IIF, das Sie auf Nicht-RTOS- und IFF-Systemen ausführen, ist in jeder "wahrnehmbaren Zeit" hoch genug, um sicherzustellen, dass der zugrunde liegende Wert erreicht wird Das Betriebssystem ging entweder in den Ruhezustand oder wechselte kontextbezogen zu einer anderen Aufgabe.

Ich denke, die Antwort, die Sie brauchen, beginnt mit diesem Kommentar, den Sie selbst als Antwort auf eine andere Antwort abgegeben haben:

Das Muster ist ein Ergebnis des Zusammenspiels von Java, JVM, Betriebssystem, CPU + Caches, Festplatte, der Trance-Musik, die ich gestreamt habe und die CPU / RAM-Zyklen und alles dazwischen verbraucht. Das Muster entsteht einfach aus der einen Zeile Java-Code in einer for / next-Schleife. Ein wesentlicher Teil der Entropie kommt von den zugrunde liegenden Hardwareschaltungen.

Ich denke, Sie haben das bereits erkannt: Sie haben keine deterministischen Mittel verwendet, um das Muster zu erstellen.

Sie haben einen Computer verwendet, von dem ein nicht zu vernachlässigender Teil deterministisch ist, aber die Entropie kam von externen nicht deterministischen (oder zumindest nicht deterministischen) Quellen: Sie oder die Außenwelt, die interagieren mit dem Computer (und in geringerem Maße mit physischen Fehlern in der Computerhardware, die die zeitlichen Abläufe der Dinge beeinflussen könnten).

Dies ist übrigens ein großer Teil der Art und Weise, wie moderne Betriebssysteme ihre Zufallszahlengeneratoren einsetzen, die Programmen zur Verfügung stehen: indem sie die Entropie in Wechselwirkungen mit ihrer Hardware und dem Benutzer nutzen, von dem wir hoffen, dass sie für einen Angreifer nicht vorhersehbar sind.

Übrigens ist die Entropie der Außenwelt tatsächlich ein Problem, mit dem sich die sonst gut codierte Kryptographie bis heute befassen muss: Computer mit vorhersagbarem VerhaltenB. solche mit Nur-Lese-Speicher oder solche, die über das Netzwerk gestartet werden und deren Netzwerkumgebung vorhersehbar ist (entweder nicht mit einem Netzwerk verbunden oder die Arbeitslast im Netzwerk ist so gering, dass alles innerhalb des Netzwerks bereitgestellt wird) Eine verlässliche Zeitspanne), auf der dieselbe begrenzte Menge von Software mit ungefähr gleichbleibendem Verhalten ausgeführt wird, könnte die Entropie, die sie von diesen als unvorhersehbar angenommenen Komponenten erhalten, grob überschätzen und am Ende weitaus vorhersehbarere Zahlen erzeugen als würden Sie auf einem typischen Arbeitsplatz sitzen, der alle möglichen anderen Dinge für Sie erledigt (Musik streamen, mit Dropbox synchronisieren, was auch immer) im Hintergrund.

Ich denke, die meisten Antworten konzentrieren sich darauf, ob das Überprüfen der letzten acht Bits von Zeitmessungen in Nanosekunden, die in einer Schleife aufgenommen wurden, eine gute Möglichkeit ist, diese Entropie zu gewinnen. Dies ist eine sehr wichtige Frage, die Sie richtig beantworten müssen, bevor Sie die Methode in Ihrem Beispiel als Zufallszahlengenerierungsschema in der Praxis verwenden , aber es ist eine andere Frage als die, nach der Sie meiner Meinung nach fragen.

Um die vorherigen Antworten zu ergänzen, haben Sie hier eine einfache Möglichkeit, über diese Frage nachzudenken.

Es geht um den Unterschied zwischen zufällig und deterministisch . Wir kommen zu Von Neumann und was er danach gesagt hat.

Zufällige Zahlen

Ein echter Zufallszahlengenerator hätte kein Muster, das nicht einmal im Hintergrund verborgen wäre. Mit diesem Muster könnten wir die nächste Zahl vorhersagen, die der Sequenz bisher gegeben ist. In einer idealen Welt könnte man alles wissen, was es im physikalischen Universum zu wissen gibt, und über das System, Nanosekunden für Nanosekunden, und es wäre immer noch nutzlos, die nächste produzierte Zahl vorherzusagen.

Das ist ein idealer Fall - in der Praxis erreichen wir dies, indem wir viele Quellen zusammenmischen, die "keine schlechten Annäherungen" an den Zufall darstellen oder wirklich zufällig sind, oder die die Dinge mathematisch so weit vertauschen, dass Sie mathematisch nachweisen können, dass sie sehr nahe an unvorhersehbar und unvorhersehbar kommen mangelnde Neigung zu bestimmten Zahlen oder Mustern.

• "Gute" Quellen sind Dinge, die dem Warten auf einen radioaktiven Zerfallsprozess oder einen anderen Quantenprozess ähneln, der von Natur aus unvorhersehbar ist. Ausgang von einem wärmeempfindlichen Halbleiter. Zufälliges Rauschen in einer Diode oder einem anderen elektrischen Material. Photonenzählung von der Sonne.

• In diesem Zusammenhang können wir auch einige hinzufügen, die wir als "nicht schlecht" betrachten, was hilfreich ist, da sie keine Verbindung zu diesen Elementen haben: Warten auf den nächsten Mausklick oder das nächste Netzwerkpaket. Letzte Mikrotime beim nächsten Schreiben der Datei. Ausgabe einer "bekannten aber mathematisch ziemlich zufälligen" Pseudozufallszahlengeneratorfunktion. Vorherige Entropie aus früheren Verwendungen von Zufallszahlen.

Das Ziel hierbei ist es, eine Zahl zu erhalten , die unabhängig von dem Universum, das Sie kennen , immer noch nicht vorhergesagt werden kann und die statistisch genauso wahrscheinlich ist wie diese Zahl , ohne mathematisch erkennbares Muster, Verzerrung oder Vorhersagbarkeit und ohne Korrelation zu einem Ereignis, das dies ist überwacht und zur Vorhersage herangezogen werden. (Oder wenn dies mit einem Ereignis korreliert ist, erfolgt dies auf eine Weise, die die Verbindung unglaublich labil macht, z. B. "Nanosekunden-Ziffer nur der Zeit des letzten Mausklicks")

Deterministische Zahlen

Mathematiker können Dinge über Formeln und Funktionen beweisen. So ist es möglich zu beweisen, dass eine Funktion, wenn sie wiederholt aufgerufen wird, keinem Muster eine Vorliebe gibt, außer dem einfachen Muster "Dies sind die Ausgaben dieser Funktion, wenn sie wiederholt aufgerufen wird".

Wenn Sie beispielsweise eine Zahl zwischen 1 und 10 Millionen auswählen, diese binär schreiben und sie wiederholt "haschen", erhalten Sie eine ziemlich zufällig aussehende Folge von Ziffern. Es ist fast zufällig - aber es ist überhaupt nicht zufällig. Sie können anhand des Algorithmus und eines beliebigen Zustands vorhersagen, wie die nächste Zahl aussehen wird.

Wir nennen es "Pseudozufall", weil es hauptsächlich zufällig aussieht und zu sein scheint, auch wenn es nicht so ist.

Hier ist ein gutes Beispiel. Denken Sie an diese dreistellige Folge von "Zufallszahlen": 983, 367, 336, 244, 065, 664, 308, 602, 139, 494, 639, 522, 473, 719, 070, 217. Sagen wir, dass ich es Ihnen sage Ich kann auf die gleiche Weise eine Million Zahlen erzeugen. Sie können dann an einen Statistiker weitergeben, der bestätigt (sagt), dass er gleichmäßig verteilt ist oder wie auch immer. Es gibt kein offensichtliches vorhersehbares Muster. Sie sehen ziemlich zufällig aus, oder? Aber jetzt sage ich Ihnen, dass sie tatsächlich sind

die 500. + Ziffer von Pi, gruppiert in 3s.

Plötzlich jedoch zufällig die

Ziffern von Pi

Vielleicht können Sie sofort vorhersagen, dass die nächsten 2 Zahlen 986 und 094 sein werden.

Um klar zu sein, ich weiß nicht genau, wie zufällig das ist

Ziffern von Pi

sind. Es wird untersucht und die Antwort bekannt sein. Der springende Punkt ist jedoch: Grundsätzlich gilt das Gleiche für jede Quelle, die nach einem deterministischen Prozess hergestellt wird .

Zwischen

Dazwischen gibt es eine ganze Reihe von "Dingen, die zufällig aussehen und oft bis zu einem gewissen Grad zufällig sind". Je mehr Zufälligkeit und nahezu Zufälligkeit man einmischen kann, desto weniger neigt die Ausgabe dazu, ein Muster zu erkennen oder eine Ausgabe mathematisch vorherzusagen.

Zurück zu von Neumann und Ihrer Frage

Wie Sie sehen, sehen deterministische Ausgaben möglicherweise zufällig aus, sind statistisch jedoch möglicherweise sogar zufällig verteilt. Sie könnten sogar "geheime" oder sich schnell ändernde Daten verwenden, von denen wir keine realistische Hoffnung haben, dass sie es wissen. Aber solange es deterministisch ist, können die Zahlen niemals wirklich zufällig sein . Sie können nur "so nahe am Zufall sein, dass wir den Unterschied gerne vergessen".

Das ist die Bedeutung des Zitats, das Sie gegeben haben. Ein deterministischer Prozess kann einfach keine Zufallszahlen liefern. Es können nur Zahlen angegeben werden, die scheinbar zufällige Zahlen sind und sich auch so verhalten.

Wir können Ihre Frage jetzt folgendermaßen umformulieren: "Die Ausgabe meines (oder eines modernen) Computers kann völlig zufällig aussehen und sich völlig verhalten. Bedeutet das, dass von Neumanns Zitat jetzt veraltet und falsch ist?"

Das Problem ist immer noch das Folgende: Auch wenn die Ausgabe Ihres Computers zufällig aussieht und sich verhält, ist sie möglicherweise nicht wirklich zufällig . Wenn es nur deterministisch berechnet wird, bedeutet das, dass es nichts gibt, was nicht vorhersehbar ist, was Ursache und Wirkung sind, um die nächste Zahl zu ermitteln (das ist, was "deterministisch" in diesem Sinne bedeutet). Wir beginnen mit einigen vorhandenen Daten (bekannt), wenden einen bekannten Prozess an (komplex oder chaotisch oder was auch immer) und erhalten eine scheinbar neue "Zufallszahl". Aber es ist nicht zufällig, weil der Prozess deterministisch war.

Wenn Sie sagen, dass Ihre Methode einen echten Hardware-Zufallsgenerator enthält, um dies zu beheben (wie eine Zufallszahl, die durch radioaktiven Zerfall oder Rauschen in einem Halbleiter erzeugt wird), könnte Ihre Antwort jetzt zufällig sein - aber Ihre Methode ist per Definition nicht mehr deterministisch , gerade weil man die Outputs (oder Effekte) aufgrund der Inputs / Initialdaten (Ursachen) nicht mehr vorhersagen kann .

Von Neumann gewinnt per Definition in beide Richtungen!