LCG是一种常用的伪随机数生成算法。LCG是一种常用的伪随机数生成算法
一、LCG 算法基本原理
1.核心公式
LCG（线性同余生成器）生成序列使用如下公式：
eₙ₊₁ = (a * eₙ + b) mod m
2.伪随机特性
序列具有周期性，周期长度与a、b、m相关。
满足Hull-Dobell准则时周期最大化，a-1是m所有质因子的数，b与m互质。
二、LCG参数破解方法
1. 模数m的恢复
利用差分性质构造方程。
定义差分tn=eₙ₊₁-eₙ
则tn₊₁-tn=(a-1)*tn mod m
通过以下公式计算m的候选值。
def compute_m(x):
diffs = []
for i in range(2):
t = (x[i+2]-x[i+1])**2 - (x[i+3]-x[i+2])*(x[i+1]-x[i])
diffs.append(abs(t))
return reduce(gcd, diffs)//计算结果为m的倍数，通过GCD提取m。2. 乘数a与增量b的计算
利用前三项建立方程组。
x₁=(a*x₀+b)mod m
x₂=(a*x₁+b)mod m
消去b。
a=(x₂-x₁)*(x₁-x₀)⁻¹mod m
(x₁-x₀)⁻¹为模m的乘法逆元，通过扩展欧几里得算法求解。
代入求b。
b=(x₁-a*x₀)mod m
3. 初始种子恢复
eₙ=(eₙ₊₁-b)*a⁻¹mod m //逆向公式
e₀=(x₀-b)*a⁻¹mod m //初始种子
三、CTF实例——H&NCTF lcgn
1. 题目条件
生成5个随机数：x=[x₀, x₁, x₂, x₃, x₄]
a、b为256位素数，m为2048位素数。
2. 代码
from math import gcd
from functools import reduce
from Crypto.Util.number import inverse
x = [ 11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, ... 10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074]# 恢复模数m
def compute_m(x):
diffs = []
for i in range(2):
t = (x[i+2]-x[i+1])** 2 - (x[i+3]-x[i+2])*(x[i+1]-x[i])
diffs.append(abs(t))
return reduce(gcd, diffs)
m = compute_m(x)
a = ((x[2]-x[1]) * inverse(x[1]-x[0], m)) % m
b = (x[1] - a * x[0]) % m
c = ((x[0] - b) * inverse(a, m)) % m
print(f"m = {m}")
print(f"a = {a}")
print(f"b = {b}")
print(f"c = {c}")四、具体分析
1.算法缺陷
线性结构导致差分关系可预测。
参数选取不当时周期过短（如m非大素数）。
种子与加密信息相关时（如c=pow(e, flag, n)）易被逆向。
2.条件
使用LCG需满足：m为2048位以上大素数,a-1是m所有质因子的倍数,b与m互质。
作者：SD9ard3n
编辑：石可可