Linear congruential generator predictor
Recover the modulus, multiplier, and increment of an LCG from a handful of consecutive outputs, then predict every future value.
Open in ctfpalAn LCG produces s[n+1] = (a * s[n] + c) mod m. Three unknowns, and each output is an equation - so with enough consecutive outputs the parameters are recoverable by arithmetic alone, even when none of a, c, or m were disclosed.
Recovering the parameters in order
- Modulus first. Build differences
t[n] = s[n+1] - s[n]. Thent[n+2]*t[n] - t[n+1]^2is a multiple ofmfor every n. The GCD of several such values ism(or a small multiple of it). - Multiplier next. With
mknown,a = (s[2] - s[1]) * inverse(s[1] - s[0], m) mod m. - Increment last.
c = (s[1] - a * s[0]) mod m.
Six consecutive outputs is comfortably enough. Fewer will do when some parameters are already known - and challenges often disclose m as a familiar constant like 2**32 or 2**48, which removes the hardest step.
Related tools
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.
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.
ECDSA nonce reuse private key recovery
Recover an ECDSA private key from two signatures that reused the same nonce - the flaw that broke the PlayStation 3 and countless wallets.
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.