Unveiling the Magic Behind Random Number Generation in PHP

Introduction: The Enigma of Randomness in Computing

Hello, tech enthusiasts! Have you ever pondered how computers, those epitomes of precision and predictability, manage to generate «random» numbers? In the digital realm, true chaos is elusive, replaced by deterministic algorithms and predictable states. Today, we’ll delve into the mechanics of randomness in PHP, focusing on the Mersenne Twister algorithm. By the end of this article, you’ll understand:

  • The workings of the Mersenne Twister algorithm
  • Why these numbers are «pseudorandom» and how they can be predicted
  • The differences between rand() and mt_rand() and their unsuitability for cryptography
  • The inner workings of the random number generator in PHP 8.x

Evolution of Random Number Generators in PHP

The journey of random number generators in PHP has evolved from basic algorithms to more sophisticated solutions:

// PHP 4/5 (outdated version)
$random = rand(0, 100); 

// PHP 5+ (improved version)
$betterRandom = mt_rand(0, 100);

// PHP 7+ (cryptographically secure)
$secureRandom = random_int(0, 100);

Today, we’ll focus on mt_rand(), which utilizes the Mersenne Twister algorithm, a popular choice for generating pseudorandom numbers.

Mersenne Twister: Precision in Randomness

Developed in 1997 by Makoto Matsumoto and Takuji Nishimura, the Mersenne Twister algorithm is named after Mersenne primes (numbers of the form 2^n — 1). Its key features include:

  • A massive period of 2¹⁹⁹³⁷ — 1 numbers
  • High-speed performance
  • Excellent distribution of values

But how does it work in practice? Let’s break it down step-by-step.

Step 1: Initialization — The Seed of Randomness

The process begins with a «seed»—an initial value that transforms a deterministic algorithm into a generator of «random» numbers. Here’s a glimpse into the PHP source code:

// Example initialization from PHP source code
PHPAPI inline void php_random_mt19937_seed32(php_random_status_state_mt19937 *state, uint32_t seed)
{
    uint32_t i, prev_state;
    state->state[0] = seed;
    for (i = 1; i state[i - 1];
        state->state[i] = (1812433253U * (prev_state ^ (prev_state >> 30)) + i) & 0xffffffffU;
    }
    state->count = i;

    mt19937_reload(state);
}

Key Points:

  • The magic number 1812433253 was chosen for optimal bit dispersion.
  • The operation x ^ (x >> 30) helps spread the seed’s influence across the state.
  • Adding + i ensures different states even with a seed of 0.

Step 2: Number Generation — The Heart of Mersenne Twister

When you call mt_rand(), the following occurs:

static php_random_result generate(void *state)
{
    php_random_status_state_mt19937 *s = state;
    uint32_t s1;

    // Reload state if numbers are exhausted
    if (s->count >= N) {
        mt19937_reload(s);
    }

    // Fetch the next number from the state array
    s1 = s->state[s->count++];

    // Apply "tempering transform" for better distribution
    s1 ^= (s1 >> 11);
    s1 ^= (s1 << 7) & 0x9d2c5680U;
    s1 ^= (s1 <> 18)),
    };
}

Key Points:

  • Each number is drawn from a precomputed state array.
  • Tempering (bitwise operations) conceals linear dependencies.
  • After 624 numbers, the state is fully recomputed.

Step 3: State Reloading

Every 624 calls, the state array is completely refreshed:

static inline void mt19937_reload(php_random_status_state_mt19937 *state)
{
    uint32_t *p = state->state;

    if (state->mode == MT_RAND_MT19937) {
        // Main mixing loop
        for (uint32_t i = N - M; i--; ++p) {
            *p = twist(p[M], p[0], p[1]);
        }
        // Tail processing
        for (uint32_t i = M; --i; ++p) {
            *p = twist(p[M-N], p[0], p[1]);
        }
        *p = twist(p[M-N], p[0], state->state[0]);
    } else {
        for (uint32_t i = N - M; i--; ++p) {
            *p = twist_php(p[M], p[0], p[1]);
        }
        for (uint32_t i = M; --i; ++p) {
            *p = twist_php(p[M-N], p[0], p[1]);
        }
        *p = twist_php(p[M-N], p[0], state->state[0]);
    }

    state->count = 0;
}

Where twist is a macro that shuffles bits:

#define N             624                 /* length of state vector */
ZEND_STATIC_ASSERT(
    N == sizeof(((php_random_status_state_mt19937*)0)->state) / sizeof(((php_random_status_state_mt19937*)0)->state[0]),
    "Assumed length of Mt19937 state vector does not match actual size."
);
#define M             (397)                /* a period parameter */
#define hiBit(u)      ((u) & 0x80000000U)  /* mask all but highest   bit of u */
#define loBit(u)      ((u) & 0x00000001U)  /* mask all but lowest    bit of u */
#define loBits(u)     ((u) & 0x7FFFFFFFU)  /* mask     the highest   bit of u */
#define mixBits(u, v) (hiBit(u) | loBits(v)) /* move hi bit of u to hi bit of v */

#define twist(m,u,v)  (m ^ (mixBits(u,v) >> 1) ^ ((uint32_t)(-(int32_t)(loBit(v))) & 0x9908b0dfU))
#define twist_php(m,u,v)  (m ^ (mixBits(u,v) >> 1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))

All these numbers, which seem random, are meticulously crafted by the algorithm’s creators for enhanced randomization.

Conclusion: The Illusion of Randomness

We’ve explored how PHP generates «random» numbers using the Mersenne Twister algorithm and dissected the C source code. But why are these numbers called pseudorandom? Can they be predicted? Yes, they can. Knowing 624 consecutive numbers allows you to reconstruct the state, which is why PHP documentation includes this note:

Unveiling the Magic Behind Random Number Generation in PHP

In our next article, we’ll explore how to generate cryptographically secure random values. Thank you for joining us on this deep dive into PHP’s random number generation! If you enjoyed unraveling the source code as much as I did, stay tuned for more insights into PHP’s hidden mechanisms, such as:

  • PHP’s interaction with the external world: Networking and HTTP
  • The magic of introspection: A closer look at the Reflection API
  • JIT compilation in PHP 8 — a revolution under the hood
  • Asynchronous PHP: From coroutines to Fibers

Thank you for your attention!