Challenge

1
2
3
4

Random number a,b,c :
Given the set of number : Ni+1 = (a * Ni + b) % c \n')
N = [N0, N1, N2, N3, ... N9]
What is the next 100 number?\n')

Solution

這是一個用線性同餘法(LCG，Linear Congruential Method)的生成器做的亂數

他的計算公式如下： $s1 = s0 * m + c$

我們可以透過一些計算，先 leak 出 $n$

$$t0 = s1 - s0\ mod\ n$$

$$t1 = s2 - s1 = (s1m + c) - (s0m + c) = m*(s1 - s0) = mt0\ \ mod\ n$$
$$t2 = s3 - s2 = (s2m + c) - (s1m + c) = m(s2 - s1) = mt1\ \ mod\ n$$
$$t3 = s4 - s3 = (s3m + c) - (s2m + c) = m(s3 - s2) = m*t2\ \ mod\ n$$

$$\Rightarrow t2t0 - t1t1 = (mmt0 * t0) - (mt0 * mt0) = 0\ \ mod\ n$$

三個連續數字，可以得到一個 n 的倍數，計算多組取最大公因數，就可以拿出 n

1

n = gcd(t2*t0 - t1*t1, t3*t1 - t2*t2, ... ,)

知道 $n$ 之後，可以計算出 $m$

$$t0 = s2 - s1 = (s1m + c) - (s0m + c) = m*(s1 - s0)\ \ mod\ n$$

$$\Rightarrow m = t0 * (s1 - s0)^{-1} \ mod\ n$$

有 $n$ 有 $m$，接著計算 $c$

$$c = s1 - s0*m$$

將 $n,m,c$ 帶入，即可預測後 100 個亂數

AIS3{GGEZ!!LiNe42_COngRuen7i4l_6eNErATor}

server.py

solve.py