sekaictf趣题

碰到的最复杂的题，没有之一，但是研究下来还是蛮有意思的，对线性代数要求极高

题目

from Crypto.Util.number import getPrime, getRandomRange
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

FLAG = open('flag.txt','rb').read()

def lcg(a,b,p,x):
    while 1: yield (x := (a*x+next(b)) % p)

P, p = getPrime(256), getPrime(0x137)
X, A, B, a, b = [getRandomRange(0,m) for m in (P,P,p,p,p)]

# what's better than one lcg? TWO lcgs!
moons = lcg(a,iter([b]*14),p,B)
planets = lcg(A,moons,P,X)
orbit = [next(planets) for _ in range(14)]
star = AES.new(X.to_bytes(32),AES.MODE_ECB).encrypt(pad(FLAG,16)).hex()

print(f"{orbit = }")
print(f"{star = }")

'''
orbit = ......
star = ......
'''

分析

先放一张本次进攻总览：

先只看着外层差分 $\Delta$ 上的线性关系，用 LLL 抠出关系多项式 → 用 resultant 分离出内层模数 $p$、求根得 $a$ → 借助左核"钓"出内层差分 $dm$ → 再反哺外层差分，用同样的 gcd 手法抠出外层模数 $P$、回代得 $A$ → 最后用差分拼出 $m_1$，从而恢复 $X$。

题目的数学模型非常简单，就是一个双层lcg的问题

$$\begin{cases} m_{i+1} = (a \cdot m_i + b) \bmod p, & m_0 = B \quad \text{（内层，} p \text{ 为 311 bit 素数）} \\[4pt] o_{i+1} = (A \cdot o_i + m_{i+1}) \bmod P, & o_0 = X \quad \text{（外层，} P \text{ 为 256 bit 素数）} \end{cases}$$

我们已知：

$\text{orbit} = (o_1, \dots, o_{14})$（从 $o_1$ 开始，$X = o_0$ 不可见）

$\text{star}$（AES-ECB 密文，密钥 X.to_bytes(32)）

注意内层模数 $p$（311 bit）> 外层 $P$（256 bit），这是"差分能量化到整数零、从而能逐层剥开模数"的基础。不过靠的可不是"扰动小"——$dm$ 本身约 $2^{311}$，比 $P$ 还大 55 个 bit——而是后面 LLL 给出的关系系数足够短（实测约 94~96 bit）：

$$|\sum_j r_j\,dm_{i+j}|\le 11\cdot 2^{96}\cdot p\approx 2^{404}<pP\approx 2^{567}$$

和式比 $pP$ 小，“同余"才有资本升级成"整数零”，外层差分里的内层信息就是这样被干净剥离出来的。

恢复a，p

从差分入手，从这大量的线性关系一点一点扣出a，p出来

我们计算两层lcg的差分：

$$\Delta_i = o_{i+1} - o_i \quad (i=1,\dots,13)$$

$$dm_i = m_{i+1} - m_i \quad (i=0,1,\dots,13)$$

（$\Delta_0 = o_1 - o_0$ 要用到看不见的 $X$，扔掉不用。）

不难发现差分也是存在一层递推关系的（$i \ge 1$）：

$$\Delta_{i+1} \equiv A \cdot \Delta_i + dm_{i+1} \mod P$$

$$dm_{i+1} \equiv a \cdot dm_i \pmod{p}$$

一个差一位的细节：orbit[0] = o_1（$X = o_0$ 不可见），所以代码里 dy[k] = orbit[k+1] - orbit[k] = Δ_{k+1}——dy 和 Δ 整体错开一位。后文"$dx[i]$ 对应 $dm_{i+2}$"的下标错位，根源都在这里。

把 13 个 $dy$（也就是 $\Delta_1$ 到 $\Delta_{13}$）排成 3 个长度 11 的滑动窗口，堆成 $3 \times 11$ 整数矩阵：

$$Y = \begin{bmatrix} \Delta_1 & \Delta_2 & \cdots & \Delta_{11} \\ \Delta_2 & \Delta_3 & \cdots & \Delta_{12} \\ \Delta_3 & \Delta_4 & \cdots & \Delta_{13} \end{bmatrix}$$

维度账本：一个核向量 $r$ 就是一条对三个窗口同时精确成立的整系数关系 $\sum_j r_j \Delta_{i+j} = 0$；11 列减 3 行约束，右核维数 $= 11 - 3 = 8$。

我们对Y求右核同时LLL输出一个8行11列的基。为什么只留最短 6 条（代码里的 [:-2]）：实测（玩具参数、真值数据、多个随机种子）8 条里最短的 6 条全部满足 $R(a)\equiv 0 \pmod p$，而最长的 2 条不满足——好关系集中在 LLL 输出的短端，丢掉最长的 2 条是最便宜的容错。这 6 条基向量反映了$\Delta_i$间的线性关系，下面就从线性关系里面分离出有用信息

由此我们来回代一下我们找出的关系系数：

$$0 = A \underbrace{\sum_j r_j \, \Delta_{i+j}}_{=\,(Y r)_i \,=\, 0} - \underbrace{\sum_j r_j \, \Delta_{i+1+j}}_{=\,(Y r)_{i+1} \,=\, 0} + \sum_j r_j \, dm_{i+1+j}$$

$$\sum_j r_j \, dm_{i+1+j} = 0$$

$$dm_{i+1+j} \equiv a^j \cdot dm_{i+1} \pmod{p}$$

代入前式，由 $dm_{i+1} \not\equiv 0 \pmod{p}$（内层差分非零，可约去）：

$$\sum_j r_j \, a^j \equiv 0 \pmod{p}$$

所以我们构造多项式：

$$R(x) = r_0 + r_1 x + \dots + r_{10} x^{10}$$

(输出6组$R_i(x)$)

我们有

$$R_i(a) = 0$$

手握 ≥ 3 条好关系多项式 $R_0, R_1, R_2$，它们在模 $p$ 下有公共根 $a$

$$p \mid \gcd\Big( \operatorname{Res}(R_0, R_1),\ \operatorname{Res}(R_1, R_2) \Big)$$

p由此求出
再由多项式求根找出a
至此内层参数全部恢复

恢复dm

$$M = \begin{bmatrix} r^{(0)}_0 & \cdots & r^{(0)}_{10} & 0 \\ 0 & r^{(0)}_0 & \cdots & r^{(0)}_{10} \\ r^{(1)}_0 & \cdots & r^{(1)}_{10} & 0 \\ 0 & r^{(1)}_0 & \cdots & r^{(1)}_{10} \\ \vdots & & & \vdots \end{bmatrix} \quad \text{（6 条关系 } \times \text{ 2 个平移 = 12 行）}$$

$M$ 的维度账本：$12 \times 12$ 但不满秩——实测 $\operatorname{rank}(M) = 9$，右核维数 $= 12 - 9 = 3$（rkm2 就是这 3 维解空间的 LLL 短基，所以是 $3\times 12$）。这个 3 维解空间就是下一步左核钓鱼的舞台。

配平系数

继续做一个求解右核,同时配平系数，将我们求解的结果放大为真实的dx

rkm2 = M.right_kernel_matrix().LLL()        # 3×12，解空间的短基
k = ZZ(rkm2.solve_left(dy[1:])[2])          # dy[1:] 在基下的第 3 个坐标
rkm2 *= k

求出 $dy[1{:}]$ 在这组基下的坐标 $(c_0, c_1, c_2)$。取 $c_2$（记作 $k$）把整个基放大 $k$ 倍——效果是把基的尺度对齐到真实数据的量级。

这一步不是锦上添花，是生死线：后面恢复 $P$ 的时候要求 $dx = dm$ 严格成立。要是 $dx$ 差个 $c \neq 1$ 倍，就有 $t_i \equiv A\cdot dy_i + (1-c)\,dm_{i+2} \pmod P$，gcd 什么都抠不出来。

取第 3 个坐标是启发式选择：拿已知成员 $dy[1{:}]$ 的坐标去钉基底的绝对尺度。实测这么校准之后，钓出来的序列恰好就是真 $dm$ 本身（比值恒为 1），不多不少。

左核钓鱼

这里是我认为最有趣的部分

再堆一个矩阵：

$$N=\begin{bmatrix}\;\mathbf{B}_{2}\;\\[2pt]\;\mathbf{B}_{1}\;\\[2pt]\;\mathbf{B}_{0}\;\\[2pt]\;\boldsymbol{\alpha}\;\end{bmatrix} =\begin{bmatrix} b_{2,0} & b_{2,1} & b_{2,2} & \cdots & b_{2,11}\\[2pt] b_{1,0} & b_{1,1} & b_{1,2} & \cdots & b_{1,11}\\[2pt] b_{0,0} & b_{0,1} & b_{0,2} & \cdots & b_{0,11}\\[2pt] 1 & a & a^{2} & \cdots & a^{11} \end{bmatrix}_{4\times 12}\quad\text{（模 }p\text{，即 }\mathrm{GF}(p)\text{ 上）}$$

其中前三行是解空间基 $\mathbf{B}=\mathrm{rkm}2$ 的倒序（对应 rkm2[::-1]），末行是等比向量 $\boldsymbol{\alpha}=(1,a,a^{2},\dots,a^{11})$

这个矩阵向量构成的空间里包含着所有满足那 6 条递推关系的序列。

dy[1:]（已知，即 $\Delta_2$ 到 $\Delta_{13}$）和 $dm_2,\dots,dm_{13}$（我们想求的，注意起点是 $dm_2$，对应后文的 $dx[i] = dm_{i+2}$）都住在这个空间里。

我们求解左核

左核向量 $\ell = (\ell_0, \ell_1, \ell_2, \ell_3)$ 满足 $\ell \cdot N \equiv 0 \pmod p$，按行展开（注意 $N$ 的前三行是基的倒序）：

$$\ell_0 \cdot \mathrm{rkm2}[2] + \ell_1 \cdot \mathrm{rkm2}[1] + \ell_2 \cdot \mathrm{rkm2}[0] \equiv -\ell_3 \cdot \alpha \pmod{p}$$

我们观察这个式子：
左边是基的一个具体线性组合,右边是这个目标向量的方向特征

而我们的目标向量：dm 也恰好同时满足两个式子——它既在解空间里（满足全部递推），又与 α 平行（模 p 等比）

这个组合结果恰好就是我们要的 dm（差个常数倍）！

（代码里 M.left_kernel_matrix()[0, 2::-1] 只取了左核的第一个基向量——左核是高维的，但前面"既在解空间、又与 $\alpha$ 平行"这两个约束已把方向唯一确定，其余向量只是冗余。）

恢复A,P

恢复P

有了 $dx$（= $dm$ 序列）后，由 (3)：

$$t_i = dy_{i+1} - dx_i \equiv A \cdot dy_i \pmod{P}$$

完全套用前面恢复 $p$ 的 gcd 手法（把 $dy$ 当作已知序列、$t$ 当作它的"公比 $A$ 像"）：

$$P \mid \gcd\Big( dy_0 \cdot t_1 - dy_1 \cdot t_0, \;\; dy_1 \cdot t_2 - dy_2 \cdot t_1 \Big)$$

由此得出P

回代：A → m₁ → X

在模 $P$ 下进行（注意恢复 $dm$ 一节的下标错位：$dx[i] = dm_{i+2}$——就是前面说的 dy 与 Δ 错开一位的后果）：

$$\begin{aligned} A &\equiv \frac{dy_1 - dx_0}{dy_0} \pmod{P} \\ dm_1 &\equiv \frac{dx_0}{a} \pmod{p} \\ m_2 &\equiv o_2 - A \cdot o_1 \pmod{P} \\ m_1 &\equiv m_2 - dm_1 \pmod{P} \\ X &\equiv \frac{o_1 - m_1}{A} \pmod{P} \end{aligned}$$

还有一点：

$dx[0] \equiv a \cdot dm_1 \pmod{p}$，所以用模逆元计算：
$\mu \equiv dx[0] \cdot a^{-1} \pmod{p},\ 0 \le \mu < p$。
这个 $\mu$ 是 $dm_1$ 在模 $p$ 下的非负代表。
所以真实的$dm_1$由两种情况：$\mu$（非负），$\mu-p$（负数）

exp

贴之前补两个有意思的点：

一是整个攻击从头到尾都没恢复 $b$ 和 $B$——差分把 $b$ 消了，$X$ 又只依赖 $m_1$，七个秘密参数里这两个压根没出过场。

二是 exp 开头那行 exec(open('chall.py','r').read().split("'''")[1])，是直接把题目文件注释块里的 orbit/star exec 出来，省得手抄数据。

贴一下官方的exp吧，写不动了

from Crypto.Cipher import AES

exec(open('chall.py','r').read().split("'''")[1])

dy = vector(orbit[1:]) - vector(orbit[:-1])

Y = matrix(ZZ,3,11)
for i in range(3):
    Y[i] = vector(dy[i:i+11])

rkm = Y.right_kernel_matrix().LLL()[:-2]
R.<x> = PolynomialRing(ZZ)

poly0 = sum([rkm[0,i]*x**i for i in range(11)])
poly1 = sum([rkm[1,i]*x**i for i in range(11)])
poly2 = sum([rkm[2,i]*x**i for i in range(11)])

res0 = poly0.resultant(poly1)
res1 = poly1.resultant(poly2)
p = gcd(res0,res1).factor()[-1][0]

poly0 = poly0.change_ring(GF(p))
poly1 = poly1.change_ring(GF(p))
a = gcd(poly0,poly1).roots()[0][0]

M = matrix(0,12)
for row in rkm:
    M = M.stack(matrix([0]+list(row)))
    M = M.stack(matrix(list(row)+[0]))

rkm2 = M.right_kernel_matrix().LLL()
k = ZZ(rkm2.solve_left(dy[1:])[2])
rkm2 *= k

M = rkm2[::-1].stack(vector(a**i for i in range(len(dy)-1)))
dx = vector(M.left_kernel_matrix()[0, 2::-1]).lift_centered()*rkm2

gcd_a = dy[0]*(dy[2]-dx[1])-dy[1]*(dy[1]-dx[0])
gcd_b = dy[1]*(dy[3]-dx[2])-dy[2]*(dy[2]-dx[1])
P = gcd(gcd_a,gcd_b).factor()[-1][0]

A = mod((dy[1]-dx[0])/dy[0],P)
X = orbit[0]-(dy[0]-mod(ZZ(mod(dx[0]/a,p))-p,P))/A
flag = AES.new(X.to_bytes(),AES.MODE_ECB).decrypt(bytes.fromhex(star))
if not flag.isascii():
    X = orbit[0]-(dy[0]-mod(mod(dx[0]/a,p),P))/A
    flag = AES.new(X.to_bytes(),AES.MODE_ECB).decrypt(bytes.fromhex(star))

print(flag.decode()) # SEKAI{orbital_strike_like_miku_miku_beam!!!}