# XMAS CTF 2018 Let’s Crack the Greater lapland monolith

# XMAS CTF 2018 Let’s Crack the Greater lapland monolith

### Let’s Crack the Greater lapland monolith by Johannes

The first step is to find the modulus to calculate other values of LCG.

One feature of Linear Congruent Generators is that the modulus in most cases is equal to greatest common divisor of the generated values.

Therefore, I took 10 generated values and did `gcd(a1,a2,a3 ...)`

which gives us the modulus.

The other step is to get the multiplier.

We have two equations `a1=a*mult+inc (mod modul) a2=a1*mult+inc`

(mod modul). From here we obtain that `mult = (a2-a1)/(a1-a0);`

The last step is to crack the increment and it is pretty easy. `a1=a*mult+inc (mod modul) --> inc = a1-a*mult`

(mod modul)

Yeah we finally cracked the LCG, now we can submit the values into the field and get our flag.