rsa-attack-techniques

技能：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 直接因数分解（n 较小）

from sympy import factorint

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

适用情况：n < ~512 位，或已知 n 在 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）

两条消息满足已知线性关系：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 填充有效或无效），通过迭代逐步缩小明文范围。

复杂度：平均每个字节需要 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):
    """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)