rsa-attack-techniques

SKILL：RSA 攻撃手法 — 暗号解読のエキスパート向けプレイブック

AI の読み込み指示：CTF および許可されたセキュリティ評価向けの、RSA 攻撃手法のエキスパートガイドです。素因数分解攻撃、小さい指数の悪用、格子ベースの手法（Wiener／Boneh-Durfee／Coppersmith）、ブロードキャスト攻撃、共通法、パディングオラクル、フォールト攻撃を扱います。ベースモデルは、与えられたパラメーターに合わない攻撃を提案したり、既知の情報に基づいて適切な攻撃を選択できなかったりすることがよくあります。

0. 関連ルーティング

• Coppersmith／Boneh-Durfee の格子理論を詳しく知りたい場合は、lattice-crypto-attacks を参照してください
• RSA 署名の偽造にハッシュの弱点が関係する場合は、hash-attack-techniques を参照してください
• RSA が共通鍵を保護している場合（ハイブリッド暗号化）は、symmetric-cipher-attacks を参照してください

高度なリファレンス

次の情報が必要な場合は、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.1 直接素因数分解（小さい n）

from sympy import factorint

n = 0x...  # small modulus
factors = factorint(n)
p, q = list(factors.keys())

条件：n < 約 512 ビット、または factordb に登録されていることが分かっている場合です。

1.2 Fermat の素因数分解

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 Pollard の 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):
    """Find shared factors among multiple RSA moduli."""
    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...  # ciphertext
e = 3
m, exact = iroot(c, e)
if exact:
    print(f"Plaintext: {bytes.fromhex(hex(m)[2:])}")

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

同じメッセージを、異なる法（n₁、n₂、...、nₑ）と同じ小さい e で暗号化した場合に使います。

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

# e = 3, three ciphertexts under three different n
n_list = [n1, n2, n3]
c_list = [c1, c2, c3]

# CRT: find x such that x ≡ ci (mod ni) for all i
r, M = crt(n_list, c_list)
m, exact = iroot(r, 3)
assert exact

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

2 つのメッセージが既知の線形関数 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):
    """Recover d when d is small via continued fractions."""
    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 are roots of 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 prefix, unknown suffix
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 — known MSB of p
p_msb = ...  # known upper bits of 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. 共通法攻撃

同じメッセージを同じ n で、異なる e₁、e₂ を使って暗号化しており、gcd(e₁, e₂) = 1 の場合に使います。

from gmpy2 import gcd, invert

def common_modulus(n, e1, e2, c1, c2):
    """Recover m when same message encrypted with two different e under same n."""
    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):
    """Decrypt using LSB (parity) oracle. oracle_func(c) returns 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  # multiply plaintext by 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 マンガー攻撃（PKCS#1 OAEP）

Bleichenbacher 攻撃と似ていますが、OAEP パディングを対象とします。パディング解除後の最初のバイトが 0x00 かどうかを判別するオラクルを悪用します。

---

7. RSA-CRT 故障攻撃

RSA-CRT 署名で故障した署名が生成された場合（CRT の片方に故障が発生）：

def rsa_crt_fault(n, e, correct_sig, faulty_sig, msg):
    """Factor n from one correct and one faulty CRT signature."""
    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

# Even simpler: only faulty signature needed if message is known
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 challenge — what information do you have?
│
├─ Have n and it's small (< 512 bits)?
│  └─ Factor directly: factordb.com → yafu → msieve
│
├─ Have multiple n values?
│  └─ Batch GCD — shared factors?
│     ├─ Yes → factor all that share factors
│     └─ No → analyze each n individually
│
├─ Know e?
│  ├─ e = 3 (or small)?
│  │  ├─ Single ciphertext, small message → cube root
│  │  ├─ Multiple ciphertexts, different n → Hastad broadcast
│  │  ├─ Two related messages → Franklin-Reiter
│  │  └─ Partial plaintext known → Coppersmith
│  │
│  ├─ e is very large?
│  │  └─ d is likely small → Wiener → Boneh-Durfee
│  │
│  └─ Same n, two different e values?
│     └─ Common modulus attack (Bezout coefficients)
│
├─ Know partial factorization info?
│  ├─ Know some bits of p → Coppersmith partial key
│  ├─ p-1 is B-smooth → Pollard p-1
│  └─ p ≈ q (close primes) → Fermat factorization
│
├─ Have an oracle?
│  ├─ Parity oracle (LSB) → LSB oracle attack
│  ├─ Padding validity oracle (PKCS#1 v1.5) → Bleichenbacher
│  └─ OAEP oracle → Manger's attack
│
├─ Have faulty signature?
│  └─ RSA-CRT fault → factor n from faulty sig
│
├─ Know e·d relationship?
│  └─ e·d ≡ 1 mod φ(n) → factor n from (e,d,n)
│
└─ None of the above?
   ├─ Check factordb for known factorization
   ├─ Try Pollard rho for medium-size n
   ├─ Look for implementation flaws (weak PRNG for key generation)
   └─ Consider side-channel if physical access available

---

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 のクイックコマンド

# From public key
python3 RsaCtfTool.py --publickey pub.pem -n --private

# From parameters
python3 RsaCtfTool.py -n $N -e $E --uncipher $C

# Try all attacks
python3 RsaCtfTool.py --publickey pub.pem --uncipherfile flag.enc --attack all

因数分解後の復号

from Crypto.PublicKey import RSA
from gmpy2 import invert

p, q = ...  # factored
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = int(invert(e, phi))

c = ...  # ciphertext as integer
m = pow(c, d, n)
plaintext = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(plaintext)