Wir erhöhen die Zufälligkeit der Tatsache, dass [wahrscheinlich] [fast] zufällig

Zufallszahlen schmackhafter, wenn ein wenig Pfeffer

Wir werden Theorie mit Praxis kombinieren - wir werden zeigen, dass eine Verbesserung der Entropie von Zufallssequenzen möglich ist, wonach wir uns die Quellcodes ansehen, die dies tun.

Ich wollte unbedingt darüber schreiben, dass eine qualitativ hochwertige, dh hochentropische Zufallszahlengenerierung für die Lösung einer Vielzahl von Problemen von entscheidender Bedeutung ist, aber dies ist wahrscheinlich überflüssig. Ich hoffe, jeder weiß das sehr gut.

Auf der Suche nach hochwertigen Zufallszahlen erfinden die Leute sehr witzige Geräte (siehe zum Beispiel hier und hier ). Im Prinzip sind ziemlich gute Zufallsquellen in die API von Betriebssystemen integriert, aber dies ist eine ernste Angelegenheit, und ein wenig Zweifel frisst uns: Ist das RNG, das ich verwende, gut genug und wird es verwöhnt ... sagen wir, von Dritten?

Ein bisschen Theorie

Zunächst zeigen wir, dass mit dem richtigen Ansatz die Qualität des vorhandenen RNG nicht beeinträchtigt werden kann. Der einfachste richtige Ansatz besteht darin, eine andere Sequenz durch die XOR-Operation auf der Hauptsequenz zu überlagern. Die Hauptsequenz kann zum Beispiel ein systemisches RNG sein, das wir bereits für gut halten, aber es gibt immer noch einige Zweifel, und wir hatten den Wunsch, auf Nummer sicher zu gehen. Eine zusätzliche Sequenz kann zum Beispiel ein Pseudozufallszahlengenerator sein, dessen Ausgabe gut aussieht, aber wir wissen, dass seine reale Entropie sehr niedrig ist. Die resultierende Sequenz ist das Ergebnis der Anwendung der XOR-Operation auf die Bits der Primär- und Sekundärsequenz. Eine signifikante Nuance: Die Primär- und Sekundärsequenzen müssen unabhängig voneinander sein. Das heißt, ihre Entropie muss aus grundlegend unterschiedlichen Quellen stammen, deren gegenseitige Abhängigkeit nicht berechnet werden kann.

Bezeichne mit x das nächste Bit der Hauptsequenz und y - das entsprechende Bit der zusätzlichen Sequenz. Das Bit der resultierenden Sequenz wird mit r bezeichnet :
r = x⊕y

Der erste Versuch zu beweisen. Versuchen wir, die Informationsentropie von x , y und r durchzugehen . Wir bezeichnen die Wahrscheinlichkeit von Null x als p _x0 und die Wahrscheinlichkeit von Null y als p _y0 . Die Informationsentropien x und y werden nach der Shannon-Formel berechnet:

H _x = - (p _{x 0} log ₂ p _{x 0} + (1 - p _{x 0} ) log ₂ (1 - p _{x 0} ))
H _y = - (p _y0 log ₂ p _y0 + (1 - p _y0 ) log ₂ (1 - p _y0 ))

Null in der resultierenden Sequenz wird angezeigt, wenn sich am Eingang zwei Nullen oder zwei Einheiten befinden. Wahrscheinlichkeit von Null r:

p _r0 = p _x0 p _y0 + (1 - p _x0 ) (1 - p _y0 )
H _r = - (p _r0 log ₂ p _r0 + (1 - p _r0 ) log ₂ (1 - p _r0 ))

Um die Unveränderlichkeit der Hauptsequenz zu beweisen, muss dies bewiesen werden
Hr - Hx ≥ 0 für alle Werte von p _x0 und p _y0 . Ich konnte es nicht analytisch beweisen, aber die visualisierte Berechnung zeigt, dass die Zunahme der Entropie eine glatte Oberfläche bildet, die nirgendwo auf Minus gehen wird:


Wenn wir zum Beispiel ein stark verzerrtes zusätzliches Signal mit p _y0 = 0,1 zum verzerrten Hauptsignal c p _x0 = 0,3 (Entropie 0,881) hinzufügen, erhalten wir das Ergebnis p _r0 = 0,66 mit Entropie 0,925.

Entropie kann also nicht verdorben werden, aber dies ist noch nicht genau. Daher ist ein zweiter Versuch erforderlich. Durch Entropie kann man aber auch beweisen. Schema (alle Schritte sind recht einfach, Sie können es selbst tun):

1. Wir beweisen, dass die Entropie am Punkt p ₀ = 1/2 ein Maximum hat.
2. Wir beweisen, dass für jedes p _x0 und p _{y0 der} Wert von p _r0 nicht weiter von 1/2 als p _{x0 entfernt sein kann} .

Der zweite Versuch zu beweisen. Durch die Fähigkeit zu raten. Angenommen, ein Angreifer hat a priori Informationen über die Primär- und Sekundärsequenzen. Der Besitz von Informationen drückt sich in der Fähigkeit aus, die Werte von x , y und als Ergebnis von r mit einiger Wahrscheinlichkeit im Voraus zu erraten. Die Wahrscheinlichkeiten für das Erraten von x und y werden mit g _x bzw. g y bezeichnet (aus dem Wort "erraten"). Das Bit der resultierenden Sequenz wird entweder erraten, wenn beide Werte richtig erraten wurden, oder wenn beide falsch sind. Die Wahrscheinlichkeit des Erratens ist also folgende:
g _r = g _x g _y + (1 - g _x ) (1 - g _y ) = 2 g _x g _y - g _x - g _y + 1

Wenn wir den perfekten Vermesser haben, haben wir g = 1. Wenn wir nichts wissen, ist g ... nein, nicht null, sondern 1/2. Dies ist genau die Wahrscheinlichkeit, dass es sich herausstellt, wenn wir eine Entscheidung treffen, indem wir eine Münze werfen. Ein sehr interessanter Fall ist, wenn g <1/2 ist. Einerseits hat ein solcher Vermesser irgendwo in sich Daten über den vorhergesagten Wert, kehrt jedoch aus irgendeinem Grund seine Ausgabe um und die Münze wird schlechter . Bitte denken Sie an den Satz "schlimmer als eine Münze", er wird uns unten nützlich sein. Aus Sicht der mathematischen Kommunikationstheorie (und damit der uns bekannten quantitativen Informationstheorie) ist diese Situation absurd, da es sich nicht um eine Informationstheorie handelt, sondern um eine Desinformationstheorie, aber im Leben haben wir diese Situation viel häufiger als wir möchten .

Betrachten Sie die Grenzfälle:

• g _x = 1 , d. h. die Sequenz x ist vollständig vorhersagbar:
  g _r = g _x g _y + (1 - g _x ) (1 - g _y ) = 1 g _y + (1 - 1) (1 - g _y ) = g _y
  Das heißt, die Wahrscheinlichkeit, das Ergebnis zu erraten, ist gleich der Wahrscheinlichkeit, die zusätzliche Sequenz zu erraten.
• g _y = 1 : Ähnlich wie beim vorherigen. Die Wahrscheinlichkeit, das Ergebnis zu erraten, entspricht der Wahrscheinlichkeit, die Hauptsequenz zu erraten.
• g _x = 1/2 , d. h. die Sequenz x ist völlig unvorhersehbar:
  g _r = 2 g _x g _y - g _x - g _y + 1 = 2/2 g _y - 1/2 - g _y + 1 = g _y - g _y + 1/2 = 1/2
  Das heißt, das Hinzufügen einer zusätzlichen Sequenz beeinträchtigt nicht die vollständige Unvorhersehbarkeit der Hauptsequenz.
• g _y = 1/2 : Ähnlich wie beim vorherigen. Das Hinzufügen einer völlig unvorhersehbaren zusätzlichen Sequenz macht das Ergebnis völlig unvorhersehbar.

Um zu beweisen, dass das Hinzufügen einer zusätzlichen Sequenz zur Hauptsequenz dem Angreifer nicht hilft, müssen wir herausfinden, unter welchen Bedingungen g _r größer als g _{x sein kann} , d. H.

2 g _x g _y - g _x - g _y + 1> g _x

Bewegen Sie g _x von rechts nach links und g _y und 1 nach rechts:

2 g _x g _y - g _x - g _x > g _y - 1
2 g _x g _y - 2 g _x > g _y - 1
Wir nehmen auf der linken Seite 2g _x aus Klammern heraus:
2 g _x (g _y - 1)> g _y - 1
Da wir g _y kleiner als eins haben (der Grenzfall, wenn g _y = 1 ist, haben wir bereits berücksichtigt), wandeln wir g _y −1 in 1 - g _{y um} , ohne zu vergessen, "mehr" in "weniger" zu ändern:
2 g _x (1 - g _y ) <1 - g _y

Reduzieren Sie "1 - g _y " und erhalten Sie die Bedingung, unter der das Hinzufügen einer zusätzlichen Sequenz die Situation für den Angreifer verbessert:

2 g _x <1
g _x <1/2

Das heißt, g _r kann nur dann größer als g _{x sein} , wenn die Hauptsequenz schlechter als eine Münze ist . Dann, wenn unser Prädiktor in bewusste Sabotage verwickelt ist.

Einige zusätzliche Überlegungen zur Entropie.

1. Entropie ist ein äußerst mythologisches Konzept. Informationen - einschließlich. Das ist sehr beunruhigend. Informationsentropie wird oft als eine Art subtile Materie dargestellt, die entweder objektiv in den Daten vorhanden ist oder nicht. Tatsächlich ist die Informationsentropie nicht im Signal selbst vorhanden, sondern eine quantitative Bewertung des a priori-Bewusstseins des Nachrichtenempfängers in Bezug auf die Nachricht selbst. Das heißt, es geht nicht nur um das Signal, sondern auch um den Empfänger. Wenn der Empfänger im Voraus überhaupt nichts über das Signal weiß, beträgt die Informationsentropie der übertragenen Binäreinheit genau 1 Bit, unabhängig davon, wie das Signal empfangen wurde und was es ist.
2. Wir haben einen Entropieadditionssatz, nach dem die Gesamtentropie unabhängiger Quellen gleich der Summe der Entropien dieser Quellen ist. Wenn wir die Hauptsequenz durch Verkettung mit der zusätzlichen Sequenz kombiniert hätten, hätten wir die Entropien der Quellen beibehalten, hätten aber ein schlechtes Ergebnis erzielt, da wir in unserer Aufgabe nicht die Gesamtentropie, sondern die spezifische Entropie in Bezug auf ein separates Bit bewerten müssen. Die Verkettung von Quellen gibt uns die spezifische Entropie des Ergebnisses, die dem arithmetischen Mittel der Entropie der Quellen entspricht, und die entropieschwache zusätzliche Sequenz verschlechtert natürlich das Ergebnis. Die Anwendung der XOR-Operation führt dazu, dass wir einen Teil der Entropie verlieren, aber die resultierende Entropie ist garantiert nicht schlechter als die maximale Entropie der Terme.
3. Kryptographen haben ein Dogma: Die Verwendung von Pseudozufallszahlengeneratoren ist unverzeihliche Arroganz. Weil diese Generatoren eine kleine spezifische Entropie haben. Aber wir haben gerade herausgefunden, dass Entropie, wenn alles richtig gemacht wird, zu einem Fass Honig wird, das durch keine Menge Teer verdorben werden kann.
4. Wenn wir nur 10 Bytes reale Entropie haben, verteilt auf ein Kilobyte Daten, haben wir aus formaler Sicht nur 1% der spezifischen Entropie, was sehr schlecht ist. Aber wenn diese 10 Bytes qualitativ verschmiert sind und abgesehen von Brute Force keine Möglichkeit besteht, diese 10 Bytes zu berechnen, sieht nicht alles so schlecht aus. 10 Bytes sind 2 ⁸⁰ , und wenn unsere Brute Force pro Sekunde eine Billion Optionen durchsucht, benötigen wir durchschnittlich 19.000 Jahre, um zu lernen, wie man das nächste Zeichen errät.

Wie oben erwähnt, ist die Informationsentropie ein relativer Wert. Wenn für ein Subjekt die spezifische Entropie 1 ist, kann sie für ein anderes durchaus 0 sein. Außerdem hat eine mit 1 möglicherweise keine Möglichkeit, den wahren Stand der Dinge zu kennen. Das System RNG erzeugt einen Stream, der für uns nicht von wirklich zufällig zu unterscheiden ist, aber wir können nur hoffen, dass er für alle wirklich zufällig ist. Und glauben. Wenn Paranoia darauf hindeutet, dass die Qualität des Haupt-RNG plötzlich unbefriedigend sein könnte, ist es sinnvoll, sich mit Hilfe eines zusätzlichen abzusichern.

Implementieren eines summierenden RNG in Python

from random import Random, SystemRandom from random import BPF as _BPF, RECIP_BPF as _RECIP_BPF from functools import reduce as _reduce from operator import xor as _xor class CompoundRandom(SystemRandom): def __new__(cls, *sources): """Positional arguments must be descendants of Random""" if not all(isinstance(src, Random) for src in sources): raise TypeError("all the sources must be descendants of Random") return super().__new__(cls) def __init__(self, *sources): """Positional arguments must be descendants of Random""" self.sources = sources super().__init__() def getrandbits(self, k): """getrandbits(k) -> x. Generates an int with k random bits.""" ########         : return _reduce(_xor, (src.getrandbits(k) for src in self.sources), 0) def random(self): """Get the next random number in the range [0.0, 1.0).""" ########  ,   SystemRandom   .  ... return self.getrandbits(_BPF) * _RECIP_BPF 

Anwendungsbeispiel:

 >>> import random_xe # <<<    >>> from random import Random, SystemRandom >>> #  : >>> myrandom1 = random_xe.CompoundRandom(SystemRandom(), Random()) >>> #    Random: >>> myrandom1.random() 0.4092251189581082 >>> myrandom1.randint(100, 200) 186 >>> myrandom1.gauss(20, 10) 19.106991205743107 

SystemRandom, das als korrekt angesehen wird, wird als Hauptstrom und als Nebenstrom - als Standard-PRNG-Zufall - verwendet. Der Punkt dabei ist natürlich nicht sehr viel. Das Standard-PRNG ist definitiv nicht die Art von Ergänzung, für die es sich gelohnt hat, anzufangen. Stattdessen können Sie zwei systemische RNGs zusammen heiraten:

 >>> myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom()) 

Der Sinn, die Wahrheit darin ist noch weniger (obwohl Bruce Schneier aus irgendeinem Grund aus irgendeinem Grund in der Angewandten Kryptographie empfiehlt), da die obigen Berechnungen nur für unabhängige Quellen gelten. Wenn das System-RNG gefährdet ist, wird auch das Ergebnis beeinträchtigt. Im Prinzip ist der Flug der Phantasie bei der Suche nach einer Quelle zusätzlicher Entropie nicht durch irgendetwas begrenzt (in unserer Welt ist Unordnung viel häufiger als Ordnung), aber als einfache Lösung werde ich das HashRandom PRSP anbieten, das auch in der random_xe-Bibliothek implementiert ist.

PRSPs basierend auf Streaming Circular Hashing

Im einfachsten Fall können Sie eine relativ kleine Menge von Anfangsdaten verwenden (z. B. den Benutzer bitten, auf der Tastatur zu trommeln), ihren Hash berechnen und dann den Hash zyklisch zur Eingabe des Hash-Algorithmus hinzufügen und die folgenden Hashes ausführen. Schematisch kann dies wie folgt dargestellt werden:



Die kryptografische Stärke dieses Prozesses basiert auf zwei Annahmen:

1. Die Wiederherstellung der Originaldaten aus dem Hashwert ist unerträglich kompliziert.
2. Mit dem Hash-Wert kann der interne Status des Hashing-Algorithmus nicht wiederhergestellt werden.

Nach Rücksprache mit einem internen Paranoiden erkannte er die zweite Annahme als unnötig an, und daher ist das Schema bei der endgültigen Umsetzung des PRNG etwas kompliziert:



Wenn es einem Angreifer nun gelingt, einen "Hash 1r" -Wert zu erhalten, kann er den ihm folgenden "Hash 2r" -Wert nicht berechnen, da er keinen "Hash 2h" -Wert hat, den er nicht erkennen kann, ohne die Hash-Funktion "gegen Wolle" zu berechnen. Somit entspricht die kryptografische Stärke dieses Schemas der kryptografischen Stärke des verwendeten Hashing-Algorithmus.

Anwendungsbeispiel:

 >>> #  ,  HashRandom     '123': >>> myrandom3 = random_xe.CompoundRandom(SystemRandom(), random_xe.HashRandom('123')) >>> #    Random: >>> myrandom3.random() 0.8257149881148604 

Standardmäßig wird der SHA-256-Algorithmus verwendet. Wenn Sie etwas anderes möchten, können Sie den gewünschten Typ des Hashing-Algorithmus mit dem zweiten Parameter an den Konstruktor übertragen. Lassen Sie uns zum Beispiel ein zusammengesetztes RNG erstellen, das Folgendes in einem Haufen zusammenfasst:

1. Systemisches RNG (das ist heilig).
2. Benutzereingaben, die vom SHA3-512-Algorithmus verarbeitet werden.
3. Die für diese Eingabe aufgewendete Zeit, die von SHA-256 verarbeitet wird.

 >>> from getpass import getpass >>> from time import perf_counter >>> from hashlib import sha3_512 #    : >>> def super_myrandom(): t_start = perf_counter() return random_xe.CompoundRandom(SystemRandom(), random_xe.HashRandom( getpass('  :'), sha3_512), random_xe.HashRandom(perf_counter() - t_start)) >>> myrandom4 = super_myrandom()   : >>> myrandom4.random() 0.35381173716740766 

Schlussfolgerungen:

1. Wenn wir uns bei unserem Zufallszahlengenerator nicht sicher sind, können wir dieses Problem einfach und erstaunlich billig lösen.
2. Wenn wir dieses Problem lösen, können wir es nicht schlimmer machen. Nur besser. Und es ist mathematisch bewiesen.
3. Wir dürfen nicht vergessen, sicherzustellen, dass die verwendeten Entropiequellen unabhängig sind.

Die Bibliotheksquellen befinden sich auf GitHub .