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

AI LOAD INSTRUCTION: CTF と暗号解析用の格子ベース手法のエキスパート向け。LLL/BKZ 削減、Coppersmith 法（一変数および多変数）、DSA/ECDSA nonce 復元用隠れ数問題、ナップサック攻撃、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 バイアス	隠れ数問題 → CVP	既知バイアスビット
ナップサック暗号	低密度格子攻撃	密度 < 0.9408
LCG 切り詰め出力	漸化式格子上の CVP	出力あたりの未知ビット
部分集合和	ナップサック格子上の LLL 削減	要素サイズ vs カウント
NTRU 鍵復元	NTRU 格子上の格子削減	次元と鍵サイズ

---

1. 格子の基礎

1.1 定義

格子 L は基底ベクトルのすべての整数一次結合の集合です:

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

ここで b₁, ..., bₙ は ℝᵐ 内の線形独立ベクトルです。

主要な問題:

• SVP (最短ベクトル問題): L 内の最短非ゼロベクトルを見つける
• CVP (最近傍ベクトル問題): 目標 t が与えられたとき、t に最も近い L 内のベクトル v を見つける
• SVP は一般に NP困難 ですが、LLL は多項式時間で近似的に短いベクトルを見つけます

1.2 格子品質メトリクス

行列式: det(L) = |det(B)| ここで B は基底行列
ガウス启発式: 最短ベクトル ≈ √(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()
# L 内の短ベクトルが解を示す
short_vector = L[0]  # 最初の行は通常最短

2.3 Python (fpylll)

from fpylll import IntegerMatrix, LLL

n = 4
A = IntegerMatrix(n, n)
# 行列 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])  # 最短ベクトル

---

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 に進める。BKZ ブロックサイズ 20-40 は通常 CTF で十分です。

---

4. COPPERSMITH 法

4.1 一変数の場合

f(x) ≡ 0 (mod N) が小根 |x₀| < X を持つ場合、x₀ を見つけます。

界: X < N^(1/d)、ここで d = f の次数。

# SageMath — 組み込みの small_roots
N = ...
R.<x> = PolynomialRing(Zmod(N))
f = x^3 + a*x^2 + b*x + c  # 既知多項式
roots = f.small_roots(X=2^100, beta=1.0, epsilon=1/30)

パラメータ:

• X: 根の上界
• beta: N = p^beta (modular 根が N 自体の場合 beta=1.0; 未知因子 p ≈ √N の根の場合 beta=0.5)
• epsilon: より小さい = より良い結果だが低速（1/30 から 1/100 を試す）

4.2 ステレオタイプメッセージ攻撃 (RSA)

# SageMath
n, e, c = ...  # RSA パラメータ
known_msb = ...  # メッセージの既知上位部分

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

# x は未知の下位ビットを表す
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 = ...  # p の既知上位ビット

R.<x> = PolynomialRing(Zmod(n))
f = p_known + x
roots = f.small_roots(X=2^unknown_bits, beta=0.5)
# p ≈ √n なので beta=0.5
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) ここで phi = (p-1)(q-1)
# 書き換え: e*d = 1 + k*((n+1) - (p+q))
# x = k、y = (p+q) とすると、どちらも n に相対的に小さい

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

# シフト多項式を構築し、格子を構築
# LLL を適用して小さい (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: (r, s, hash, known_nonce_bits) のリスト
    q: 曲線の位数
    known_bits: nonce あたりの既知ビット数
    """
    n = len(signatures)

    # 格子を構築
    B = 2^(q.nbits() - known_bits)  # 未知部分の界
    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 = 既知 nonce ビット

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

    # LLL 削減
    L = M.LLL()

    # 秘密鍵 x を含む行を見つける
    for row in L:
        x_candidate = Integer(row[n] * q / B) % q
        # x_candidate を 1 つの署名に対して検証
        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):
    """nonce k が再利用された場合、秘密鍵を復元します。"""
    # s1 - s2 = k⁻¹(h1 - h2) mod q  (r は同じなので)
    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):
    """LLL 格子攻撃を介して部分集合和を解く。"""
    n = len(weights)

    # 格子を構築 (Lagarias-Odlyzko スタイル)
    N = ceil(sqrt(n) / 2)  # スケーリング係数
    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

    # 代替案: CJLOSS 埋め込み
    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()

    # {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):
    """
    鍵復元用の NTRU 格子を構築します。
    h = 公開鍵多項式 (mod q)
    q = 法
    N = 次元
    """
    # NTRU 格子:
    # | qI  0 |
    # | H   I |
    # ここで H は 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()

    # 削減基底の短ベクトル = (f, g) 秘密鍵
    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. 暗号学的問題を以下のように表現します:
   「f(x) ≡ 0 (mod N) となる小さい x を見つける」
   または「ある格子 L 内で x を目標 t に近づけられるを見つける」

2. 格子タイプを選択:
   ├─ 多項式格子 → Coppersmith スタイル
   ├─ 法格子 → HNP スタイル CVP
   └─ ナップサック格子 → 部分集合和 / CJLOSS

3. 次元を決定:
   └─ より多くの次元 = より良い近似だが低速

4. スケーリング係数を設定:
   └─ 短いベクトルがほぼ同じエントリを持つように行を均衡させる
   └─ 一般的: N/X で乗算、ここで X は根の界

5. 削減を適用:
   ├─ LLL で開始 (高速、通常十分)
   └─ LLL が失敗した場合 BKZ (ブロックサイズを増加: 20, 30, 40)

6. 解を抽出:
   └─ 削減基底の行をチェックして有効な解を見つける

8.2 埋め込み手法 (CVP → SVP)

CVP を埋め込みによって SVP に変換:

# SageMath
def cvp_to_svp(basis_matrix, target, scale=1):
    """Kannan の埋め込みで CVP を SVP に変換します。"""
    n = basis_matrix.nrows()
    m = basis_matrix.ncols()

    # 行列を拡張
    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  # スケーリング係数 (1 から試す、その後調整)

    L = M.LLL()

    # 最後のエントリが ±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 ≥ known_bits_ratio × q_bits
n 個の重みを持つナップサック	n + 1 または n + 2	密度に依存
n 個の出力を持つ LCG	n + 1	より多くの出力 = より簡単
Boneh-Durfee	(m+1)(m+2)/2	m = パラメータ深さ

---

9. 決定木

格子アプローチが必要 — どの構成?
│
├─ RSA 関連?
│  ├─ メッセージの小さい未知部分 → Coppersmith 一変数
│  │  └─ チェック: unknown_bits < n_bits / e
│  ├─ 部分因子知識 → Coppersmith mod p
│  │  └─ beta=0.5、X=2^unknown_bits を使用
│  ├─ 小さい秘密鍵 d → Boneh-Durfee
│  │  └─ チェック: d < N^0.292
│  └─ 複数の関連方程式 → 多変数 Coppersmith
│
├─ DSA/ECDSA 関連?
│  ├─ 再利用された nonce → 直接代数的復元 (格子不要)
│  ├─ 部分的な nonce リーク → HNP → CVP 格子
│  │  └─ 十分な署名が必要: n ≥ q_bits / leaked_bits
│  └─ Nonce バイアス → 統計的 HNP → より大きい格子
│
├─ ナップサック / 部分集合和?
│  ├─ 低密度 (d < 0.9408) → CJLOSS 格子攻撃
│  ├─ 高密度 → 格子攻撃は機能しそうにない
│  └─ スーパー増加 → 貪欲アルゴリズム (格子不要)
│
├─ LCG / PRNG?
│  ├─ 完全な出力が既知 → 代数的復元 (格子不要)
│  ├─ 切り詰められた出力 → 漸化式格子上の CVP
│  └─ 未知の法 → 出力差分の GCD を使用
│
├─ NTRU?
│  └─ 巡回格子を構築 → 短いキーベクトル用の LLL/BKZ
│
└─ カスタム問題?
   ├─ 「多項式の小根を mod N で見つける」として表現 → Coppersmith
   ├─ 「格子点を目標に近づける」として表現 → CVP
   ├─ 「格子内の短ベクトルを見つける」として表現 → SVP / LLL
   └─ どれにも当てはまらない場合 → おそらく格子問題ではない

---

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 の混合を回避