These are two very similar challenges: the first one has a bug so that you can solve it in an unintended way, so the organizers realized a second “fixed” challenge. The following method works for both of them.
We’re given a web page that gets a random integer and asks us to guess it, multiple times. After guessing correctly 20 times, it will return a flag.
From the title we can see that the prng is of lcg type (linear congruential generator), that is, given 3 integers and a seed , the sequence is constructed as . It turns out that the website tells you what value it randomized even if you fail, so observing about 10 values we can break the prng as follows:
We did this using the Python script from msm from p4team and then did it on the website by hand (input 20 times is faster than scripting). Here’s the code:
from functools import reduce from gmpy2 import gcd def egcd(a, b): if a == 0: return (b, 0, 1) else: g, x, y = egcd(b % a, a) return (g, y - (b // a) * x, x) def modinv(b, n): g, x, _ = egcd(b, n) if g == 1: return x % n def crack_unknown_increment(states, modulus, multiplier): increment = (states - states*multiplier) % modulus return modulus, multiplier, increment def crack_unknown_multiplier(states, modulus): multiplier = (states - states) * modinv(states - states, modulus) % modulus return crack_unknown_increment(states, modulus, multiplier) def crack_unknown_modulus(states): diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])] zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])] modulus = abs(reduce(gcd, zeroes)) return crack_unknown_multiplier(states, modulus) obs = [9933, 16949, 696, 30323, 33563, 25061, 14546, 13243, 12116] n,k,d = crack_unknown_modulus(obs) state = obs[-1] while True: state = (state*k+d) % n print(state) input()