lattice-crypto-attacks

SKILL: 格子ベース暗号解析 — エキスパート攻撃プレイブック

AI LOAD INSTRUCTION: CTF と暗号解析のためのエキスパート向け格子テクニックです。LLL/BKZ 簡約、Coppersmith 法（単変数および多変数）、DSA/ECDSA nonce の復元に用いる Hidden Number Problem、ナップサック攻撃、NTRU 解析を扱います。基本モデルでは、正しい攻撃格子を構成できない（次元が間違っている、スケーリング係数が欠落している）ことや、Coppersmith の境界を誤って適用することがよくあります。

0. 関連するルーティング

• rsa-attack-techniques：格子手法（Coppersmith、Boneh-Durfee）を使う RSA 固有の攻撃について
• 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 バイアス	Hidden Number Problem → 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 が与えられたとき、t に最も近い v ∈ L を見つけます
• SVP は一般に NP 困難ですが、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' を生成します。

• ベクトルがほぼ直交している
• 第 1 ベクトルが近似的に短い（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 単変数の場合

小さい根 |x₀| < X を持つ f(x) ≡ 0 (mod N) が与えられたとき、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) の場合：

• 多項式時間アルゴリズムは保証されていません
• ヒューリスティックな手法は実際に機能します
• RSA の小さい d に対する Boneh-Durfee で使用されます

# 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. Hidden Number Problem（HNP）— DSA/ECDSA nonce の復元

5.1 問題の定義

与えられるもの：nonce kᵢ に既知のバイアス（MSB または LSB の漏えい）がある署名 (rᵢ, sᵢ)。

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 実用的なノンスの偏りの原因

原因	漏洩ビット数	必要な署名数
MSB の偏り（常に 0）	1 ビット	約 100 個の署名
誤った長さで生成された k	可変	約 50 個の署名
タイミングサイドチャネル	1～4 ビット	20～100 個の署名
安全でない PRNG	多数	少数
ノンスの再利用（k₁ = k₂）	すべて	2 個の署名

ノンスの再利用（最も単純なケース）の場合：

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ᵢaᵢ = S を満たす x₁,...,xₙ ∈ {0,1} を求めます。

密度 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）	格子攻撃に失敗する	ノンスに偏りのある署名をさらに収集します
BKZ のブロックサイズが小さすぎる	解が十分に短くならない	ブロックサイズを大きくします（25、30、40 を試します）
整数オーバーフロー	SageMath がクラッシュする	明示的に ZZ リングを使用し、QQ と ZZ の混在を避けます