Wie kann ich die Anfangswerte des Pseudozufallszahlengenerators bestimmen, wenn die Sequenz angegeben ist?

Angenommen, ich wusste, dass eine Zufallszahlenfolge von einem linearen Kongruenzgenerator erzeugt wurde. Das ist,

$x_{n+1}=(aX_n+c) \bmod m$

Wie kann ich die Parameter $a,c,m$ und rekonstruieren $x_0$ , die diese Sequenz erzeugt haben, wenn mir die gesamte Periode (oder zumindest eine große zusammenhängende Folge davon) gegeben wird ? Ich suche nach einer allgemeinen Methode, mit der die Anfangsparameter ermittelt werden können, wenn der Pseudozufallszahlengenerator bekannt ist.

random-number-generation inverse-problem Paul
quelle

Was genau ist bekannt? Anhand einer zusammenhängenden Folge können Sie nicht erkennen, wo die Sequenz

begann

x_{0}

$x_0$ , es sei denn, die Elemente werden nacheinander indiziert. Wenn

m

$m$ bekannt ist, werden

a

$a$ und

c

$c$ leicht entdeckt.

Hardmath

Antworten:

Siehe das Papier Wie man einen linearen Kongruenzgenerator knackt , Haldir ("Reverse Engineering Team", Dezember 2004):

In diesem Artikel werde ich eine Methode vorstellen, die alle Werte des LCG einschließlich des Moduls mit sechs oder mehr aufeinanderfolgenden PRNG-Ausgangszahlen löst.

Das Papier enthält in C geschriebenen "Proof of Concept" -Quellcode, der Victor Shoups NTL für erweiterte Präzisionsarithmetik verwendet.

Hardmath
quelle

Das war eine großartige Zeitung! :) Kennen Sie eine allgemeinere Methode, die für andere Zufallszahlengeneratoren gelten könnte, nicht nur für lineare Kongruenzen?

Paul

@Paul: Man kann natürlich RNGs finden, die für ihre Parameter leicht aus ausreichenden Ausgabedaten "gelöst" werden können (inverses Problem), aber es scheint, dass je besser das RNG (zufälliger das Erscheinungsbild der Ausgabe), desto schwieriger das inverse Problem wäre. Die Lösung des LCG-Falls hängt mit bestimmten bekannten dimensionalen Clustering-Effekten zusammen, wodurch Paare generierter Werte ungleichmäßig verteilt werden. Weitere

Informationen finden