格攻击案例专题

枫桥2025/10/7大约 7 分钟

格攻击案例专题

本文适合

已经读过格密码与LLL入门、RSA基本概念和基础 SageMath 的密码学方向学习者。学完你能：把“可能用 LLL”的直觉落到背包、RSA 部分泄露、nonce 偏差、近似公约数和截断 PRNG 等 CTF 题型上，并写出可验证的最小求解脚本

一句话判断

题目里出现“大整数线性组合、模方程、小未知量、部分泄露、带误差样本、截断输出”，并且暴力不可行但未知量有明确上界时，就要考虑格攻击。

格攻击不是“看到大数就 LLL”。它的核心判断是：能不能把题目关系写成短向量、小根、近似线性关系或有界误差问题。

题目中常见信号

常见材料：

a1, a2, ..., an, target
n, e, c, p_high / p_low
(r, s, h) signatures
xi = qi * p + ri
truncated random outputs

高频暗示：

high bits、low bits、partial key、known prefix。
nonce、k、biased random、leaked bits。
多个样本共享同一个秘密。
未知量很小，或者只剩几十到几百 bit。
直接 gcd、Fermat、Wiener、爆破都不够。

做题时先写两列：

已知量

作用：题目直接给出的数、签名、密文、输出

小未知量

作用：泄露缺口、误差、选择位、截断低位/高位

约束关系

作用：等式、模方程、线性组合、范围边界

验证方式

作用：回代、解密、验签、重放 PRNG

核心概念

格攻击的共同目标是把“正确答案”变成格中的短向量或多项式的小根。

CTF 入门阶段最常见的是这些形态：

子集和 / 背包：未知量是 0/1 选择位。
RSA 部分泄露：未知量是 p、q、d、padding 或明文中的缺失部分。
ECDSA / DSA nonce 偏差：未知量是多个签名 nonce 的小误差或泄露位。
近似公约数：多个样本共享隐藏因子，但每个样本带小噪声。
截断 PRNG：状态转移线性，输出只泄露高位或低位。

LLL 的作用不是“直接解题”，而是把构造好的格规约出短向量。真正难点通常在构造：

题目关系 -> 有界未知量 -> 缩放 -> 格矩阵 -> LLL -> 候选解 -> 回代验证

最小分析流程

1. 先排除更简单的攻击

RSA 题先跑：

from math import gcd, isqrt

print(gcd(n1, n2))          # 共因子
print(isqrt(n))             # 接近平方时考虑 Fermat

签名题先看：

seen = {}
for r, s, h in sigs:
    if r in seen:
        print("nonce reuse", r)
    seen[r] = (s, h)

如果简单攻击能解，不要强行上格。

2. 找小未知量和边界

把未知量写成：

x < 2^k
ri < B
ki = known_part + xi
m = prefix || x || suffix

没有边界，格很难构造；边界估错，LLL 也会给你看起来很短但无法回代的垃圾向量。

3. 写出数学关系

不要直接写 Sage。先写纸面关系，例如 RSA 低位泄露：

p = p0 + x
p * q = n
x < 2^unknown_bits

ECDSA nonce 部分泄露：

s_i * k_i - h_i = r_i * d mod q
k_i = known_i + x_i
|x_i| < B

4. 构造格并保留验证函数

Sage 里最小骨架：

M = Matrix(ZZ, rows)
L = M.LLL()
for v in L:
    cand = recover_candidate(v)
    if verify(cand):
        print(cand)
        break

verify() 必须独立于 LLL，负责回代题目原始条件。

5. 迭代缩放和样本数量

如果没有结果，先调：

样本数量。
缩放因子。
未知量边界。
行列顺序。
是否需要中心化误差。

不要只把同一个矩阵反复跑。

最小验证示例

背包题验证骨架

题目给：

a = [ ... ]
target = ...

验证函数先写出来：

def verify(bits):
    return all(b in (0, 1) for b in bits) and sum(x*b for x, b in zip(a, bits)) == target

LLL 得到候选向量后，只接受能通过 verify() 的结果：

for row in L:
    bits = [int(abs(x)) for x in row[:len(a)]]
    if verify(bits):
        print("bits =", bits)
        break

这个示例的重点不是固定矩阵模板，而是养成习惯：短向量必须回代验证。

RSA 部分泄露验证骨架

如果猜测恢复了 p：

def verify_p(p):
    return p > 1 and n % p == 0

if verify_p(p):
    q = n // p
    phi = (p - 1) * (q - 1)
    d = inverse_mod(e, phi)
    m = pow(c, d, n)
    print(long_to_bytes(int(m)))

成功标准不是 LLL 输出了一个小数，而是能分解 n 并正确解密。

常见利用 / 解题路线

路线总览：

路线一：子集和 / 背包

适合：

明文 bit 直接控制求和。
数组长度中等。
目标和已知。

步骤：

把选择位写成 0/1 未知量。
构造包含 target 的格。
LLL 后从短向量读候选 bit。
回代 sum(ai*bi) == target。
把 bit 转回字符串或密钥。

路线二：RSA 部分泄露

适合：

泄露 p 的高位或低位。
p 和 q 结构相近。
明文或 padding 只有少量未知字节。

步骤：

写出 p = known + x 或 m = known + x。
确定 x 的上界。
转成小根问题或构造对应格。
得到候选后分解或解密。

关联：RSA基本概念。

路线三：ECDSA / DSA nonce 偏差

适合：

给很多签名 (r, s)。
nonce 高位、低位或范围泄露。
随机数生成器有偏差。

步骤：

写出签名方程。
把 k_i 拆成已知部分和小误差。
用多组签名构造格。
恢复私钥 d。
用公钥或新签名验证。

关联：签名算法与nonce复用、ECC基础。

路线四：近似公约数

适合：

xi = qi * p + ri

其中多个 xi 共享秘密 p，误差 ri 很小。

步骤：

估计误差上界。
构造让误差成为短向量的格。
恢复候选 p。
检查所有样本对 p 取模后是否都很小。

路线五：截断 PRNG

适合：

LCG、LFSR 或线性状态转移。
输出高位/低位被截断。
有连续样本。

步骤：

写出状态转移公式。
把缺失位设为小未知量。
用连续输出建立方程。
通过格恢复状态或缺失位。
预测下一次输出。

关联：随机数与种子、流密码与LFSR。

常见失败原因

没有先排除简单攻击：共因子、Fermat、Wiener、nonce 复用可能一步解决。
未知量边界乱估：边界太大导致短向量不突出，太小会排除真解。
缩放不合理：不同列量级差太多，LLL 优先优化了错误方向。
样本太少：nonce 偏差和截断 PRNG 常需要足够多样本。
不回代验证：短向量看起来像答案，但无法满足原题方程。
符号和模数写错：签名方程里的 s^-1、r、h 顺序错一个就全错。
把格密码和格攻击混在一起：后量子格算法不等于所有题都能套同一个 LLL 模板。

迷你案例

题目给一个简化背包：

a = [210, 311, 470, 889, 1201, 1543]
target = 210 + 470 + 1543

目标是恢复选择位。

第一步写验证：

a = [210, 311, 470, 889, 1201, 1543]
target = 2223

def verify(bits):
    return sum(x*b for x, b in zip(a, bits)) == target

第二步，LLL 或枚举得到候选：

bits = [1, 0, 1, 0, 0, 1]
print(verify(bits))

输出：

True

第三步，写入 WP 时不要只说“LLL 解出”。要说明：

题目信号：大整数数组 + target + 0/1 选择
小未知量：每个 bi 属于 {0,1}
验证条件：sum(ai*bi) == target
结果：选中第 1、3、6 个元素

真实比赛题的数字会更大，暴力不可行，但分析闭环相同：识别线性关系，构造格，回代验证。