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


    Zufallszahlen sind schmackhafter, wenn man sie ein bisschen putzt.

    Wir werden Theorie mit Praxis kombinieren - wir werden zeigen, dass eine Verbesserung der Entropie von Zufallsfolgen möglich ist.

    Ich wollte unbedingt darüber schreiben, dass die Erzeugung von Zufallszahlen mit hoher Qualität, dh mit hoher Entropie, 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.

    Im Streben nach hochwertigen Zufallszahlen erfinden Menschen sehr witzige Geräte (siehe zum Beispiel hier und hier)) Grundsätzlich sind recht gute Zufallsquellen in die API von Betriebssystemen eingebaut, aber dies ist eine ernste Angelegenheit, und ein Zweifel frisst uns immer ein wenig: Ist das RNG, das ich verwende, gut genug und ist es verdorben? 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 Ansatz ist richtig - es auf erlegt der Primärsequenz eines anderen durch die XOR - Operation. 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ärsequenzen. Wesentliche Nuance:Die Primär- und Sekundärsequenzen müssen unabhängig voneinander sein. Das heißt, ihre Entropie sollte aus grundlegend unterschiedlichen Quellen stammen, deren gegenseitige Abhängigkeit nicht berechnet werden kann.

    Bezeichnen Sie das nächste Bit der Hauptsequenz mit x , und y ist das entsprechende Bit des zusätzlichen Bits. Das Bit der resultierenden Sequenz wird mit r bezeichnet :
      r = x⊕y

    Der erste Versuch zu beweisen. Lassen Sie uns versuchen, die Informationsentropie von x , y und r zu durchlaufen . Die Wahrscheinlichkeit eines Null - x wird durch bezeichnet p x0 , und die Wahrscheinlichkeit von Null y als py0 . Die Informationsentropien x und y werden nach der Shannon-Formel berechnet:

      Hx= - (px0log2px 0+ (1 - px 0) log2(1 - px 0))
      Hy= - (py0log2py 0+ ( 1 - py0) log2(1 - py0)) Eine

    Null in der resultierenden Sequenz erscheint, wenn zwei Nullen oder zwei Einheiten am Eingang liegen. Wahrscheinlichkeit von null r:

      pr0= px0py0+ (1 - p x0 ) (1 - p y0 )
      H r = - (p r0 log 2 p r0 + (1 - p r0 ) log 2 (1 - p r0 ))

    Um zu beweisen, dass sich die Hauptsequenz nicht verschlechtert, beweisen Sie, dass
    Hr - Hx ≥ 0 für alle Werte von p x0 und p y0 ist . Ich konnte es nicht analytisch beweisen, aber die visualisierte Berechnung zeigt, dass die Zunahme der Entropie eine glatte Oberfläche bildet, die nirgendwo anders hingeht, minus:


    wenn schief zu dem Hauptsignal C beispielsweise p x0 = 0,3 (0,881 Entropie) in stark verzerrt mit zusätzlichem p y0 = 0,1, so erhält man das Ergebnis p r0 = 0,66 Entropie von 0,925.

    Die Entropie kann also nicht verderbt werden, aber das ist noch nicht richtig. Daher ist ein zweiter Versuch erforderlich. Durch Entropie kann man aber auch einen Beweis führen. Schema (alle Schritte sind recht einfach, Sie können es selbst machen):

    1. Wir beweisen, dass die Entropie am Punkt p 0 = 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 erraten. Angenommen, ein Angreifer verfügt a priori über Informationen zu den primären und sekundären Sequenzen. Der Besitz von Informationen drückt sich in der Fähigkeit aus, mit einer gewissen Wahrscheinlichkeit die Werte von x , y und als Ergebnis von r im Voraus zu erraten . Die Wahrscheinlichkeiten für das Erraten von x und y werden jeweils mit g x und g y (aus dem Wort erraten) bezeichnet. Das Bit der resultierenden Sequenz wird entweder erraten, wenn beide Werte richtig erraten wurden, oder wenn beide falsch sind, sodass die Wahrscheinlichkeit des Erratens wie folgt ist:
      g r = g x gy + (1 - g x ) (1 - g y ) = 2 g x g y - g x - g y + 1

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

    Betrachten Sie die Grenzfälle:

    • gx = 1, то есть последовательность x полностью предсказуемая:
        gr = gx gy + (1−gx) (1−gy) = 1 gy + (1−1) (1−gy) = gy
      То есть вероятность угадывания результата равна вероятности угадывания дополнительной последовательности.
    • gy = 1: Аналогично предыдущему. Вероятность угадывания результата равна вероятности угадывания основной последовательности.
    • g x = 1/2 , dh die Folge 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.

    Для того, чтобы доказать, что добавление дополнительной последовательности к основной ничем не поможет злоумышленнику, нам нужно выяснить, при каких условиях gr может быть больше gx, то есть

      2 gx gy − gx − gy + 1 > gx

    Переносим gx из правой части в левую, а gy и 1 в правую:

      2 gx gy − gx − gx > gy − 1
      2 gx gy − 2 gx > gy - 1
    Setze im linken Teil 2g x aus den 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, haben wir bereits berücksichtigt), drehen wir g y - 1 bis 1 - g y , 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 Sie ein zusätzliches hinzufügen Die Schätzreihenfolge für den Angreifer wird sich verbessern:

      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 ist als eine Münze . Dann, wenn unser Predictor mit bewusster Sabotage beschäftigt ist.

    Einige zusätzliche Überlegungen zur Entropie.

    1. Entropie ist ein äußerst mythologischer Begriff. Informationen - einschließlich. Das ist sehr beunruhigend. Oft wird die Informationsentropie als eine Art subtile Materie dargestellt, die entweder objektiv in den Daten vorhanden ist oder nicht. Tatsächlich ist die Informationsentropie nicht das, was im Signal selbst vorhanden ist, sondern eine quantitative Beurteilung 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 Verketten mit der zusätzlichen Sequenz kombinieren, würden wir die Entropien der Quellen beibehalten, aber ein schlechtes Ergebnis erhalten, da wir in unserer Aufgabe nicht die gesamte Entropie, sondern die spezifische Entropie in Form eines separaten Bits bewerten müssen. Die Verkettung von Quellen ergibt 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. Kryptografen haben ein Dogma: Die Verwendung von Pseudozufallszahlengeneratoren ist unverzeihlich arrogant. 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 verderbt werden kann.
    4. Wenn wir nur 10 Bytes reale Entropie haben, verteilt auf ein Kilobyte Daten, haben wir formal gesehen nur 1% der spezifischen Entropie, was sehr schlecht ist. Aber wenn diese 10 Bytes qualitativ verschmiert sind und es außer roher Gewalt keine Möglichkeit gibt, diese 10 Bytes zu berechnen, sieht nicht alles so schlecht aus. 10 Bytes sind 2 80 , und wenn unsere rohe Kraft pro Sekunde eine Billion Optionen durchsucht, werden wir durchschnittlich 19.000 Jahre brauchen, 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. Darüber hinaus kann eine Person mit 1 keine Möglichkeit haben, den wahren Sachverhalt zu kennen. Das systemische RNG erzeugt einen Strom, der für uns nicht von wirklich zufällig zu unterscheiden ist, aber wir können nur hoffen, dass er für jeden wirklich zufällig ist . Und glauben. Wenn die Paranoia vermuten lässt, dass die Qualität des Haupt-RNG plötzlich nicht mehr zufriedenstellend ist, ist es sinnvoll, die Sicherheit mit Hilfe eines zusätzlichen RNG zu gewährleisten.

    Implementieren eines Summierungs-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, wurde als Hauptstream und als Sekundärstream verwendet - als Standard-PRSP-Zufall. 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 ist noch weniger (obwohl Bruce Schneier aus irgendeinem Grund diese Technik in „Applied Cryptography“ empfiehlt), weil die obigen Berechnungen nur für unabhängige Quellen gültig sind. Wenn das System-RNG beeinträchtigt wird, wird auch das Ergebnis beeinträchtigt. Im Prinzip ist die Suche nach einer Quelle zusätzlicher Entropie nicht durch irgendetwas eingeschränkt (in unserer Welt ist Unordnung viel häufiger als Ordnung), aber als einfache Lösung biete ich das HashRandom PRSP an, das auch in der random_xe-Bibliothek implementiert ist.

    PRSPs, die auf Streaming Circular Hashing basieren


    Im einfachsten Fall können Sie eine relativ kleine Menge von Anfangsdaten verwenden (z. B. den Benutzer auffordern, auf der Tastatur zu trommeln), deren 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 Aufgabe, die ursprünglichen Daten aus dem Hash-Wert wiederherzustellen, ist unerträglich kompliziert.
    2. Mit dem Hash-Wert kann der interne Zustand des Hash-Algorithmus nicht wiederhergestellt werden.

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



    Gelingt es einem Angreifer nun, einen „Hash 1r“ -Wert zu erhalten, kann er den nachfolgenden „Hash 2r“ -Wert nicht berechnen, da er keinen „Hash 2h“ -Wert hat, den er nicht ohne Berechnung der Hash-Funktion „gegen Wolle“ erkennen kann. 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 wünschen, können Sie den gewünschten Typ des Hashing-Algorithmus als zweiten Parameter an den Konstruktor übergeben. Lassen Sie uns zum Beispiel ein zusammengesetztes RNG erstellen, das Folgendes in einem Haufen zusammenfasst:

    1. System-RNG (das ist heilig).
    2. Benutzereingaben, die vom SHA3-512-Algorithmus verarbeitet werden.
    3. Die für diesen Eingang 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 Zufallsgenerator 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 noch 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 .

    Jetzt auch beliebt: