SKILL: RSA Attack Techniques — エキスパート暗号解析プレイブック

AI LOAD INSTRUCTION: CTF および認可されたセキュリティ評価のためのエキスパート RSA 攻撃技法。因数分解攻撃、小指数エクスプロイト、格子ベースのアプローチ (Wiener/Boneh-Durfee/Coppersmith)、ブロードキャスト攻撃、共通法数、パディングオラクル、および障害攻撃をカバーします。基本モデルは、与えられたパラメータに合致しない攻撃を提示したり、既知情報に基づいた正しい攻撃選択を見落としたりすることがよくあります。

0. RELATED ROUTING

• lattice-crypto-attacks - Coppersmith/Boneh-Durfee の背後にある格子理論の詳細版
• hash-attack-techniques - RSA 署名偽造がハッシュ弱点を含む場合
• symmetric-cipher-attacks - RSA が対称鍵を保護する場合（ハイブリッド暗号化）

Advanced Reference

次の場合は RSA_ATTACK_CATALOG.md もロードしてください:

• 各攻撃の詳細な SageMath/Python 実装
• ステップバイステップの数学的導出
• 攻撃ごとのエッジケースと失敗条件

攻撃選択クイックガイド

与えられた情報 / 観測	攻撃	ツール
小さい n (< 512 ビット)	直接因数分解	factordb, yafu, msieve
e = 3、小さいメッセージ	キューブルート	gmpy2.iroot
複数の (n, c)、同じ小さい e	Hastad ブロードキャスト	CRT + iroot
非常に大きい e または非常に小さい d	Wiener / Boneh-Durfee	SageMath, RsaCtfTool
p の部分的な知識	Coppersmith 小根	SageMath
同じ n、異なる e	共通法数	拡張ユークリッド互除法
複数の n 値	バッチ GCD（共有因数）	Python/SageMath
パディングエラーオラクル	Bleichenbacher	カスタムスクリプト
LSB パリティオラクル	LSB オラクル攻撃	カスタムスクリプト
CRT 計算における障害	RSA-CRT 障害	単一障害署名

---

1. 因数分解攻撃

1.1 直接因数分解（小さい n）

from sympy import factorint

n = 0x...  # 小さい法数
factors = factorint(n)
p, q = list(factors.keys())

使用時: n < 約512 ビット、または factordb に既知の場合。

1.2 フェルマの因数分解

p と q が接近している場合に有効：|p - q| が小さい。

from gmpy2 import isqrt, is_square

def fermat_factor(n):
    a = isqrt(n) + 1
    while True:
        b2 = a * a - n
        if is_square(b2):
            b = isqrt(b2)
            return (a + b, a - b)
        a += 1

1.3 ポラードの p-1 法

p-1 が小さい素因数のみを持つ場合（B-平滑）に有効。

from gmpy2 import gcd

def pollard_p1(n, B=2**20):
    a = 2
    for j in range(2, B):
        a = pow(a, j, n)
    d = gcd(a - 1, n)
    if 1 < d < n:
        return d
    return None

1.4 バッチ GCD（複数の n が因数を共有）

from math import gcd
from functools import reduce

def batch_gcd(moduli):
    """複数の RSA 法数間の共有因数を検出します。"""
    product = reduce(lambda a, b: a * b, moduli)
    results = {}
    for i, n in enumerate(moduli):
        remainder = product // n
        g = gcd(n, remainder)
        if g != 1 and g != n:
            results[i] = (g, n // g)
    return results

---

2. 小指数攻撃

2.1 キューブルート攻撃（e = 3、小さい m）

m^e < n の場合（法による短縮が発生していない）、単に e 乗根を求めます。

from gmpy2 import iroot

c = 0x...  # 暗号文
e = 3
m, exact = iroot(c, e)
if exact:
    print(f"平文: {bytes.fromhex(hex(m)[2:])}")

2.2 Hastad ブロードキャスト攻撃

同じメッセージが同じ小さい e で異なる法数 (n₁, n₂, ..., nₑ) の下で暗号化されている場合。

from sympy.ntheory.modular import crt
from gmpy2 import iroot

# e = 3、3 つの異なる n の下での 3 つの暗号文
n_list = [n1, n2, n3]
c_list = [c1, c2, c3]

# CRT: すべての i に対して x ≡ ci (mod ni) を満たす x を検出
r, M = crt(n_list, c_list)
m, exact = iroot(r, 3)
assert exact

2.3 関連メッセージ攻撃（Franklin-Reiter）

既知の一次関数によって関連するメッセージ：m₂ = a·m₁ + b。同じ n と e。

# SageMath
def franklin_reiter(n, e, c1, c2, a, b):
    R.<x> = PolynomialRing(Zmod(n))
    f1 = x^e - c1
    f2 = (a*x + b)^e - c2
    return Integer(n - gcd(f1, f2).coefficients()[0])

---

3. 大きい e / 小さい d 攻撃

3.1 Wiener 攻撃（連分数）

d < n^(1/4) / 3 のとき、e/n の連分数展開により d が明らかになります。

def wiener_attack(e, n):
    """d が小さい場合、連分数を経由して d を復号します。"""
    cf = continued_fraction(e, n)
    convergents = get_convergents(cf)

    for k, d in convergents:
        if k == 0:
            continue
        phi_candidate = (e * d - 1) // k
        # phi(n) = n - p - q + 1 → p + q = n - phi + 1
        s = n - phi_candidate + 1
        # p, q は x^2 - s*x + n = 0 の根
        discriminant = s * s - 4 * n
        if discriminant >= 0:
            from gmpy2 import isqrt, is_square
            if is_square(discriminant):
                return d
    return None

def continued_fraction(a, b):
    cf = []
    while b:
        cf.append(a // b)
        a, b = b, a % b
    return cf

def get_convergents(cf):
    convergents = []
    h_prev, h_curr = 0, 1
    k_prev, k_curr = 1, 0
    for a in cf:
        h_prev, h_curr = h_curr, a * h_curr + h_prev
        k_prev, k_curr = k_curr, a * k_curr + k_prev
        convergents.append((h_curr, k_curr))
    return convergents

3.2 Boneh-Durfee 攻撃（格子ベース）

Wiener を拡張：d < n^0.292 のときに機能します。格子簡約化 (LLL/BKZ) を使用。

SageMath 実装を使用 — 理論については lattice-crypto-attacks を参照。

---

4. Coppersmith 法

4.1 ステレオタイプメッセージ

既知の平文部分、不明な部分は小さい。

# SageMath
n = ...
e = 3
c = ...
known_prefix = b"flag{" + b"\x00" * 27  # 既知プレフィックス、不明なサフィックス
known_int = int.from_bytes(known_prefix, 'big')

R.<x> = PolynomialRing(Zmod(n))
f = (known_int + x)^e - c
roots = f.small_roots(X=2^(27*8), beta=1.0)
if roots:
    m = known_int + int(roots[0])
    print(bytes.fromhex(hex(m)[2:]))

4.2 部分鍵露出

p の既知 MSB または LSB → Coppersmith を経由して完全な p を復号。

# SageMath — p の既知 MSB
p_msb = ...  # p の既知上位ビット
R.<x> = PolynomialRing(Zmod(n))
f = p_msb + x
roots = f.small_roots(X=2^unknown_bits, beta=0.5)
if roots:
    p = p_msb + int(roots[0])
    q = n // p

---

5. 共通法数攻撃

同じメッセージの 2 つの暗号文、同じ n だが異なる e₁, e₂ で、gcd(e₁, e₂) = 1。

from gmpy2 import gcd, invert

def common_modulus(n, e1, e2, c1, c2):
    """同じ n の下で 2 つの異なる e で暗号化された場合、m を復号します。"""
    assert gcd(e1, e2) == 1
    _, s1, s2 = extended_gcd(e1, e2)  # s1*e1 + s2*e2 = 1

    if s1 < 0:
        c1 = invert(c1, n)
        s1 = -s1
    if s2 < 0:
        c2 = invert(c2, n)
        s2 = -s2

    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return m

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

---

6. オラクル攻撃

6.1 LSB オラクル（パリティオラクル）

オラクルが復号されたメッセージが偶数か奇数かを明かします。

from gmpy2 import mpz

def lsb_oracle_attack(n, e, c, oracle_func):
    """LSB（パリティ）オラクルを使用して復号します。oracle_func(c) は m%2 を返します。"""
    from fractions import Fraction
    lo, hi = Fraction(0), Fraction(n)

    for _ in range(n.bit_length()):
        c = (c * pow(2, e, n)) % n  # 平文に 2 を掛ける
        if oracle_func(c) == 0:
            hi = (lo + hi) / 2
        else:
            lo = (lo + hi) / 2

    return int(hi)

6.2 Bleichenbacher（PKCS#1 v1.5 パディングオラクル）

パディング有効性オラクル（有効/無効な PKCS#1 v1.5）が与えられたら、反復的に平文範囲を絞り込みます。

複雑さ: 平均で 1 バイトあたり O(2^16) 回のオラクルクエリ。

対象: 異なるエラーを返す TLS 実装（有効/無効なパディング）。

6.3 Manger 攻撃（PKCS#1 OAEP）

Bleichenbacher に似ていますが OAEP パディング用。パディング解除後の最初のバイトが 0x00 かどうかを区別するオラクルを悪用。

---

7. RSA-CRT 障害攻撃

RSA-CRT 署名が障害署名を生成する場合（CRT の一半で障害が発生）：

def rsa_crt_fault(n, e, correct_sig, faulty_sig, msg):
    """1 つの正しい署名と 1 つの障害署名から n を因数分解します。"""
    from math import gcd
    diff = pow(correct_sig, e, n) - pow(faulty_sig, e, n)
    p = gcd(diff % n, n)
    if 1 < p < n:
        q = n // p
        return p, q
    return None

# さらに単純：メッセージが既知の場合、障害署名のみで十分
def rsa_crt_fault_simple(n, e, faulty_sig, msg):
    p = gcd(pow(faulty_sig, e, n) - msg, n)
    if 1 < p < n:
        return p, n // p
    return None

---

8. 決定木

RSA チャレンジ — どの情報を持っていますか？
│
├─ n があり、小さい（< 512 ビット）？
│  └─ 直接因数分解：factordb.com → yafu → msieve
│
├─ 複数の n 値を持っていますか？
│  └─ バッチ GCD — 共有因数がありますか？
│     ├─ はい → 因数を共有するすべての n を因数分解
│     └─ いいえ → 各 n を個別に分析
│
├─ e を知っていますか？
│  ├─ e = 3（または小さい）？
│  │  ├─ 単一の暗号文、小さいメッセージ → キューブルート
│  │  ├─ 複数の暗号文、異なる n → Hastad ブロードキャスト
│  │  ├─ 2 つの関連メッセージ → Franklin-Reiter
│  │  └─ 部分的な平文が既知 → Coppersmith
│  │
│  ├─ e は非常に大きい？
│  │  └─ d は小さい可能性が高い → Wiener → Boneh-Durfee
│  │
│  └─ 同じ n、2 つの異なる e？
│     └─ 共通法数攻撃（Bezout 係数）
│
├─ 部分的な因数分解情報を知っていますか？
│  ├─ p の数ビットを知っている → Coppersmith 部分鍵
│  ├─ p-1 は B-平滑 → ポラード p-1
│  └─ p ≈ q（接近した素数） → フェルマ因数分解
│
├─ オラクルを持っていますか？
│  ├─ パリティオラクル（LSB） → LSB オラクル攻撃
│  ├─ パディング有効性オラクル（PKCS#1 v1.5） → Bleichenbacher
│  └─ OAEP オラクル → Manger 攻撃
│
├─ 障害署名を持っていますか？
│  └─ RSA-CRT 障害 → 障害署名から n を因数分解
│
├─ e·d 関係を知っていますか？
│  └─ e·d ≡ 1 mod φ(n) → (e,d,n) から n を因数分解
│
└─ 上記のいずれでもない？
   ├─ 既知の因数分解について factordb を確認
   ├─ 中程度のサイズの n に対して Pollard rho を試す
   ├─ 実装の欠陥を探す（鍵生成の弱い PRNG）
   └─ 物理的アクセスがある場合、サイドチャネルを検討

---

9. ツール

ツール	目的	使用方法
RsaCtfTool	自動化 RSA 攻撃スイート	python3 RsaCtfTool.py --publickey pub.pem --uncipherfile flag.enc
SageMath	数学計算	Coppersmith、格子攻撃、多項式演算
factordb.com	オンライン因数分解データベース	n が既に因数分解されているか確認
yafu	高速因数分解（SIQS/GNFS）	yafu "factor(n)"
msieve	GNFS 因数分解	大きい n の因数分解
gmpy2	高速 Python 整数ライブラリ	iroot、invert、gcd
pycryptodome	RSA プリミティブ	因数から鍵構築

RsaCtfTool クイックコマンド

# 公開鍵から
python3 RsaCtfTool.py --publickey pub.pem -n --private

# パラメータから
python3 RsaCtfTool.py -n $N -e $E --uncipher $C

# すべての攻撃を試す
python3 RsaCtfTool.py --publickey pub.pem --uncipherfile flag.enc --attack all

因数分解後に復号化

from Crypto.PublicKey import RSA
from gmpy2 import invert

p, q = ...  # 因数分解済み
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = int(invert(e, phi))

c = ...  # 整数としての暗号文
m = pow(c, d, n)
plaintext = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(plaintext)