LCG

LCG，线性同余生成器

principle

递归公式$s_{n+1}=as_n+b\mod{p}$

若$gcd(a,p)=1$,则周期$T=ord(a)$

因此选取系数时应尽量使得a为模m的原根，以此尽量延长LCG周期，使$T=phi(p)$

Crack methods

unknown a,b

已知：m,s0,s1,s2

$$\begin{align} \because s_{1} &= a * s_{0} + b \pmod m\\ s_{2} &= a * s_{1} + b\pmod m\\ \therefore s_{2} - s_{1} &= a * s_{1} - s_{0}\pmod m\\ a &= \frac{s_{2} - s_{1} }{s_{1} - s_{0}}\pmod{p} \end{align}$$

以下是另一种利用格密码的解法：

一组求模等式方程组的通法，基于LLL，对构造的格基进行约化

$$\left[\matrix{a&b&1&k_{1}&k_{2}}\right] \left[\matrix{ s_{0}&s_{1}&\frac{1}{m}&0&0\\ 1&1&0&\frac{1}{m}&0\\ -s_{1}&-s_{2}&0&0&1\\ m&0&0&0&0\\ 0&m&0&0&0 }\right]$$

因此我们要找到格基约化后一个行向量，满足前两个元素为0

为了在约化后的矩阵中得到直观的a, b，邻接上一个$\frac{E}{m}$（这里不用单位矩阵E的原因，是因为最好使得包含a(-a),b(-b)的行向量的长度尽可能短，也就是说更大的分母也是允许的

在LLL约化后，找到满足下列要求的行向量r，即求解成功：

• r[0] = r[1] = 0
• r[-1] = 1(-1)
  𝑚⋅𝑟[2]=𝑎(−𝑎),𝑚⋅𝑟[3]=𝑏(−𝑏)

#sage
A = Matrix([  
    [s0  ,s1  ,1/m ,0   ,0   ],  
    [1   ,1   ,0   ,1/m ,0   ],  
    [-s1 ,-s2 ,0   ,0   ,1   ],  
    [m   ,0   ,0   ,0   ,0   ],  
    [0   ,m   ,0   ,0   ,0   ]  
])  
A = A.LLL()  
a = None  
b = None  
for l in A:  
    if l[0] == 0 and l[1] == 0:  
        if l[-1] == 1:  
            a, b = l[2] * m, l[3] * m  
        elif l[-1] == -1:  
            a, b = -l[2] * m, -l[3] * m  
        else:  
            continue  
if not a or not b:  
    raise ValueError("[*] No solves")  
a %= m  
b %= m

unknown a,b,p

已知$s_{0}$~$s_6$

令​$\begin{align} T_{n}&=s_{n+1}-s_{n}\\ T_{n+1} &= S_{n+2} - S_{n+1} = a(S_{n+1} - S_{n})= aT_{n}\pmod p\\ T_{n+2} &= S_{n+3} - S_{n+2} = at(S_{n+2} - S_{n+1}) = aT_{n+1} = a^{2}T_{n}\pmod p\\ \therefore T_{n}T_{n+2} &- T_{n+1}^{2} = 0\pmod p \end{align}$
既然$T_{n}T_{n+2} - T_{n+1}^{2}=kp$, 那么可以尝试gcd一连串的$T_{n}T_{n+2} - T_{n+1}^{2}$来找到p
此时问题就转化为unknown(a,b)

LCG_LLBP

结合HNP的LCG，seed高位泄露

这个问题一般给出了a，b，m和一组连续的seed的高位

$$\begin{align} &s_{n+1}=as_{n}+b\mod{p}\\ &拆分高低位，s_{n}=h_{n}+l_{n}\\ &h_{n+1}+l_{n+1}=a(h_{n}+l_{n})+b\mod{p}\\ &l_{n+1}=al_{n}+ah_{n}+b-h_{n+1}\mod{p}\\ &l_{n+2}=al_{n+1}+ah_{n+1}+b-h_{n+2}\mod{p}\\ &\therefore l_{n+2}=al_{n}+a(ah_{n}+b-h_{n+1})+(ah_{n+1}+b-h_{n+2})\mod{p}\\ &构造A ,B\\ &l_{n+1}= A_{n}+b_{n}+k_{n}m\\ &构造lattice\\ &\left[\matrix{ p&\\ &p\\ \vdots&\vdots&\ddots\\ A_{1}&A_{2}&\cdots&1&0\\ B_{1}&B_{2}&\cdots&0&2^{lbit} }\right] \end{align}$$

#sage
p=...
a=...
b=...
s=[...]
lbit=...

s.insert(0,0) #添上未输出s0 = 0
for i in range(len(s)):
    out[i] <<= lbit
A = [1]
B = [0]
for i in range(1, len(s)-1):
    A.append(a*A[i-1] % p)
    B.append((a*B[i-1]+a*s[i]+b-s[i+1]) % p)
A = A[1:]
B = B[1:]

Ai = matrix(A)
Bi = matrix(B)
Mi = matrix.identity(len(s)-1)*p
K = ZZ(pow(2,lbit))
M = matrix.block([[Mi,ZZ(0),ZZ(0)],[Ai,ZZ(1),ZZ(0)],[Bi,ZZ(0),K]])

ll = M.LLL()[0]
l1 = ll[-2]
h1 = out[1]
s1 = l1+h1
#for s1=a*seed+b%m
seed = ((s1-b)*inverse_mod(a,p))%p
print(seed)

得到seed之后就可以直接推测next了

参考Summary-of-Crypto-in-CTF(PRNG) | 0xDktb’s Blog (dunkirkturbo.github.io)
LCG(线性同余生成器)-CSDN博客
| 独奏の小屋 (hasegawaazusa.github.io)