格密码与LLL入门

本文适合

CTF 密码学 入门学习者。学完你能：理解 格密码与LLL入门 的核心概念和基本用法

一句话判断

如果题目给出模方程、线性关系或多项式关系，并且未知量被承诺“很小、很短、很稀疏、只泄露部分位”，就要考虑把问题建成格，用 LLL 找短向量或近向量。

题目中常见信号

RSA 明文、素数或私钥只差一小段未知

说明：Coppersmith 小根

ECDSA/DSA nonce 泄露高位/低位

说明：Hidden Number Problem

背包/子集和，系数很多且解是 0/1

说明：格化子集和

LWE/NTRU、小噪声、多组线性方程

说明：CVP/SVP 或嵌入格

PRNG 输出被截断

说明：小误差恢复状态

直接爆破空间过大，但未知量有界

说明：格攻击候选

核心概念

LLL 不是万能破解器，它只是把一个整数格基约化得更短、更接近正交。CTF 中的关键是建模：把“目标解很短”或“误差很小”编码进格，使 LLL 输出里出现可验证的候选。

S 级分析必须写出：未知量是什么、界限是多少、方程是什么、格矩阵每一行代表什么，以及如何验证 LLL 输出。

最小分析流程

1. 先排除更简单路线：直接分解、gcd、低指数、重复 nonce。
2. 找小未知量：缺失位数、噪声范围、0/1 向量、截断位数。
3. 写出等式或同余式，并把未知量放到有界位置。
4. 选择 SVP、CVP、Coppersmith 或 HNP 建模。
5. 调整缩放因子，让短向量各维量级接近。
6. 对 LLL 输出逐个验证，不把短向量直接当答案。

最小验证示例

from sageall import Matrix, ZZ

# 子集和玩具例子：找 bits 使 sum(a_i * bit_i) = target
a = [3, 7, 11, 19]
target = 22
M = Matrix(ZZ, [
    [1, 0, 0, 0, a[0]],
    [0, 1, 0, 0, a[1]],
    [0, 0, 1, 0, a[2]],
    [0, 0, 0, 1, a[3]],
    [0, 0, 0, 0, -target],
])
for row in M.LLL():
    if row[-1] == 0:
        bits = list(row[:-1])
        if all(x in (0, 1, -1) for x in bits):
            print(row)

玩具矩阵只说明验证思路：真实背包要根据密度、目标位置和符号调整构造。

常见利用 / 解题路线

路线总览：

• Coppersmith：RSA 小根、部分已知素数或明文。
• HNP：ECDSA/DSA nonce 部分泄露或偏差。
• 子集和：低密度背包和 0/1 解。
• LWE/CVP：小噪声线性方程组。
• 截断 PRNG：把丢失低位/高位当小误差。

常见失败原因

LLL 输出全是无关短向量

排查动作：缩放不平衡，调整权重

没有候选满足验证

排查动作：未知量界限估错或方程方向错

Coppersmith 无根

排查动作：小根界限过大，减少未知位或增加关系

HNP 私钥不对

排查动作：nonce 泄露位方向、签名 hash 截断或模数写错

矩阵维度爆炸

排查动作：先用小样本验证建模，再扩展

迷你案例

RSA 题泄露 p 的高 900 位，低 124 位未知。设 p = p_high * 2^124 + x，其中 x < 2^124，并且 p | n。构造 f(x)=p_high*2^124+x 在模 n 下的小根问题，用 Coppersmith 找到 x，恢复 p，再算 q,d 解密。

这个 WP 的关键是写清未知量 x 的界限，而不是只写“用 Coppersmith”。