PHP SourceCode Random

Question

Die Funktion für rand() sollte etwas wie (SEED * A + C) mod M sein. Wie kann ich die Werte von A, C und M finden? Und wenn ich diese Werte finde, kann ich die nächste Zahl in der Sequenz vorhersagen?

Ich weiß, dass ich die Werte dieser Variablen im PHP-Quellcode finden kann. Aber nachdem ich mich umgesehen habe, kann ich sie wirklich nicht finden ...

Weiß jemand, in welcher Datei es wäre? Oder wer sonst könnte ich kontaktieren (Ich habe versucht, E-Mail internals@lists.php.net, aber noch keine Antwort bekam)

Auch dies alles mache ich vor in PHP-Versionen bis 7, wobei rand() und mt_rand() wurde auch synonym.

EDIT: Ich habe gesehen Ist es möglich, Rand (0,10) in PHP vorherzusagen? aber diese Antworten beziehen sich nicht auf die konstanten Werte in PHPs rand() Wert.

Vielen Dank!

Answer 1

Ich glaube, dass die alte Schule rand() Funktion verwendet linear congruential generator.

Diese generator is system dependent. Ein von glibc verwendeter Algorithmus war:

next = next * 1103515245 + 12345; 
return next & 0x7fffffff; 

so haben Sie Ihre Konstanten. Der Zustand ist natürlich der Anfangswert von "next", der null ist, sofern er nicht anders durch srand() gesetzt wird.

Es gibt Möglichkeiten, eine lineare Kongruenz anzugreifen; Eine Möglichkeit - die langsamste, aber am einfachsten zu erklären - ist Brute Force es. Sagen Sie, dass Sie vier aufeinanderfolgende Werte haben: a0, a1, a2, a3 von Ihrer rand() Implementierung. Sie können alle Werte von Seed überprüfen, die dieselbe Sequenz ergeben würden.

Beachten Sie, dass, wenn Ihr a0-Wert von, sagen wir, rand()% 7172 produziert wird, dann muss der ursprüngliche Startwert der Regel "seed% 7172 === a0" entsprechen. Dies reduziert sofort den Platz, den Sie für die Brute-Force-Lösung benötigen, und beschleunigt die Operationen entsprechend. Außerdem müssen Sie nicht alle vier Zahlen überprüfen.

Dies würde ich bestimmt

#include <stdio.h> 

int main() { 
     srand(1); 
     printf("%ld\n", rand()); 
} 

die effizienten äquivalent läuft (in PHP)

for ($seed = 0; $seed < MAX_SEED; $seed++) { 
    srand($seed); 
    if ($a0 !== [RAND() FORMULA]) return false; 
    if ($a1 !== [RAND() FORMULA]) return false; 
    if ($a2 !== [RAND() FORMULA]) return false; 
    if ($a3 !== [RAND() FORMULA]) return false; 
    return true; 
} 

Experiment

durch Vergleich mit einer Referenz trivial C Quellcode sein, dass PHP und C tatsächlich teilen die gleiche zugrunde liegende Funktion (ich tabellierte verschiedene Werte für srand()).

Ich fand auch heraus, dass srand (0) und srand (1) das gleiche Ergebnis liefern, was nicht mit meinem linearen Modell übereinstimmt.

Und das ist, weil glibc rand() ist nicht so trivial ein linearer kongruenter Generator. Weitere Informationen here.Tatsächlich ist es in einer SO answer zitiert und der Code, den ich hatte, war für den alten Generator TYPE_0.