Rating:

## PokePark - Raising New Generation Writeup (6 solves / 497 points)
> nc 3.16.14.62 5000

### [Solve Script](sol/apex.py)
py
from Crypto.Util.number import inverse, GCD
from functools import reduce

def get_inc(states, m, n):
s1 = states
s2 = states
return ( s2 - m * s1) % n

def get_mult(states, n):
s1 = states
s2 = states
s3 = states
m = ((s3 - s2) * inverse(s2-s1, n)) % n
return m

def get_mod(states):
diffs = [b - a for a, b in zip(states, states[1:])]
z = [a*c - b**2 for a, b, c in zip(diffs, diffs[1:], diffs[2:])]
n = reduce(GCD, z)
return n

def predict_state(curr_state, n, m, c):
pred = (m * curr_state + c) % n
return pred

if __name__ == '__main__':

states = [1997095401, 13001997, 1628715232, 1990339562, 284249215, 1372925577, 48385624, 1468364002, 2059193937, 26044107]

n = get_mod(states)
print("n:", n)

m = get_mult(states, n)
print("m:", m)

c = get_inc(states, m, n)
print("c:", c)

print("predicted:", predict_state(states[-1], n, m, c))


The name of the challenge was supposed to be a hint that it's Park-Miller Random Number Generator ?. Here is a little bit of intro stuff about
this Random Number Generator (RNG).

State[i+1] = m * State[i] mod n

where **m** is the multiplier and n is the prime modulus. So the next **State[i+1]** is determined by multiplying the
current **State[i]** with **m** and then mod **n**.

## Predicting The Next State
### The Modulus
According to this - [Cracking a linear congruential generator](https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator)
we can recover the modulus by this method:

*To recover m, define t<sub>n</sub> = s<sub>n</sub> + 1 - s<sub>n</sub> and u<sub>n</sub> = |t<sub>n</sub> + 2 * t<sub>n</sub> - t2<sub>n</sub> + 1|;
then with high probability you will have m = gcd(u1, u2, ..., u10). 10 here is arbitrary; if you make it k, then the probability that this fails is
exponentially small in k.*

### The Multiplier
We can get the multiplier by solving the two linear equations only,

s1 = s0 * m + c (mod n)

s2 = s1 * m + c (mod n)

s2 - s1 = s1 * m - s0 * m (mod n)

s2 - s1 = m * (s1 - s0) (mod n)

m = ((s2 - s1) * inverse_mod(s1 - s0, n)) (mod n)

where **s0, s1 and s2** are the three consecutive states.

### The Increment
The increment for Lehmer RNG is 0 but if you want you can recover that too,

s1 = s0 * m + c (mod n)

c = s1 - s0 * m (mod n)

Now that we have the modulus, multiplier and the increment( which is 0 anyway) we can predict the next state like this:

next_state = m * last_state + c (mod n)

Now submit the predicted value and get the flag !!! \o/  ## Flag
> darkCON{P0k3m0ns_4nd_RNG!!!}

### # Source Code + the binary - [[./src folder]](src/)

## Ref
* [Lehmer random number generator - Wiki](https://en.wikipedia.org/wiki/Lehmer_random_number_generator)
* [Cracking a linear congruential generator](https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator)

Original writeup (https://github.com/r3yc0n1c/CTF-Writeups/tree/main/2021/darkCON-2021/Crypto/PokePark%20-%20Raising%20New%20Generation#pokepark---raising-new-generation-writeup-6-solves--497-points).