Kann ein neuronales Netzwerk verwendet werden, um die nächste Pseudozufallszahl vorherzusagen?

17

Ist es möglich, einem neuronalen Netzwerk die Ausgabe eines Zufallszahlengenerators zuzuführen und zu erwarten, dass es die Hashing- (oder Generator-) Funktion lernt, damit es vorhersagen kann, welche Pseudozufallszahl als nächstes generiert wird ?

Gibt es so etwas schon? Kann mich jemand auf die richtigen Ressourcen hinweisen, wenn dies oder etwas Ähnliches (zur Vorhersage von Pseudozufallszahlen) bereits erforscht ist?

Derzeit schaue ich mir diese Bibliothek und die dazugehörigen Links an. https://github.com/Vict0rSch/deep_learning/tree/master/keras/recurrent

AshTyson
quelle

Antworten:

13

Wenn wir über ein perfektes RNG sprechen, ist die Antwort ein klares Nein . Es ist unmöglich, eine wirklich zufällige Zahl vorherzusagen, sonst wäre sie nicht wirklich zufällig.

Wenn wir über Pseudo-RNG sprechen, ändern sich die Dinge ein wenig. Abhängig von der Qualität des PRNG reicht das Problem von leicht bis fast unmöglich. Ein sehr schwaches PRNG wie das von XKCD veröffentlichte könnte natürlich leicht von einem neuronalen Netzwerk mit wenig Training vorhergesagt werden. Aber in der realen Welt sehen die Dinge anders aus.

Das neuronale Netzwerk könnte trainiert werden, um bestimmte Muster in der Geschichte von Zufallszahlen zu finden, die von einem PRNG erzeugt werden, um das nächste Bit vorherzusagen. Je stärker das PRNG wird, desto mehr Eingangsneuronen sind erforderlich, vorausgesetzt, Sie verwenden ein Neuron für jedes Bit der vom PRNG erzeugten vorherigen Zufälligkeit. Je weniger vorhersehbar das PRNG wird, desto mehr Daten werden benötigt, um ein Muster zu finden. Für starke PRNGs ist dies nicht möglich.

Positiv ist zu vermerken, dass Sie eine beliebige Anzahl von Trainingsmustern für das neuronale Netzwerk generieren können, vorausgesetzt, Sie haben die Kontrolle über das PRNG und können so viele Zufallszahlen erzeugen, wie Sie möchten.

Da moderne PRNGs eine Schlüsselkomponente für die Kryptographie sind, wurden umfangreiche Untersuchungen durchgeführt, um zu überprüfen, ob sie "zufällig genug" sind, um solchen Vorhersageangriffen standzuhalten. Daher bin ich mir ziemlich sicher, dass es mit den derzeit verfügbaren Rechenressourcen nicht möglich ist, ein neuronales Netzwerk aufzubauen, um ein PRNG erfolgreich anzugreifen, das für die Kryptographie als sicher gilt.

Es ist auch erwähnenswert, dass es nicht notwendig ist, die Ausgabe eines PRNG genau vorherzusagen, um die Kryptographie zu unterbrechen - es könnte ausreichen, das nächste Bit mit einer Sicherheit von etwas mehr als 50% vorherzusagen, um eine Implementierung signifikant zu schwächen. Wenn Sie also in der Lage sind, ein neuronales Netzwerk aufzubauen, das das nächste Bit eines PRNG (als sicher für die Kryptografie angesehen) mit einer Erfolgsrate von 55% vorhersagt, werden Sie wahrscheinlich für eine Weile Schlagzeilen in den Sicherheitsnachrichten machen.

Demento
quelle
2
Wow danke für die Erklärung dahinter. Ich versuche, das Muster zu analysieren und das nächste Bit vorherzusagen, und es ist kein perfektes RNG, sondern ein etwas solides PRNG. Aber es ist auch nicht Stand der Technik. Ich denke, mit ein wenig Rechenleistung und korrekter Implementierung könnte ich es mit 60-70% vorhersagen, wenn nicht mehr. Wenn möglich, können Sie auf Ressourcen verweisen, in denen ich mehr darüber lesen kann. Ich habe keinen Forschungshintergrund und bin eher ein Entwickler.
AshTyson
3

Als absoluter Neuling im maschinellen Lernen habe ich dieses Experiment durchgeführt (mit Scikit-learn):

  • Generierte eine große Anzahl (N) von pseudozufälligen Extraktionen mit der Funktion Python random.choices, um N Zahlen aus 90 auszuwählen.

  • Ausbildung eines MLP-Klassifikators mit folgenden Trainingsdaten:

    • i. Beispiel: X <- lotteryResults [i: i + 100], Y <- lotteryResults [i]

    In der Praxis zielte ich auf eine Funktion ab, die bei N Zahlen die nächste vorhersagen konnte.

  • Er bat den ausgebildeten Klassifikator, die verbleibenden Zahlen vorherzusagen.

Ergebnisse:

  • Natürlich erhielt der Klassifikator eine Gewinnpunktzahl, die mit der von zufälligen Vermutungen oder anderen Techniken vergleichbar war, die nicht auf neuronalen Netzen basierten (ich verglich die Ergebnisse mit mehreren Klassifikatoren, die in Scikit-Learn-Bibliotheken verfügbar sind).

  • Wenn ich jedoch die pseudozufälligen Lotterieextraktionen mit einer bestimmten Verteilungsfunktion generiere, werden die vom neuronalen Netzwerk vorhergesagten Zahlen ungefähr mit derselben Verteilungskurve generiert (wenn Sie die Vorkommen der Zufallszahlen und der Vorhersagen des neuronalen Netzwerks darstellen). Sie können sehen, dass die beiden den gleichen Trend haben, auch wenn es in der Vorhersagekurve viele Spitzen gibt. Vielleicht kann das neuronale Netzwerk also etwas über Pseudozufallszahlenverteilungen lernen?

  • Wenn ich die Größe des Trainingssatzes unter eine bestimmte Grenze reduziere, sehe ich, dass der Klassifikator immer die gleichen wenigen Zahlen vorhersagt, die zu den häufigsten in der Pseudozufallsgenerierung gehören. Seltsamerweise (oder vielleicht auch nicht) scheint dieses Verhalten die Gewinnpunktzahl leicht zu erhöhen.

Francesco Bochicchio
quelle
3

Alte Frage, aber ich dachte, es ist eine praktische Antwort wert. Ich bin zufällig darauf gestoßen, nachdem ich mir eine Anleitung zum Aufbau eines solchen neuronalen Netzwerks angesehen hatte, die als Beispiel das Echo von Pythons Randint demonstrierte . Hier ist der endgültige Code ohne detaillierte Erklärung, immer noch recht einfach und nützlich, falls der Link offline geht:

from random import randint
from numpy import array
from numpy import argmax
from pandas import concat
from pandas import DataFrame
from keras.models import Sequential
from keras.layers import LSTM
from keras.layers import Dense

# generate a sequence of random numbers in [0, 99]
def generate_sequence(length=25):
    return [randint(0, 99) for _ in range(length)]

# one hot encode sequence
def one_hot_encode(sequence, n_unique=100):
    encoding = list()
    for value in sequence:
        vector = [0 for _ in range(n_unique)]
        vector[value] = 1
        encoding.append(vector)
    return array(encoding)

# decode a one hot encoded string
def one_hot_decode(encoded_seq):
    return [argmax(vector) for vector in encoded_seq]

# generate data for the lstm
def generate_data():
    # generate sequence
    sequence = generate_sequence()
    # one hot encode
    encoded = one_hot_encode(sequence)
    # create lag inputs
    df = DataFrame(encoded)
    df = concat([df.shift(4), df.shift(3), df.shift(2), df.shift(1), df], axis=1)
    # remove non-viable rows
    values = df.values
    values = values[5:,:]
    # convert to 3d for input
    X = values.reshape(len(values), 5, 100)
    # drop last value from y
    y = encoded[4:-1,:]
    return X, y

# define model
model = Sequential()
model.add(LSTM(50, batch_input_shape=(5, 5, 100), stateful=True))
model.add(Dense(100, activation='softmax'))
model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['acc'])
# fit model
for i in range(2000):
    X, y = generate_data()
    model.fit(X, y, epochs=1, batch_size=5, verbose=2, shuffle=False)
    model.reset_states()
# evaluate model on new data
X, y = generate_data()
yhat = model.predict(X, batch_size=5)
print('Expected:  %s' % one_hot_decode(y))
print('Predicted: %s' % one_hot_decode(yhat))

Ich habe es gerade versucht und es funktioniert in der Tat ganz gut! Es dauerte nur ein paar Minuten auf meinem alten langsamen Netbook. Hier ist meine eigene Ausgabe, die sich von dem obigen Link unterscheidet, und Sie können sehen, dass die Übereinstimmung nicht perfekt ist. Ich nehme an, dass die Ausstiegskriterien etwas zu tolerant sind:

...
 - 0s - loss: 0.2545 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.1845 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.3113 - acc: 0.9500
Expected:  [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 79, 45, 95, 92, 32, 33]
Predicted: [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 95, 45, 95, 92, 32, 33]
isp-zax
quelle
Dies lernt nicht, die zufällige Sequenz vorherzusagen - es lernt, sie wiederzugeben. Konkret besteht die Trainingsstichprobe X aus 5 zufälligen Ganzzahlen, und die Ausgabe y ist die 4. Ganzzahl der 5. Wenn beispielsweise X = [15, 33, 44, 30, 3], ist y = 30. Das LSTM lernt, die 4. Probe wiederzugeben.
thinkski
Ja, guter Punkt. Ich finde es immer noch ein sehr interessantes praktisches Beispiel für die Verwendung von LSTM. Wenn Sie wissen, wie man etwas wie Mersenne Twister aus Samen lernt, die nur als Eingabe gegeben werden, posten Sie es bitte hier, da ich wirklich interessiert wäre, es zu sehen. Scheint mit genügend Proben möglich, aber ich könnte völlig falsch liegen.
ISP-Zax
2

Wenn ein Pseudo-Zufallszahlengenerator Zahlen ausgibt, können Sie bei der Analyse dieser Zahlen den Algorithmus bestimmen, der sie erzeugt hat, da die Zahlen nicht zufällig sind, sondern von diesem Algorithmus bestimmt werden und kein Zufall sind. Wenn die Welt aus physikalischen Gesetzen besteht, die verstanden und repliziert werden können, dann ist die scheinbare Zufälligkeit, die wir bei Ereignissen beobachten, auf diese physikalischen Gesetze zurückzuführen. und der Pseudo-Generator ist nicht länger und ist eine tatsächliche Zufälligkeit, die nach ihrer Definition unbestimmbar ist und ein Paradox darstellt. Wie können Regeln per Definition Zufälligkeit erzeugen? Unsere offensichtliche Wahrnehmung der Zufälligkeit von Ereignissen, die wir beobachten, ist sicherlich eine Anspielung und tatsächlich eine Gewissheit, die wir nicht vorhersagen können.

Bobs
quelle
1
Wahr. Ganz philosophisch. Erwartet eine technische Antwort.
Trotzdem
2

Zusätzlich zu dem, was Demento gesagt hat, ist das Ausmaß der Zufälligkeit im Algorithmus zur Erzeugung von Zufallszahlen das Hauptproblem. Im Folgenden sind einige Entwürfe aufgeführt, die das RNG schwach machen können:
Verdeckte Sequenzen
Angenommen, dies sind die vorherigen Sequenzen von Zeichen, die generiert wurden: (Nur ein Beispiel für den praktischen Gebrauch wird ein größerer Bereich verwendet.)

lwjVJA
Ls3Ajg
xpKr+A
XleXYg
9hyCzA
jeFuNg
JaZZoA

Anfangs können Sie kein Muster in den Generationen beobachten, aber wenn Sie sie in Base64-Codierung und dann in Hex ändern, erhalten wir Folgendes:

9708D524
2ECDC08E
C692ABF8
5E579762
F61C82CC
8DE16E36
25A659A0

Wenn wir nun jede Zahl von der vorherigen subtrahieren, erhalten wir Folgendes:

FF97C4EB6A
97C4EB6A
FF97C4EB6A
97C4EB6A
FF97C4EB6A
FF97C4EB6A

Dies zeigt an, dass der Algorithmus dem vorherigen Wert nur 0x97C4EB6A hinzufügt, das Ergebnis auf eine 32-Bit-Zahl abschneidet und die Daten von Base64 codiert.
Das Obige ist ein grundlegendes Beispiel. Die heutigen ML-Algorithmen und -Systeme sind in der Lage, komplexere Muster zu lernen und vorherzusagen.

Zeitabhängigkeit
Einige RNG-Algorithmen verwenden die Zeit als Haupteingabe für die Generierung von Zufallszahlen, insbesondere diejenigen, die von Entwicklern selbst erstellt wurden, um in ihrer Anwendung verwendet zu werden.

Immer wenn schwache RNG-Algorithmen implementiert werden, die stochastisch erscheinen, können sie mit perfekter Genauigkeit vorwärts oder rückwärts extrapoliert werden, falls ein ausreichender Datensatz verfügbar ist.

Ugnes
quelle
Sie haben mir gerade eine Vorstellung in meinem eigenen Kopf zwischen Quantität und ihrer Kommunikation gezeigt, die eine Methode zur Bestimmung eines Musters ist, von dem ich wusste, dass ich nicht weit von meiner Intuition entfernt bin :)
Bobs
Aber es wirft immer noch eine untrennbare Frage auf, ob Zufälligkeit ein "Produkt" ist, das von der Rationalität getrennt ist, wenn wir versuchen, es anhand einer Funktion der Sprache zu beschreiben, die wir verwenden, die aus einer Demut bei der Aufrechterhaltung des Evolutionsprozesses und der wahrgenommenen Methode zur Aufrechterhaltung der menschlichen Gesundheit abgeleitet ist lol.
Bobs
Ist Zufälligkeit oder ihre Wahrnehmung eine Disjunktion zwischen Realität und menschlicher Wahrnehmung, und aufgrund ihrer Disjunktheit entscheidet nur ein Rest der empfindungsfähigen Wahrnehmung über jedes Bild, das wir alle beobachten, und summiert sich zu einer übertragbaren Zufälligkeit aufgrund der intellektuellen Disjunktheit im Menschen. Konzentrischer Faktor bei der konzeptuellen Verteilung.
Bobs
Wie können Sie jemals etwas ohne eine Basis analysieren, von der aus Sie Ihre Analyse beginnen können, wenn Sie versuchen, die Zufälligkeit zu analysieren, dann ist es sicherlich eine Basis der Gewissheit ego enteric lol
Bobs
Pseudozufälligkeit ist eine Eigenschaft von Plastikmenschen, die sich als echte bodenständige Eigenschaften tarnen, die sie überflüssig missachten und mit denen sie sich unheilig oder menschlich beschäftigen. Entschlossenheit führt zu Glauben und einer Gewissheit des Berufs und einer gesunden Kommunikation des Produkts eines guten Lebens, das den Problemen eines Gleichgewichts der Not nicht standhält.
Bobs