AIS3 2019 - Random Guess (Crypto, 196)

Challenge

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=s0m+cs1 = s0 * m + c

我們可以透過一些計算,先 leak 出 nn

t0=s1s0 mod nt0 = s1 - s0\ mod\ n

t1=s2s1=(s1m+c)(s0m+c)=m(s1s0)=mt0  mod nt1 = s2 - s1 = (s1*m + c) - (s0*m + c) = m*(s1 - s0) = m*t0\ \ mod\ n

t2=s3s2=(s2m+c)(s1m+c)=m(s2s1)=mt1  mod nt2 = s3 - s2 = (s2*m + c) - (s1*m + c) = m*(s2 - s1) = m*t1\ \ mod\ n

t3=s4s3=(s3m+c)(s2m+c)=m(s3s2)=mt2  mod nt3 = s4 - s3 = (s3*m + c) - (s2*m + c) = m*(s3 - s2) = m*t2\ \ mod\ n

t2t0t1t1=(mmt0t0)(mt0mt0)=0  mod n\Rightarrow t2*t0 - t1*t1 = (m*m*t0 * t0) - (m*t0 * m*t0) = 0\ \ mod\ n

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

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

知道 nn 之後,可以計算出 mm

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

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

nnmm,接著計算 cc

c=s1s0mc = s1 - s0*m

n,m,cn,m,c 帶入,即可預測後 100 個亂數

AIS3{GGEZ!!LiNe42_COngRuen7i4l_6eNErATor}

server.py

solve.py