谁还有多余资金

必要基础：字节、取模、最大公约数和模逆#

1
"A" → 65
2
"B" → 66

1
m = bytes_to_long(flag)

1
m.to_bytes((m.bit_length() + 7) // 8, "big")

1
23 % 7

1
from math import gcd
2
assert gcd(21, 91) == 7

1
assert pow(5, -1, 17) == 7

如果完整的 t1 已知，flag 很容易恢复#

原题关系为：

两边乘以 $m+r_1$：

再乘以 $t_1^{-1}$：

因此：

对应代码：

1
m = (k * pow(t1, -1, p) - r1) % p

所以最后恢复 flag 的式子其实已经有了，问题就卡在这里：

题目只给了 $t_1,t_2$ 的高位，怎样补齐它们未知的低位？

不过先别急着补低位，模数 $p$ 还没拿到，先处理前面的 RSA。

先分解不平衡的 RSA 模数#

题目使用：

1
p = getPrime(1024)
2
q = getPrime(25)
3
N = p * q

这里的“位”是二进制位数：

$p$ 非常大，但 $q$ 只有几千万。整数分解不能只看 $N$ 的总位数：一个很小的素因子就可能成为突破口。

本题使用 Pollard rho 找到：

1
q = 23520857

于是：

1
p = N // q

恢复出的 $p$ 为：

1
141728564220215689105745310666761712438508810180329898864435481120368603802944433535439870033233448775648620641750653586896162186017744701345428383181658483867762748650405587002562099473480910200825070136353056453764908432415631471548522147066421239360596574292417840898610873956701534267841521331362184363411

知道 $p,q$ 后，正常计算 RSA 的欧拉函数和私钥：

再解密：

代码是：

1
d = pow(e, -1, (p - 1) * (q - 1))
2
message = pow(c, d, N)

结果转回字节得到：

1
Hurry up and go smelt copper!

这句话在提示 Coppersmith 相关方法。真正对后续攻击必需的是恢复出的 $p$；提示语本身不需要代入后面的方程。

Pollard rho：为什么不用知道因子也能制造碰撞#

Pollard rho 的原始思想来自 J. M. Pollard 的论文 A Monte Carlo Method for Factorization。这里用一组小数字把过程走一遍。

1
2 → 5 → 26 → 677 → 7474 → 2839 → 871 → …

1
2 → 5 → 26 → 95
2
    ↑         ↓
3
    └─────────┘

1
x = f(x)
2
y = f(f(y))
3
d = gcd(abs(x - y), N)

1
from math import gcd
2
from random import randrange
3

4
def pollard_rho(n):
5
    if n % 2 == 0:
6
        return 2
7

8
    while True:
9
        x = y = randrange(2, n)
10
        c = randrange(1, n)
11
        d = 1
12

13
        while d == 1:
14
            x = (x * x + c) % n
15
            y = (y * y + c) % n
16
            y = (y * y + c) % n
17
            d = gcd(abs(x - y), n)
18

19
        if 1 < d < n:
20
            return d
21
        # d == n：换一组起点和 c。

把高位泄漏写成两个小未知量#

先看一个小例子：

1
123 >> 4  # 7

对非负整数，右移 4 位等于整除 $2^4=16$：

如果只知道右移结果为 7，就可以写：

同样，由：

1
leak1 = t1 >> 244
2
leak2 = t2 >> 244

令：

得到：

其中：

$x,y$ 就是被丢弃的低位。244 位仍然无法暴力枚举，“小”是相对 1024 位的 $p$ 而言。

消掉 m：从三个未知量变成两个#

由原始模逆关系：

第一式乘 $t_2$：

第二式乘 $t_1$：

第二式减第一式，含 $m$ 的项抵消：

令：

则：

代入 $t_1=A+x,t_2=B+y$：

这里 $m$ 已经完全消失，只剩两个范围已知的小未知量。

归一化：得到双变量小根方程#

本题 $r_1\ne r_2$，且两者都远小于 $p$，因此 $\delta\not\equiv0\pmod p$，存在模逆。

定义：

方程变为：

逐项展开：

合并同类项：

取各系数模 $p$ 的整数代表元：

最终：

所谓 Bivariate 就是“双变量”：这里的两个变量是 $x,y$。

注意，当我们把 $\alpha,\beta,\gamma$ 选成普通整数后，$f$ 就是一个确定的整数多项式。它在真实根处的值可能是 $p$ 的非零倍数，而不是整数零。这一点正是后续攻击要解决的问题。

小例子一：用小数字核对消元过程#

暂时设：

于是：

模 101 下：

所以：

假设丢弃低 2 位：

因此：

继续计算：

得到：

对应多项式：

代入真实低位 $(2,2)$：

确实模 101 为零。

这组小数字先用来核对消元和正负号。后面再换一组参数，把格攻击也走一遍。

接下来要把模方程变成整数等式#

现在我们知道真实低位 $(x_0,y_0)$ 满足：

但这只表示：

这里 $\ell$ 是某个未知整数，表示它究竟是 $p$ 的多少倍。

直接求解这个模方程并不容易。我们希望找到几个新多项式：

使它们在真实根处满足：

作为普通整数等式成立。

格和 LLL 的作用，就是帮助找到这样的多项式。

格和基到底是什么#

1
(-2,6)   (0,6)   (2,6)   (4,6)
2
   •       •       •       •
3

4
(-2,3)   (0,3)   (2,3)   (4,3)
5
   •       •       •       •
6

7
(-2,0)   (0,0)   (2,0)   (4,0)
8
   •       •       •       •

LLL 在这道题里做了什么#

LLL 的名字来自 Lenstra、Lenstra、Lovász。其原始论文是 Factoring Polynomials with Rational Coefficients。

这里先把 LLL 的作用记成：

1
输入：一组整数基向量
2
输出：生成同一个格的一组较短的基向量

它主要通过减去其他基向量的整数倍、交换向量等操作，改善基的长度和方向关系。内部使用 Gram–Schmidt 正交化来衡量这些关系。

暂时先不展开完整的 LLL 算法证明，解这道题需要抓住下面几点：

1. 输出基生成的格与输入相同。
2. 输出向量仍是输入基的整数线性组合。
3. 寻找的是较短的非零向量，不保证每次找到真正的最短向量。
4. LLL 不认识 flag、RSA 或模逆；我们必须先设计好“短向量为什么有用”。

LLL 通常以欧氏长度衡量向量。例如：

后文还会用另一个容易计算的量——L1 范数：

两种范数不要混淆。我们使用 LLL 找较短向量，再对输出显式检查 L1 范数条件。

多项式为什么可以变成格向量#

本题只需要四种单项式：

固定这个顺序，多项式：

对应系数向量：

反过来：

对应：

因为顺序固定，所以可以准确来回转换。

更重要的是，多项式的加法和整数倍运算，与系数向量完全对应。例如：

则：

对应：

因此：

对向量做整数线性组合，等价于对对应的多项式做同样的整数线性组合。

这就是把代数方程放进格里的入口。

为什么选择 p、px、py、f 作为构造材料#

考虑四个整数多项式：

在真实根 $(x_0,y_0)$ 处，它们的值都能被 $p$ 整除：

• $p$ 本身当然可以。
• $px_0$、$py_0$ 显然可以。
• $f(x_0,y_0)$ 可以，因为我们已经建立了模方程。

因此，任意整数线性组合：

都满足：

这说明我们拥有一个很大的“候选多项式集合”，而且不管怎么做整数线性组合，整除性质都不会丢失。

四个多项式还恰好只涉及 $1,x,y,xy$ 四种单项式，使得后面能够用四维格表示，并用三条独立方程做线性化求解。

但仅有整除性质还不够。接下来要让某些组合在真实根处的值足够小。

为什么必须缩放：把未知量范围变成权重#

设：

系数小，不代表代入后的值小。即使 $g(x)=2x$ 的系数只有 2，当 $x=10^{100}$ 时，结果仍很大。

已知：

因此：

所以应该关注的不是未缩放向量：

而是：

这等价于记录 $g(Xu,Yv)$ 关于辅助变量 $u,v$ 的系数。真实根对应的 $u=x_0/X,v=y_0/Y$ 都位于 $[0,1)$，所以各项的大小容易控制。

辅助变量不需要实际求出来。这个说法只是解释缩放为何合理。

缩放把“根的范围”转化成“向量的权重”，让短向量真正对应代入值较小的多项式。

一行一行构造 4×4 格基#

按照单项式顺序 $(1,x,y,xy)$：

给四列分别乘：

得到格基矩阵：

这里每一行是一条基向量。这里把基向量按行放进矩阵。

这个格中的每个向量，都是四行的整数线性组合，因此对应某个：

所以它在真实根处仍然满足：

调用 LLL，就是希望找到加权系数较小的这类 $g$。

一个容易混淆的细节：矩阵里的 $pX$ 是多项式 $px$ 的 $x$ 系数 $p$ 再乘权重 $X$，并不是把某个未知的 $x_0$ 代入了矩阵。构造矩阵时不需要知道真实根。

最关键的证明：短向量如何产生整数等式#

设 LLL 输出一行：

除去列权重，对应整数多项式：

这些除法都是整除。因为输入格的第二列全部能被 $X$ 整除，第三列全部能被 $Y$ 整除，第四列全部能被 $XY$ 整除；整数行组合保留这些性质。

由根的范围：

得到：

如果显式检查发现：

那么同时有：

区间 $(-p,p)$ 内唯一的 $p$ 的整数倍是 0，因此：

例如，一个整数能被 101 整除，同时绝对值小于 101，那么它不可能是 $101,-101,202$，只能是 0。

这里就能看出，短向量为什么有用：它给出了一个足够小、同时又能被 $p$ 整除的整数，这个数只能是 0。把这几步连起来就是：

1
构造格：保留“在真实根处能被 p 整除”的性质
2
   ↓
3
LLL：寻找较短的加权系数向量
4
   ↓
5
检查 L1 范数 < p
6
   ↓
7
整除性质 + 大小限制
8
   ↓
9
得到精确的整数等式

LLL 不保证每一行都满足范数条件。代码必须检查，不符合的行不能直接当成整数零方程使用。

小例子二：完整跑通 4×4 格攻击#

第一组小例子用来检查模逆消元；现在换一组参数，完整演示格攻击。

已知：

以及：

这些范围当然可以直接枚举。这里刻意使用格，是为了把真实题目的每一步缩小到能看清的数字。

1
from fpylll import IntegerMatrix, LLL
2

3
p = 10007
4
X = Y = 4
5
alpha, beta, gamma = 100, 3000, 801
6

7
B = IntegerMatrix.from_matrix([
8
    [p, 0, 0, 0],
9
    [0, p * X, 0, 0],
10
    [0, 0, p * Y, 0],
11
    [gamma, alpha * X, beta * Y, X * Y],
12
])
13

14
LLL.reduction(B, delta=0.99)
15
weights = [1, X, Y, X * Y]
16

17
for i in range(B.nrows):
18
    vector = [int(B[i, j]) for j in range(B.ncols)]
19
    l1 = sum(abs(value) for value in vector)
20

21
    if l1 >= p:
22
        continue
23

24
    assert all(value % weight == 0
25
               for value, weight in zip(vector, weights))
26
    coefficients = [value // weight
27
                    for value, weight in zip(vector, weights)]
28

29
    print("加权向量：", vector)
30
    print("L1 范数：", l1)
31
    print("[常数项, x 系数, y 系数, xy 系数]：", coefficients)

为什么低 244 位算“小”：理解参数余量#

这一节是参数直觉，不是前面严格范数证明的替代品。

如果未知位数更多，$X,Y$ 更大，矩阵里的 $pX,pY,XY$ 都会变大，就更难找到满足 L1 范数小于 $p$ 的行。

对于三角矩阵，本题格基的行列式就是对角线乘积：

行列式的绝对值也可理解为一组基张成的基本区域的体积。二维时对应面积，高维是类似概念。它不直接等于最短向量长度，但能提供一个长度尺度。

对四维格，取四次方根：

希望这个体积尺度低于 $p$，启发式上得到：

即：

若 $X=Y$，则约为：

本题：

而：

每个变量范围比这个尺度小约 12 位，因此小规模格就有成功空间。

但必须区分两种结论：

• 严格成立的部分：若某行加权 L1 范数小于 $p$，对应多项式在真实根处严格等于零。
• 需要实际检查的部分：LLL 是否找到足够多这样的行，以及它们是否给出足够独立的方程。

不能仅根据行列式估计，就宣布任意同类双变量模方程都必然可解。单变量模小根、双变量整数小根和多变量模小根不是可以随意互换的定理场景。相关区别可参阅 Coron 的原始论文 Finding Small Roots of Bivariate Integer Polynomial Equations。

回到真实题目：得到三条独立整数方程#

真实参数虽然大，格的维度仍然只有 4。

按同样流程构造并约化后，得到三行满足严格条件的向量。加权 L1 范数的二进制位数为：

1
1008, 1009, 1011

$p$ 为 1024 位。这里不仅比较位数，代码还直接计算并检查了：

1
sum(abs(value) for value in vector) < p

因此对应三条多项式：

临时设 $z=xy$，得到：

本题这个矩阵可逆，即三条线性方程足够独立，因此有唯一解。

代码使用 fractions.Fraction 做精确有理数消元。不能将这些几百、上千位的整数转为普通浮点数后直接求解，否则会丢失精度。

实际恢复的低位：

1
x = 26935065816404425348087810146545330304118198184338416823761954915055210704
2

3
y = 3508779780900061165273789436142261523358634325843505345455544824287405353

并验证：

• $x,y,z$ 都是整数。
• $0\le x<X,0\le y<Y$。
• $z=xy$。
• 原始 $f(x,y)\equiv0\pmod p$。

这组参数下，无需计算 resultant 或 Gröbner basis，普通精确线性消元即可。

补齐模逆输出，恢复 flag#

既然低位已知：

代码是：

1
t1 = (leak1 << 244) + x
2
t2 = (leak2 << 244) + y

利用前面推导的公式：

恢复：

1
m = (k * pow(t1, -1, p) - r1) % p

另一个泄漏独立计算：

1
m2 = (k * pow(t2, -1, p) - r2) % p
2
assert m == m2

转换回字节：

1
flag = m.to_bytes((m.bit_length() + 7) // 8, "big")

结果为：

1
flag{H4hAHhhHh4_c0pP3r_N07_v1OI3n7_3n0uGh}

再回代原题：

1
assert t1 == k * pow(m + r1, -1, p) % p
2
assert t2 == k * pow(m + r2, -1, p) % p
3
assert t1 >> 244 == leak1
4
assert t2 >> 244 == leak2

这同时检查了两次完整模逆输出与原始高位泄漏。

严格说，泄漏只能恢复 $m\bmod p$。本题得到的是正常长度的 flag，其整数值小于 $p$，因此可以直接还原。如果允许任意长的消息，$m$ 与 $m+tp$ 会产生相同泄漏，不能仅凭这些关系无条件区分。

从题目到答案的完整路线#

1
N 中含 25 位小素因子
2
        ↓ Pollard rho
3
恢复 q，再计算 p=N/q
4
        ↓
5
解密 RSA 提示语（辅助理解题意）
6
        ↓
7
t1=A+x，t2=B+y，x、y 的范围已知
8
        ↓ 两条模逆关系交叉相减
9
消掉 m
10
        ↓ 乘 delta 的模逆
11
f(x,y)=xy+alpha*x+beta*y+gamma ≡ 0 mod p
12
        ↓
13
选择 p、px、py、f 四个多项式
14
        ↓ 按 1、X、Y、XY 加权
15
构造 4×4 整数格基
16
        ↓ LLL
17
得到较短的加权系数向量
18
        ↓ 检查 L1 范数 < p
19
产生三条严格的整数方程
20
        ↓ 暂时令 z=xy，精确消元
21
恢复 x、y，并检查 z=xy 与根范围
22
        ↓
23
补齐 t1、t2，逆运算得到 m
24
        ↓
25
转换为 flag，并回代全部泄漏关系