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.