MT19937 state recovery and predictor
Recover the full Mersenne Twister state from 624 consecutive outputs by inverting the tempering function - then predict Python’s random module exactly.
Open in ctfpalMT19937 backs random in Python, Math.random in some engines, and mt_rand in PHP. It has excellent statistical properties and no cryptographic security whatsoever: its output is a reversible function of its internal state, so observing enough output reconstructs the state exactly.
Untempering
Each 32-bit output is the state word passed through four invertible steps - two right shifts with XOR, two left shifts with XOR and a mask. Every one of those is reversible bit by bit, so untemper() recovers the state word from the output word. Collect 624 consecutive outputs, untemper each, and you hold the entire state array. From there the generator is deterministic forever, forward and backward.
def unshift_right(value, shift):
result = value
for _ in range(32 // shift + 1):
result = value ^ (result >> shift)
return resultCommon questions
- Does this work on Python’s `random.randint`?
- Yes, but `randint` consumes a variable number of words depending on the range, so you must model the same rejection sampling Python uses. Raw `getrandbits(32)` output is the clean case.
Related tools
Linear congruential generator predictor
Recover the modulus, multiplier, and increment of an LCG from a handful of consecutive outputs, then predict every future value.
Modular arithmetic and number theory toolkit
Modular inverse, Chinese remainder theorem, Tonelli-Shanks square roots, Jacobi symbols, and integer nth roots - arbitrary precision, in the browser.
RSA decryption and attack runner
Paste n, e, and c and let ctfpal choose the attack: trial division, Fermat, Pollard’s rho, Wiener, common modulus, or Hastad broadcast. Arbitrary-precision, in-browser.
Fermat factorization for close RSA primes
Factor an RSA modulus whose primes were generated too close together. Fermat’s method finds them in a handful of steps where trial division never would.