lattice-crypto-attacks

技能：基于格的密码分析——专家攻击手册

AI 加载指令：适用于 CTF 和密码分析的专家级格技术。涵盖 LLL/BKZ 规约、Coppersmith 方法（单变量和多变量）、用于恢复 DSA/ECDSA nonce 的隐藏数问题、背包攻击和 NTRU 分析。基础模型通常无法构造正确的攻击格（维度错误、缺少缩放因子），或会错误应用 Coppersmith 界限。

0. 相关路由

• rsa-attack-techniques：适用于使用格方法的 RSA 专项攻击（Coppersmith、Boneh-Durfee）
• symmetric-cipher-attacks：适用于通过格恢复 LCG 状态
• classical-cipher-analysis：适用于格方法可用于古典密码分析的情况

快速应用指南

问题类型	格技术	关键参数
RSA 小根	Coppersmith（在多项式格上使用 LLL）	根界限 X < N^(1/e)
RSA 小 d	Boneh-Durfee（多变量 Coppersmith）	d < N^0.292
DSA/ECDSA nonce 偏差	隐藏数问题 → CVP	已知的偏差位数
背包密码	低密度格攻击	密度 < 0.9408
LCG 截断输出	在递推格上使用 CVP	每个输出的未知位数
子集和	在背包格上使用 LLL 规约	元素大小与数量
NTRU 密钥恢复	在 NTRU 格上进行格规约	维度和密钥大小

---

1. 格基础知识

1.1 定义

格 L 是所有基向量的整数线性组合构成的集合：

L = { a₁·b₁ + a₂·b₂ + ... + aₙ·bₙ | aᵢ ∈ ℤ }

其中 b₁, ..., bₙ 是 ℝᵐ 中线性无关的向量。

关键问题：

• SVP（最短向量问题）：求 L 中最短的非零向量
• CVP（最近向量问题）：给定目标 t，求 L 中距离 t 最近的 v
• SVP 在一般情况下是 NP-hard，但 LLL 能在多项式时间内找到近似短向量

1.2 格质量指标

Determinant: det(L) = |det(B)| where B is the basis matrix
Gaussian heuristic: shortest vector ≈ √(n/(2πe)) · det(L)^(1/n)

---

2. LLL 算法

2.1 LLL 的作用

输入格基 B，并生成规约基 B'，使其满足：

• 向量近似正交
• 第一个向量近似较短（与 SVP 的近似因子在 2^((n-1)/2) 以内）
• 多项式时间运行：O(n^5 · d · log³ B)，其中 d = 维度，B = 最大元素大小

2.2 SageMath 用法

# SageMath
M = matrix(ZZ, [
    [1, 0, 0, large_value_1],
    [0, 1, 0, large_value_2],
    [0, 0, 1, large_value_3],
    [0, 0, 0, modulus],
])

L = M.LLL()
# Short vectors in L reveal the solution
short_vector = L[0]  # first row is typically shortest

2.3 Python（fpylll）

from fpylll import IntegerMatrix, LLL

n = 4
A = IntegerMatrix(n, n)
# Fill matrix A...
A[0] = (1, 0, 0, large_value_1)
A[1] = (0, 1, 0, large_value_2)
A[2] = (0, 0, 1, large_value_3)
A[3] = (0, 0, 0, modulus)

LLL.reduction(A)
print(A[0])  # shortest vector

---

3. BKZ（分块 Korkine-Zolotarev 算法）

3.1 与 LLL 的比较

属性	LLL	BKZ-β
质量	2^((n-1)/2) 近似	2^(n/(β-1)) 近似
速度	多项式	关于 β 指数增长
分块大小	固定（2）	可配置 β
最适用场景	快速规约	高质量规约

3.2 用法

# SageMath
M = matrix(ZZ, [...])
L = M.BKZ(block_size=20)  # β = 20

# fpylll
from fpylll import BKZ
BKZ.reduction(A, BKZ.Param(block_size=20))

经验法则：先使用 LLL，如有需要再改用 BKZ。对于 CTF，BKZ 分块大小为 20-40 通常就足够了。

---

4. Coppersmith 方法

4.1 单变量情形

给定 f(x) ≡ 0 (mod N)，且存在小根 |x₀| < X，求 x₀。

界限：X < N^(1/d)，其中 d 为 f 的次数。

# SageMath — built-in small_roots
N = ...
R.<x> = PolynomialRing(Zmod(N))
f = x^3 + a*x^2 + b*x + c  # known polynomial
roots = f.small_roots(X=2^100, beta=1.0, epsilon=1/30)

参数：

• X：根的上界
• beta：N = p^beta（对于 N 本身的模根，beta=1.0；对于未知因子 p ≈ √N 的模根，beta=0.5）
• epsilon：值越小，结果越好，但速度越慢（尝试 1/30 到 1/100）

4.2 模板消息攻击（RSA）

# SageMath
n, e, c = ...  # RSA parameters
known_msb = ...  # known upper portion of message

R.<x> = PolynomialRing(Zmod(n))
f = (known_msb + x)^e - c

# x represents the unknown lower bits
X = 2^(unknown_bit_count)
roots = f.small_roots(X=X, beta=1.0)
if roots:
    m = known_msb + int(roots[0])

4.3 部分密钥泄露（因子 p）

已知 p 的 MSB：p = p_known + x，其中 x 较小。

# SageMath
n = ...
p_known = ...  # known upper bits of p

R.<x> = PolynomialRing(Zmod(n))
f = p_known + x
roots = f.small_roots(X=2^unknown_bits, beta=0.5)
# beta=0.5 because p ≈ √n
if roots:
    p = p_known + int(roots[0])
    q = n // p

4.4 多变量 Coppersmith（Howgrave-Graham）

对于 f(x, y) ≡ 0 (mod N)：

• 不保证存在多项式时间算法
• 启发式方法在实践中有效
• 用于 Boneh-Durfee RSA 小 d 攻击

# SageMath — Boneh-Durfee
# e*d ≡ 1 (mod phi) where phi = (p-1)(q-1)
# Rewrite: e*d = 1 + k*((n+1) - (p+q))
# Let x = k, y = (p+q), both small relative to n

R.<x, y> = PolynomialRing(ZZ)
A = (n + 1) // 2
f = 1 + x * (A + y)  # mod e

# Build shift polynomials and construct lattice
# Apply LLL to find small (x₀, y₀)

---

5. 隐藏数问题（HNP）——DSA/ECDSA nonce 恢复

5.1 问题描述

已知：签名 (rᵢ, sᵢ)，其中 nonce kᵢ 带有已知偏差（泄露了 MSB 或 LSB）。

DSA 方程：s = k⁻¹(H(m) + xr) mod q

重排得：k = s⁻¹(H(m) + xr) mod q

如果已知 k 的部分位：可转化为格上的 CVP。

5.2 攻击设置

# SageMath
def ecdsa_nonce_attack(signatures, q, known_bits, bit_position='msb'):
    """
    signatures: list of (r, s, hash, known_nonce_bits)
    q: curve order
    known_bits: number of known bits per nonce
    """
    n = len(signatures)

    # Build lattice
    B = 2^(q.nbits() - known_bits)  # bound on unknown part
    M = matrix(QQ, n + 2, n + 2)

    for i in range(n):
        r_i, s_i, h_i, a_i = signatures[i]
        t_i = Integer(inverse_mod(s_i, q) * r_i % q)
        u_i = Integer(inverse_mod(s_i, q) * h_i % q)

        M[i, i] = q
        M[n, i] = t_i
        M[n+1, i] = u_i - a_i  # a_i = known nonce bits

    M[n, n] = B / q
    M[n+1, n+1] = B

    # LLL reduction
    L = M.LLL()

    # Find row containing the private key x
    for row in L:
        x_candidate = Integer(row[n] * q / B) % q
        # Verify x_candidate against one signature
        if verify_private_key(x_candidate, signatures[0], q):
            return x_candidate

    return None

5.3 常见的 Nonce 偏差来源

来源	泄露位数	所需签名数
MSB 偏差（始终为 0）	1 位	约 100 个签名
生成的 k 长度错误	可变	约 50 个签名
计时侧信道	1-4 位	20-100 个签名
不安全的 PRNG	多位	少量
重用 nonce（k₁ = k₂）	全部	2 个签名

对于重用 nonce（最简单的情况）：

def ecdsa_reused_nonce(r, s1, s2, h1, h2, q):
    """Recover private key when nonce k is reused."""
    # s1 - s2 = k⁻¹(h1 - h2) mod q  (since r is same)
    k = ((h1 - h2) * inverse_mod(s1 - s2, q)) % q
    x = ((s1 * k - h1) * inverse_mod(r, q)) % q
    return x, k

---

6. 背包 / 子集和攻击

6.1 低密度攻击

背包问题：给定权重 a₁,...,aₙ 和目标 S，求 x₁,...,xₙ ∈ {0,1}，使得 Σxᵢaᵢ = S。

密度 d = n / max(log₂ aᵢ)。如果 d < 0.9408，格攻击有效。

# SageMath
def knapsack_lattice(weights, target):
    """Solve subset sum via LLL lattice attack."""
    n = len(weights)

    # Build lattice (Lagarias-Odlyzko style)
    N = ceil(sqrt(n) / 2)  # scaling factor
    M = matrix(ZZ, n + 1, n + 1)

    for i in range(n):
        M[i, i] = 1
        M[i, n] = N * weights[i]
    M[n, n] = N * target

    # Alternative: CJLOSS embedding
    M2 = matrix(ZZ, n + 1, n + 2)
    for i in range(n):
        M2[i, i] = 1
        M2[i, n + 1] = N * weights[i]
    M2[n, n] = 1
    M2[n, n + 1] = N * (-target)

    L = M2.LLL()

    # Look for short vector with entries in {0, 1, -1}
    for row in L:
        if all(v in (0, 1) for v in row[:n]):
            solution = list(row[:n])
            if sum(solution[i] * weights[i] for i in range(n)) == target:
                return solution

    return None

---

7. NTRU 密码分析

7.1 NTRU 格

# SageMath
def ntru_lattice_attack(h, q, N):
    """
    Construct NTRU lattice for key recovery.
    h = public key polynomial (mod q)
    q = modulus
    N = dimension
    """
    # NTRU lattice:
    # | qI  0 |
    # | H   I |
    # where H is the circulant matrix of h

    H = matrix(ZZ, N, N)
    for i in range(N):
        for j in range(N):
            H[i, j] = h[(j - i) % N]

    M = block_matrix([
        [q * identity_matrix(N), zero_matrix(N)],
        [H, identity_matrix(N)]
    ])

    L = M.LLL()

    # Short vector in reduced basis = (f, g) private key
    for row in L:
        f = vector(row[:N])
        g = vector(row[N:])
        if f.norm() < q and g.norm() < q:
            return f, g

    return None

---

8. 构造攻击格——方法

8.1 通用步骤

1. Express the cryptographic problem as:
   "Find small x such that f(x) ≡ 0 (mod N)"
   or "Find x close to target t in some lattice L"

2. Choose lattice type:
   ├─ Polynomial lattice → Coppersmith-style
   ├─ Modular lattice → HNP-style CVP
   └─ Knapsack lattice → subset sum / CJLOSS

3. Determine dimensions:
   └─ More dimensions = better approximation but slower

4. Set scaling factors:
   └─ Balance the rows so short vector has roughly equal entries
   └─ Common: multiply by N/X where X is the root bound

5. Apply reduction:
   ├─ LLL first (fast, usually sufficient)
   └─ BKZ if LLL fails (increase block size: 20, 30, 40)

6. Extract solution:
   └─ Check reduced basis rows for valid solutions

8.2 嵌入技术（CVP → SVP）

通过将目标嵌入格中，将 CVP 转换为 SVP：

# SageMath
def cvp_to_svp(basis_matrix, target, scale=1):
    """Convert CVP to SVP via Kannan's embedding."""
    n = basis_matrix.nrows()
    m = basis_matrix.ncols()

    # Augment matrix
    M = matrix(ZZ, n + 1, m + 1)
    for i in range(n):
        for j in range(m):
            M[i, j] = basis_matrix[i, j]
        M[i, m] = 0

    for j in range(m):
        M[n, j] = target[j]
    M[n, m] = scale  # scaling factor (try 1, then adjust)

    L = M.LLL()

    # Look for row with last entry = ±scale
    for row in L:
        if abs(row[m]) == scale:
            return vector(target) - vector(row[:m]) * (row[m] // abs(row[m]))

    return None

8.3 维度选择指南

问题	典型维度	备注
Coppersmith 单变量（次数 d）	d × m，其中 m ≈ 1/ε	m 越大，根的上界越小
有 n 个签名的 HNP	n + 2	n ≥ 已知位比例 × q 的位数
有 n 个权重的背包问题	n + 1 或 n + 2	取决于密度
有 n 个输出的 LCG	n + 1	输出越多，问题越容易
Boneh-Durfee	(m+1)(m+2)/2	m = 参数深度

---

9. 决策树

Lattice approach needed — which construction?
│
├─ RSA-related?
│  ├─ Small unknown part of message → Coppersmith univariate
│  │  └─ Check: unknown_bits < n_bits / e
│  ├─ Partial factor knowledge → Coppersmith mod p
│  │  └─ Use beta=0.5, X=2^unknown_bits
│  ├─ Small private exponent d → Boneh-Durfee
│  │  └─ Check: d < N^0.292
│  └─ Multiple related equations → multivariate Coppersmith
│
├─ DSA/ECDSA-related?
│  ├─ Reused nonce → direct algebraic recovery (no lattice needed)
│  ├─ Partial nonce leakage → HNP → CVP lattice
│  │  └─ Need enough signatures: n ≥ q_bits / leaked_bits
│  └─ Nonce bias → statistical HNP → larger lattice
│
├─ Knapsack / subset sum?
│  ├─ Low density (d < 0.9408) → CJLOSS lattice attack
│  ├─ High density → lattice attack unlikely to work
│  └─ Super-increasing → greedy algorithm (no lattice needed)
│
├─ LCG / PRNG?
│  ├─ Full outputs known → algebraic recovery (no lattice)
│  ├─ Truncated outputs → CVP on recurrence lattice
│  └─ Unknown modulus → use GCD of output differences
│
├─ NTRU?
│  └─ Build circulant lattice → LLL/BKZ for short key vector
│
└─ Custom problem?
   ├─ Express as "find small root of polynomial mod N" → Coppersmith
   ├─ Express as "find lattice point close to target" → CVP
   ├─ Express as "find short vector in lattice" → SVP / LLL
   └─ If none fit → probably not a lattice problem

---

10. 常见问题

问题	表现	修复方法
根的上界过大	small_roots() 返回空	减小 X，增大 epsilon，确认上界满足 Coppersmith 准则
缩放错误	LLL 找到无关的短向量	缩放各列，使目标向量的各项大小均衡
维度不足	解不在约化后的基中	增大 m 参数（使用更多移位多项式）
beta 错误	Coppersmith 未找到因子	对半大小因子使用 beta=0.5，对整个模数使用 beta=1.0
签名数量过少（HNP）	格攻击失败	收集更多带有 nonce 偏差的签名
BKZ 块大小过小	解不够短	增大块大小（尝试 25、30、40）
整数溢出	SageMath 崩溃	显式使用 ZZ 环，避免混用 QQ 和 ZZ