CODEWITHSUNDEEP
phprandom
Redseb
Redseb

Reputation: 329

PHP SourceCode Random

The function for rand() should be something like (SEED * A + C) mod M.

How can I find the values of A, C, and M? And if I find those values, can I predict the next number in the sequence?

I know that I can find the values of these variables in the PHP source code. But after looking around I really cannot find them...

Does anybody know what file it would be in? Or who else I could contact (I've tried email [email protected] but haven't got a response)

Also I'm doing all this in PHP versions prior to 7, where rand() and mt_rand() became synonymous.

EDIT: I have seen Is it possible to predict rand(0,10) in PHP? but those answers aren't about the constant values in PHP's rand() value by themselves.

Thank you!

Upvotes: 2

Views: 960

Answers (1)

LSerni
LSerni

Reputation: 57428

I believe that the old school rand() function used a linear congruential generator.

This generator is system dependent. One algorithm employed by glibc was:

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

so there you have your constants. The state, of course, is the initial value of 'next', which is zero unless set differently by srand().

There are ways of attacking a linear congruence; one possibility - the slowest, but the easiest to explain - is to brute force it. Say that you four consecutive values: a0, a1, a2, a3 from your rand() implementation. You can check all values of seed that would yield that same sequence.

Note that if your a0 value is produced by, say, rand() % 7172, then your initial seed must obey the rule that "seed % 7172 === a0". This immediately reduces the space you need to brute force, speeding up operations proportionately. Also, you don't need to check all four numbers.

This would be the efficient equivalent of running (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;
}

Experiments

By checking with a reference trivial C source code

#include <stdio.h>

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

I determined that PHP and C do indeed share the same underlying function (I tabulated different values for srand()).

I also found out that srand(0) and srand(1) yield the same result, which isn't consistent with my linear model.

And that's because glibc rand() is not so trivial a linear congruential generator. More info here. Actually it is quoted in a SO answer and the code I had was for the old, TYPE_0 generator.

Upvotes: 1

Related Questions