CTF BUUOJ [NewStarCTF 公开赛赛道]LCG Revenge Writeup
题目信息
- 题目名称：LCG Revenge
- 题目标签：Crypto, LCG
- 题目描述：LCG, 但是三阶
- 题目文件：
- task.py：加密脚本
- output.txt：输出文件
题目分析
这一题是经典的线性同余生成器（LCG）的变体。普通的 LCG 通常形式为 xn+1=(a⋅xn+b)(modp)x_{n+1} = (a \\cdot x_n + b) \\pmod pxn+1=(a⋅xn+b)(modp)，而本题将其扩展到了三阶，即新的状态由前三个状态线性组合而成。
让我们先看看加密脚本 task.py 的核心逻辑：
from Crypto.Util.number import *
from secret import FLAG
p = getPrime(128)
step = len(FLAG) // 3
# 将 FLAG 分成三部分，转换为整数作为初始状态
xs = [bytes_to_long(FLAG[:step]), bytes_to_long(FLAG[step:2*step]), bytes_to_long(FLAG[2*step:])]
# 三个乘数因子
a = 18038175596386287827
b = 15503291946093443851
c = 17270168560153510007
p = 307956849617421078439840909609638388517
# 进行 10 轮状态更新
for _ in range(10):
new_state = (a*xs[0] + b*xs[1] + c*xs[2]) % p
xs = xs[1:] + [new_state]
print(xs)
print(a, b, c, p)
以及 output.txt 的内容：
[255290883651191064919890629542861653873, 221128501895959214555166046983862519384, 108104020183858879999084358722168548984]
18038175596386287827 15503291946093443851 17270168560153510007 307956849617421078439840909609638388517
已知条件：
目标：
恢复初始的 xsxsxs，从而还原 FLAG。
解题思路
数学推导
题目中的状态更新公式如下：
xnew=(a⋅xs[0]+b⋅xs[1]+c⋅xs[2])(modp) x_{new} = (a \\cdot xs[0] + b \\cdot xs[1] + c \\cdot xs[2]) \\pmod p xnew=(a⋅xs[0]+b⋅xs[1]+c⋅xs[2])(modp)
随后列表更新为 xs = xs[1:] + [new_state]。
这意味着如果我们当前的状态是 [A,B,C][A, B, C][A,B,C]，那么：
在这个方程中，A,B,CA, B, CA,B,C 都是已知的（即输出文件中的最终状态），系数 a,b,ca, b, ca,b,c 也是已知的。唯一的未知数是上一轮的第一个状态 OldOldOld。
我们可以将方程变形来求解 OldOldOld：
a⋅Old=C−(b⋅A+c⋅B)(modp) a \\cdot Old = C – (b \\cdot A + c \\cdot B) \\pmod p a⋅Old=C−(b⋅A+c⋅B)(modp)
Old=a−1⋅(C−b⋅A−c⋅B)(modp) Old = a^{-1} \\cdot (C – b \\cdot A – c \\cdot B) \\pmod p Old=a−1⋅(C−b⋅A−c⋅B)(modp)
其中 a−1a^{-1}a−1 是 aaa 在模 ppp 下的逆元。这本质上是一个线性代数问题，通过逆推矩阵或者简单的代数变换即可求解。
逆推流程
既然我们可以通过当前状态 [x0,x1,x2][x_0, x_1, x_2][x0,x1,x2] 推导出上一轮的状态，那么我们只需要将这个过程重复 10 次，即可回溯到初始状态。
解题脚本
根据上述推导，编写 Python 脚本如下：
from Crypto.Util.number import long_to_bytes
# 题目给出的已知参数
a = 18038175596386287827
b = 15503291946093443851
c = 17270168560153510007
p = 307956849617421078439840909609638388517
# 最终的状态
xs = [
255290883651191064919890629542861653873,
221128501895959214555166046983862519384,
108104020183858879999084358722168548984
]
# 计算 a 的逆元
# Python 3.8+ 可以直接使用 pow(a, -1, p)
a_inv = pow(a, –1, p)
# 进行 10 轮逆推
for _ in range(10):
# 当前状态 xs = [x0, x1, x2]
# 我们想求上一轮的 x_prev
# x2 = a*x_prev + b*x0 + c*x1
# x_prev = a_inv * (x2 – b*x0 – c*x1)
val = (xs[2] – b*xs[0] – c*xs[1]) % p
x_prev = (a_inv * val) % p
# 更新状态，将计算出的前一轮状态插到列表头部
xs = [x_prev, xs[0], xs[1]]
# 此时的 xs 即为初始状态
flag_parts = [long_to_bytes(x) for x in xs]
flag = b''.join(flag_parts)
print(flag.decode())
运行脚本，输出结果：
flag{try_some_linear_algebra_technique}
总结
本题虽然名为 “Revenge” 且引入了三阶 LCG 的概念，但核心考点依然是 LCG 的可逆性。只要系数 aaa 和模数 ppp 已知，且 aaa 与 ppp 互素（本题中成立），我们就可以通过计算模逆元轻松回溯状态。
题目描述中的提示 “try some linear algebra technique” 也暗示了这本质上是一个求解线性方程组的问题。对于更高阶的 LCG 或者未知系数的情况，通常需要构造矩阵并利用 LLL 算法或高斯消元法来解决，但在本题已知所有参数的情况下，简单的代数逆推足矣。
