Rating:

This was more of a guessing challenge than a crypto challenge. We are given 10 seemingly random integers and asked to predict the next one. The numbers are all less than 2^31, so it is most likely a 31-bit PRNG. The simplest and most well-known class of PRNGs is Linear Congruential Generators, or LCGs for short. LCGs usually have 3 parameters: the modulus, the multiplier, and the increment, or `m`, `a` and `c` for short. All LCGs produce their next output with the following formula:

```

next = (a * prev + c) % m

```

Now, if we know `m`, we can compute the parameters of the LCG by observing 3 consecutive outputs from it, like this:

```

y = a*x + c

z = a*y + c

z-y = a*y+c - a*x - c = a*(y-x)

a = (z-y) / (y-x)

c = z - a*y

```

Note that all of these are done modulo `m`. We can divide by multiplying with the modular multiplicative inverse.

This will give an answer for every set of 3 outputs. We can verify it by also computing the parameters for a different set of 3 outputs and checking that we get the same multiplier and increment.

Now, all that remains is to find `m`. Since all input numbers are between 0 and around 2 billion, it's reasonable to assume that `m` is around `2^31`. However, if we try exactly `2^31`, we find that we get a different multiplier for each set of 3 outputs, so this isn't the correct modulus. LCGs often have a prime modulus though (it helps with increasing the period), so we can also try `2^31-1`. With that, we find `a = 16807` and `c = 0`. These are consistent for every set of 3 outputs, so they are the correct parameters for the LCG.

```py

x = 1875578086

y = 2075920736

z = 1980480790

m = 2**31-1

a = (z-y) * pow(y-x, -1, m) % m

c = (z - a*y) % m

print("next output after z: ", (a*z+c) % m)

# in this example, the next output is 2091592677

```

Entering this gives us the flag.

Also, these parameters happen to match the LCG used in C++'s `minstd_rand0` algorithm, so you might have solved it by trying random PRNGs until one matched the sequence in the challenge.

Original writeup (https://github.com/keyboard-monkeys/ctf-writeups/blob/main/2021-darkctf/crypto_pokepark_raising_new_generation.md).