Alternative Entropie Quellen

Question

Okay, ich denke, das ist völlig subjektiv und nicht, aber ich habe über Entropiequellen für Zufallszahlengeneratoren nachgedacht. Es geht darum, dass die meisten Generatoren mit der aktuellen Zeit ausgesät werden, richtig? Nun, ich war neugierig, was andere Quellen verwendet werden könnten durchaus gültig, zufällig (Die lose Definition) Zahlen zu erzeugen.

Würde die Verwendung mehrerer Quellen (wie Zeit + aktuelle HDD-Suchzeit [wir sind hier phantastisch]) zusammen eine "zufällige" Zahl als eine einzelne Quelle erstellen? Was sind die logischen Grenzen der Anzahl der Quellen? Wie viel ist wirklich genug? Wird die Zeit einfach gewählt, weil es bequem ist?

Entschuldigung, wenn so etwas nicht erlaubt ist, aber ich bin neugierig auf die Theorie hinter den Quellen.

Answer 1

Der Wikipedia-Artikel über Hardware random number generator's Listen ein paar interessante Quellen für Zufallszahlen unter Verwendung von physikalischen Eigenschaften.

Meine Favoriten:

• A von einem Geigerzähler erfasst Kernzerfälle Strahlungsquelle an einen PC angeschlossen.
• Photonen durch einen halbdurchlässigen Spiegel reisen. Die sich gegenseitig ausschließende Ereignisse (reflection - Übertragung) werden erkannt und zugeordnet zu „0“ oder „1“ Bit-Werte sind.
• Thermisches Rauschen aus einem Widerstand, eine Zufallsspannungsquelle bereitzustellen verstärkt.
• Lawinenrauschen erzeugt aus einer Lawinendiode. (Wie cool ist das?)
• Atmospheric Lärm von einem Funkempfänger erkannt an einen PC angeschlossen

Die problems section der Wikipedia-Artikel auch die Zerbrechlichkeit viele dieser Quellen/Sensoren beschreibt. Sensoren produzieren fast immer abnehmende Zufallszahlen, wenn sie altern/degradieren. Diese physikalischen Quellen sollten ständig durch statistische Tests überprüft werden, die die erzeugten Daten analysieren können, um sicherzustellen, dass die Instrumente nicht lautlos gebrochen sind.

Answer 2

Mach dir keine Sorgen über einen "guten" Startwert für einen Zufallsgenerator. Die statistischen Eigenschaften der Sequenz hängen nicht davon ab, wie der Generator ausgesät wird. Es gibt jedoch andere Dinge. sich Sorgen machen um. Siehe Pitfalls in Random Number Generation.

Wie für Hardware-Zufallszahlengeneratoren müssen diese physikalischen Quellen gemessen werden, und der Messvorgang hat systematische Fehler. Sie können "Pseudo" Zufallszahlen finden, um eine höhere Qualität als "echte" Zufallszahlen zu haben.

Answer 3

Einige verwenden Tastatureingabe (Timeouts zwischen Anschlägen), hörte ich von mir in einem Roman denke, dass Radio statischer Empfang genutzt werden kann - aber das ist natürlich andere Hard- und Software erfordert ...

Answer 4

SGI verwendete einmal Fotos einer Lavalampe bei verschiedenen "glob phases" als Quelle für die Entropie, die sich schließlich zu einem Open-Source-Zufallszahlengenerator namens LavaRnd entwickelte.

Answer 5

Ich benutze Random.ORG, sie bieten freie Zufallsdaten von Atmospheric Noise, die ich regelmäßig einen Seed Mersene-Twister RNG säen. Es ist ungefähr so ​​zufällig, wie Sie ohne Hardware-Abhängigkeiten erhalten können.

Answer 6

Der Linux-Kernel verwendet Geräte-Interrupt-Timing (Maus, Tastatur, Festplatten), um Entropie zu erzeugen. Es gibt eine nette article auf Wikipedia über Entropie.

Answer 7

Ich habe ein Verschlüsselungsprogramm verwendet, das die Mausbewegung des Benutzers zum Generieren von Zufallszahlen verwendet. Das einzige Problem war, dass das Programm pausieren musste und den Benutzer bat, die Maus für ein paar Sekunden nach dem Zufallsprinzip zu bewegen, um richtig zu funktionieren, was nicht immer praktisch war.

Answer 8

Ich fand HotBits vor einigen Jahren - die Zahlen werden aus radioaktivem Zerfall erzeugt, wirklich zufällig Zahlen.

Es gibt Grenzen, wie viele Zahlen Sie einen Tag herunterladen können, aber es hat mich immer amüsiert, diese als wirklich, wirklich zufällige Samen für RNG zu verwenden.

Answer 9

Moderne RNGs werden beide auf Korrelationen in benachbarten Seeds überprüft und nach dem Seeding mehrere hundert Iterationen durchgeführt. Also, die leider langweilige aber wahre Antwort ist, dass es wirklich nicht viel ausmacht.

Im Allgemeinen muss bei der Verwendung von zufälligen physikalischen Prozessen überprüft werden, ob sie einer gleichmäßigen Verteilung entsprechen und auf andere Art und Weise denaturiert werden.

In my opinion, it's often better to use a very well understood pseudo-random number generator.

Answer 10

Einige TPM (Trusted Platform Module) "Chips" haben eine RNG-Hardware. Leider fehlt dem (Broadcom) TPM in meinem Dell-Laptop diese Funktion, aber viele Computer, die heute verkauft werden, kommen mit einem Hardware-RNG, der wirklich unvorhersehbare quantenmechanische Prozesse verwendet. Intel hat die thermische Geräuschvielfalt implementiert.

Verwenden Sie auch nicht die aktuelle Zeit, um einen Zufallszahlengenerator für kryptografische Zwecke oder für Anwendungen zu generieren, bei denen Unvorhersagbarkeit wichtig ist. Die Verwendung einiger weniger niedriger Bits aus der Zeit in Verbindung mit mehreren anderen Quellen ist wahrscheinlich in Ordnung.

A similar question kann Ihnen nützlich sein.

Answer 11

Rauschen oben auf dem kosmischen Mikrowellen-Hintergrundspektrum. Natürlich müssen Sie zunächst einige Anisotropie, Vordergrundobjekte, korreliertes Detektorrauschen, Galaxien- und lokale Gruppengeschwindigkeiten, Polarisationen usw. entfernen. Viele pitfalls remain.

Answer 12

Mach dir keine Sorgen über einen "guten" Samen für einen Zufallsgenerator. Die statistischen Eigenschaften der Sequenz hängen nicht davon ab, wie der Generator ausgesät wird.

Ich stimme nicht mit John D. Cook's advice überein. Wenn Sie den Mersenne-Twister mit allen Bits, die auf Null gesetzt sind, mit Ausnahme einer Eins, erzeugen, werden zunächst Zahlen erzeugt, die alles andere als zufällig sind. Es dauert eine lange Zeit, bis der Generator diesen Zustand in alles umwandelt, das statistische Tests bestehen würde. Wenn Sie die ersten 32 Bit des Generators auf einen Seed setzen, wirkt sich dies ähnlich aus. Wenn der gesamte Status auf Null gesetzt ist, erzeugt der Generator endlose Nullen.

Richtig geschriebener RNG-Code wird einen richtig geschriebenen Seeding-Algorithmus haben, der einen 64-Bit-Wert akzeptiert und den Generator so sät, dass er für jede mögliche Eingabe angemessene Zufallszahlen erzeugt. Also, wenn Sie eine zuverlässige Bibliothek verwenden, dann wird jeder Samen tun. Aber wenn Sie Ihre eigene Implementierung hacken, dann müssen Sie vorsichtig sein.

Answer 13

Quelle der Samen ist nicht so wichtig. Wichtiger ist der Pseudo-Zahlen-Generator-Algorithmus. Ich habe jedoch schon vor einiger Zeit gehört, dass ich für einige Bankgeschäfte Saatgut erzeugen werde.Sie nahmen viele Faktoren zusammen:

• Zeit
• Prozessortemperatur
• Lüfterdrehzahl
• CPU-Spannung
• Ich erinnere mich nicht mehr :)

Auch wenn einige dieser Parameter ändern sich nicht viel in der Zeit, Sie können sie in eine gute Hash-Funktion bringen.

Wie generiere ich eine gute Zufallszahl?

Vielleicht können wir infinite Anzahl von Universen berücksichtigen? Wenn dies wahr ist, dass die ganze Zeit neue parallele Universen erstellt werden, können wir etwas tun:

int Random() { 
    return Universe.object_id % MAX_INT; 
} 

In jedem Moment sollten wir uns auf einem anderen Zweig der Paralleluniversen sein, so sollten wir verschiedene ID haben. Das einzige Problem ist, wie Universe-Objekt zu bekommen :)

Answer 14

Wie wäre es mit der Ausspinnen eines Threads, der einige Variablen in einer engen Schleife für eine bestimmte Zeit manipulieren wird, bevor es getötet wird. Was Sie am Ende haben, hängt von der Prozessorgeschwindigkeit, Systemlast, etc ... Sehr hokey, aber besser als nur srand (Zeit (NULL)) ...

Answer 15

Sorry, ich bin zu spät zu dieser Diskussion (was Ist es jetzt 3 1/2 Jahre alt?), aber ich habe ein neues Interesse an der PRN-Generation und alternativen Quellen der Entropie. Linux-Kernel-Entwickler Rusty Russell hatte kürzlich eine Diskussion über seine blog über alternative Quellen der Entropie (anders als /dev/urandom).

Aber ich bin nicht ganz so beeindruckt von seinen Entscheidungen; Die MAC-Adresse einer NIC ändert sich nie (obwohl sie von allen anderen eindeutig ist), und PID scheint zu klein für eine mögliche Stichprobengröße zu sein.

Ich habe mit einem Mersenne Twister (auf meiner Linux-Box) versucht, die mit dem folgenden Algorithmus gesetzt ist. Ich bitte für jede Kommentare/Feedback, wenn jemand bereit ist und interessiert:

1. Erstellen Sie ein Array-Puffer von 64 Bits + 256 Bits * Anzahl der /proc unten Dateien.
2. Setzen Sie den Wert des Zeitstempelzählers (TSC) in die ersten 64 Bits dieses Puffers.

3. Für jede der folgenden /proc Dateien, berechnen die SHA256 Summe:

   • /proc/meminfo
   • /proc/self/maps
   • /proc/self/smaps
   • /proc/interrupts
   • /proc/diskstats

   • /proc/self/stat

     Platzieren Sie jeden 256-Bit-Hash-Wert in einen eigenen Bereich des in (1) erstellten Arrays.

4. Erstellen Sie einen SHA256-Hash dieses gesamten Puffers. HINWEIS: Ich könnte (und sollte wahrscheinlich) eine andere Hash-Funktion verwenden, die völlig unabhängig von den SHA-Funktionen ist - diese Technik wurde als "Schutz" gegen schwache Hash-Funktionen vorgeschlagen.

Jetzt habe ich 256 Bits HOFFENTLICH random (genug) Entropie Daten meine Mersenne-Twister-Saatgut. Ich benütze das Obige, um den Anfang des MT-Arrays (624 32-Bit-Ganzzahlen) zu füllen, und initialisiere dann den Rest dieses Arrays mit dem MT-Autorcode. Auch könnte ich verwenden eine andere Hash-Funktion (z. B. SHA384, SHA512), aber ich würde eine andere Größe Array-Puffer (natürlich) benötigen.

Der ursprüngliche Mersenne-Twister-Code erforderte einen einzelnen 32-Bit-Seed, aber ich finde, das ist schrecklich unpassend. "Nur" 2^32-1 verschiedene MTs auf der Suche nach einem Bruch des Krypto zu laufen, liegt in der heutigen Zeit nicht jenseits der praktischen Möglichkeiten.

Ich würde gerne jemandes Feedback dazu lesen. Kritik ist mehr als willkommen. Ich werde meine Verwendung der /proc Dateien wie oben verteidigen, weil sie ständig ändern (besonders die /proc/self/* Dateien, und die TSC liefert immer einen anderen Wert (Nanosekunde [oder besser] Auflösung, IIRC). Ich habe Diehard tests auf diese ausgeführt (mehrere hundert Milliarden Bits in Höhe von), und es scheint, mit Bravour zu übergeben. Aber das ist wahrscheinlich mehr Beweis für die Solidität des Mersenne-Twister als PRNG als, wie ich es bin Impfen.

Natürlich sind diese nicht total undurchdringlich für jemand, der sie hackt, aber ich sehe nur nicht alle diese (und SHA *) gehackt werden und gebrochen in meiner Lebenszeit.