Crypto基础篇-LCG

简介

LCG： 即线性同余生成器，形式为$X_{n+1}\equiv aX_n+b\mod m$
该问题总结来说的常见考点：

• 求$X_0(seed)$
• 求$b$
• 求$a$
• 求$m$
• 非连续
• $X_n$高位泄露
  我们接下来逐个分析求解，

求$X_0(seed)$

条件： 已知$a,b,m,X_n$
分析：
$\because X_{n}\equiv aX_{n-1}+b \mod m$
$\therefore aX_{n-1}\equiv X_n-b\mod m$
$\therefore X_{n-1}\equiv a^{-1}(X_n-b) \mod m$
依次类推，便可以求得$X_0$
代码实现：

from Crypto.Util.number import *
a=
b=
m=
X_n=

inv_a=inverse(a,m)
for i in range(n):
	X_n=inv_a*(X_n-b) %m
seed=X_n
print(seed)

求b

条件： 已知$a,m,X_n,X_{n+1}$
分析：
$\because X_{n+1}\equiv aX_n+b \mod m$
$\therefore b\equiv X_{n+1}-aX_n \mod m$
代码实现：

from Crypto.Util.number import *
a=
m=
X_n=
X_n_plus=

b=X_n_plus-a*X_n %m
print(b)

求a

条件： 已知$m,X_n,X_{n+1},X_{n+2}$
分析：
$\because已知$
$X_{n+2}\equiv aX_{n+1}+b \mod m$
$X_{n+1}\equiv aX_n+b \mod m$
$\therefore X_{n+2}-X_{n+1}\equiv a(X_{n+1}-X_n) \mod m$
$\therefore a\equiv(X_{n+1}-X_n)^{-1}(X_{n+2}-X_{n+1})\mod m$
代码实现：

from Crypto.Util.number import *
m=
X_n=
X_np1=
X_np2=

a=inverse(X_np1-X_n,m)*(X_np2-X_np1) %m
print(a)

求m

条件： 已知至少两组四个连续的序列值，即最少五个连续值$X_{n-1},X_n,X_{n+1},X_{n+2},X_{n+3}$
分析：
$\because X_n\equiv aX_{n-1}+b \mod m$
令$t_n=X_{n+1}-X_n$
则$t_{n-1}=X_n-X_{n-1}$
易得$t_n\equiv at_{n-1} \mod m$
同理$t_{n+1}\equiv at_n \mod m$
相除消去$a$，再移项得$t_{n+1}t_{n-1}\equiv t_n^2 \mod m$
$\therefore t_{n+1}t_{n-1} - t_n^2 = k_1m$
同理有$t_{n+2}t_{n} - t_{n+1}^2 = k_2m$
$\therefore m=gcd(t_{n+1}t_{n-1} - t_n^2,t_{n+2}t_{n} - t_{n+1}^2 )$

代码实现：
由于实际情况中公因数可能会带有小因子，因此若序列足够多可多试几组。

from Crypto.Util.number import *
X_seq=[]

t=[]
for i in range(len(X_seq)-1):
	t.append(X_seq[i+1]-X_seq[i])

T=[]  #T_i=T_ip2 * T_i - T_ip1**2 
for i in range(len(t)-2):
	T.append(t[i+2]*t[i]-t[i+1]**2)

m=GCD(T[0],T[1]) #m的候选值
for i in range(2,len(T)):
    m=GCD(m,T[i])

print(m)

非连续

条件： 已知$X_n,X_{n+2}$等序列
分析：
$\because X_{n+2}\equiv a(aX_n+b)+b \mod m$
$\therefore X_{n+2} \equiv a^2X_n+(a+1)b \mod m$
令$a_1=a^2,b_1=(a+1)b$
$\therefore X_{n+2}\equiv a_1X_n+b_1 \mod m$
之后按正常LCG步骤便可以解答即可

$X_n$高位/低位泄露

条件： 已知$X_n$高位$H_1,H_2,…,H_n（与原bit位相同的高位）,a,b,m$，求$L_1$
分析：
$\because H_2+L_2\equiv a(H_1+L_1)+b \mod m$
$\therefore L_2\equiv aL_1+(aH_1-H_2+b) \mod m$
$\therefore L_3\equiv a^2L_1+(a(aH_1-H_2+b)-H_3+b) \mod m$
令$A_i=a^i\mod m,B_i=aB_{i-1}-H_{i+1}+aH_i+b\mod m$，其中$B_1=(aH_1-H_2+b)\mod m$
因此，得到
$L_{i+1}\equiv A_iL_1+B_i \mod m$
下一步，构造格

$$ (k_1,k_2,...,k_n,L_1,1) \begin{pmatrix} m & 0 & \cdots & 0 & 0 & 0 \\ 0 & m & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & m & 0 & 0 \\ A_1 & A_2 & \cdots & A_n & 1 & 0 \\ B_1 & B_2 & \cdots & B_n & 0 & K \end{pmatrix} \\ =(L_2,L_3,...,L_{n+1},L_1,K) $$

求出$L_1$之后便可以反向求出$seed$，这里的$K$与$L$的bit位相同。

到这里你可能也已经发现了，已知$X_n$的高位或者低位，其求法本质是一样的，因为在我们的分析中$H$和$L$几乎是完全等效的。

代码实现：

#sage
from Crypto.Util.number import *

a=
b=
m=
h=[]
kbits=

H=[0]+h
for i in H:
	i <<= kbits

A=[1]
B=[0]
for i in range(1, len(h)-1):  
	A.append(a*A[i-1] % m)  
	B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)  
  
A = A[1:]  
B = B[1:]

G = Matrix(ZZ,len(H),len(H))
for i in range(len[A]):
	G[i,i] = m
	G[-2,i] = A[i]
	G[-1.i] = B[i]

G[-2,-2] = 1
G[-1,-1] = 2^kbits
L=G.LLL()[0]
L1=L[-2]
print(L1)

总结

LCG也是让新手头疼的一部分，希望你看完我的文章之后能有新的收获，如果有问题的话欢迎指出，本人作为一名ctfer菜鸟，难免会有些小错误哒(๑´ڡ ‘๑)/。

参考

LCG | DexterJie’Blog