rsa-attack-techniques

Compare original and translation side by side

🇺🇸

Original

English

🇨🇳

Translation

Chinese

SKILL: RSA Attack Techniques — Expert Cryptanalysis Playbook

SKILL: RSA攻击技术 — 专家级密码分析手册

AI LOAD INSTRUCTION: Expert RSA attack techniques for CTF and authorized security assessments. Covers factorization attacks, small exponent exploits, lattice-based approaches (Wiener/Boneh-Durfee/Coppersmith), broadcast attacks, common modulus, padding oracles, and fault attacks. Base models often suggest attacks that don't match the given parameters or miss the correct attack selection based on what's known.

AI加载说明：适用于CTF和授权安全评估的专家级RSA攻击技术，覆盖因子分解攻击、小指数利用、基于格的方法（Wiener/Boneh-Durfee/Coppersmith）、广播攻击、共模攻击、padding oracle、故障攻击。基础模型通常会给出与给定参数不匹配的攻击建议，或者无法根据已知条件选择正确的攻击方式。

0. RELATED ROUTING

0. 相关跳转

lattice-crypto-attacks for deep lattice theory behind Coppersmith/Boneh-Durfee
hash-attack-techniques when RSA signature forgery involves hash weaknesses
symmetric-cipher-attacks when RSA protects a symmetric key (hybrid encryption)

lattice-crypto-attacks 了解Coppersmith/Boneh-Durfee背后的深层格理论
hash-attack-techniques 当RSA签名伪造涉及哈希漏洞时使用
symmetric-cipher-attacks 当RSA用于保护对称密钥（混合加密）时使用

Advanced Reference

高级参考

Also load RSA_ATTACK_CATALOG.md when you need:

Detailed SageMath/Python implementation for each attack
Step-by-step mathematical derivation
Edge cases and failure conditions per attack

当你需要以下内容时也可以加载RSA_ATTACK_CATALOG.md：

每种攻击的详细SageMath/Python实现
分步数学推导
每种攻击的边缘情况和失败条件

Quick attack selection

快速攻击选择

Given / Observable	Attack	Tool
Small n (< 512 bits)	Direct factorization	factordb, yafu, msieve
e = 3, small message	Cube root	gmpy2.iroot
Multiple (n, c) same small e	Hastad broadcast	CRT + iroot
Very large e or very small d	Wiener / Boneh-Durfee	SageMath, RsaCtfTool
Partial p knowledge	Coppersmith small roots	SageMath
Same n, different e	Common modulus	Extended GCD
Multiple n values	Batch GCD (shared factor)	Python/SageMath
Padding error oracle	Bleichenbacher	Custom script
LSB parity oracle	LSB oracle attack	Custom script
Fault in CRT computation	RSA-CRT fault	Single faulty signature

给定/可观察条件	攻击方式	工具
小n (< 512 bits)	直接因子分解	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	共模攻击	扩展GCD
多个n值	批量GCD（共享因子）	Python/SageMath
填充错误oracle	Bleichenbacher攻击	自定义脚本
LSB奇偶校验oracle	LSB oracle攻击	自定义脚本
CRT计算出错	RSA-CRT故障攻击	单个故障签名

1. FACTORIZATION ATTACKS

1. 因子分解攻击

1.1 Direct Factorization (Small n)

1.1 直接因子分解（小n）

python

from sympy import factorint

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

When: n < ~512 bits, or known to be in factordb.

python

from sympy import factorint

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

适用场景：n < ~512 bits，或者已知在factordb中存在记录。

1.2 Fermat's Factorization

1.2 费马因子分解

Works when p and q are close together: |p - q| is small.

python

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

适用于p和q数值接近的场景：|p - q|很小。

python

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's p-1

1.3 Pollard's p-1攻击

Works when p-1 has only small prime factors (B-smooth).

python

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

适用于p-1仅包含小质因子（B-平滑）的场景。

python

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 Batch GCD (Multiple n share a factor)

1.4 批量GCD（多个n共享因子）

python

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

python

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. SMALL EXPONENT ATTACKS

2. 小指数攻击

2.1 Cube Root Attack (e = 3, small m)

2.1 立方根攻击（e = 3，小m）

If m^e < n (no modular reduction occurred), simply take the e-th root.

python

from gmpy2 import iroot

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

如果m^e < n（没有发生模约简），直接开e次方根即可。

python

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 Broadcast Attack

2.2 Hastad广播攻击

Same message encrypted with same small e under different moduli (n₁, n₂, ..., nₑ).

python

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

相同消息使用相同小e在不同模数(n₁, n₂, ..., nₑ)下加密的场景。

python

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

undefined

r, M = crt(n_list, c_list) m, exact = iroot(r, 3) assert exact

undefined

2.3 Related Message Attack (Franklin-Reiter)

2.3 关联消息攻击（Franklin-Reiter）

Two messages related by a known linear function: m₂ = a·m₁ + b. Same n and e.

python

undefined

两条消息满足已知线性关系：m₂ = a·m₁ + b，使用相同n和e加密的场景。

python

undefined

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])

---

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. LARGE e / SMALL d ATTACKS

3. 大e/小d攻击

3.1 Wiener's Attack (Continued Fractions)

3.1 Wiener攻击（连分数法）

When d < n^(1/4) / 3, the continued fraction expansion of e/n reveals d.

python

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

当d < n^(1/4) / 3时，e/n的连分数展开可以得到d。

python

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 Attack (Lattice-Based)

3.2 Boneh-Durfee攻击（基于格）

Extends Wiener: works when d < n^0.292. Uses lattice reduction (LLL/BKZ).

Use SageMath implementation — see lattice-crypto-attacks for theory.

Wiener攻击的扩展：适用于d < n^0.292的场景，使用格规约（LLL/BKZ）。

使用SageMath实现 — 查看lattice-crypto-attacks了解理论。

4. COPPERSMITH'S METHOD

4. COPPERSMITH方法

4.1 Stereotyped Message

4.1 固定格式消息攻击

Known portion of plaintext, unknown part is small.

python

undefined

已知明文的部分内容，未知部分长度很小的场景。

python

undefined

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:]))

undefined

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:]))

undefined

4.2 Partial Key Exposure

4.2 部分密钥泄露攻击

Known MSB or LSB of p → recover full p via Coppersmith.

python

undefined

已知p的最高位或最低位 → 通过Coppersmith方法恢复完整的p。

python

undefined

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

---

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. COMMON MODULUS ATTACK

5. 共模攻击

Two ciphertexts of same message under same n but different e₁, e₂ where gcd(e₁, e₂) = 1.

python

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

相同消息使用相同n但不同e₁、e₂加密，且gcd(e₁, e₂) = 1的场景。

python

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. ORACLE ATTACKS

6. ORACLE攻击

6.1 LSB Oracle (Parity Oracle)

6.1 LSB Oracle（奇偶校验Oracle）

An oracle reveals whether decrypted message is even or odd.

python

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)

Oracle会返回解密后的消息是奇数还是偶数的场景。

python

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 Padding Oracle)

6.2 Bleichenbacher攻击（PKCS#1 v1.5填充Oracle）

Given a padding validity oracle (valid/invalid PKCS#1 v1.5), iteratively narrow down the plaintext range.

Complexity: O(2^16) oracle queries per byte on average.

Target: TLS implementations returning different errors for valid/invalid padding.

给定填充有效性Oracle（返回PKCS#1 v1.5填充是否有效），可以迭代缩小明文范围。

复杂度：平均每字节需要O(2^16)次Oracle查询。

目标：对有效/无效填充返回不同错误的TLS实现。

6.3 Manger's Attack (PKCS#1 OAEP)

6.3 Manger攻击（PKCS#1 OAEP）

Similar to Bleichenbacher but for OAEP padding. Exploits oracle that distinguishes whether the first byte after unpadding is 0x00.

和Bleichenbacher攻击类似，但针对OAEP填充，利用可以区分解填充后首字节是否为0x00的Oracle。

7. RSA-CRT FAULT ATTACK

7. RSA-CRT故障攻击

If RSA-CRT signing produces a faulty signature (fault in one CRT half):

python

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

如果RSA-CRT签名生成了故障签名（其中一个CRT半区计算出错）：

python

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

---

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. DECISION TREE

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

RSA挑战 — 你目前拥有哪些信息？
│
├─ 有n且数值很小 (< 512 bits)？
│  └─ 直接分解：factordb.com → yafu → msieve
│
├─ 有多个n值？
│  └─ 批量GCD — 是否有共享因子？
│     ├─ 是 → 分解所有共享因子的n
│     └─ 否 → 单独分析每个n
│
├─ 已知e？
│  ├─ e = 3（或其他小值）？
│  │  ├─ 单个密文，消息长度小 → 立方根攻击
│  │  ├─ 多个密文，不同n → Hastad广播攻击
│  │  ├─ 两个关联消息 → Franklin-Reiter攻击
│  │  └─ 已知部分明文 → Coppersmith攻击
│  │
│  ├─ e数值极大？
│  │  └─ d大概率很小 → Wiener攻击 → Boneh-Durfee攻击
│  │
│  └─ 相同n，两个不同e值？
│     └─ 共模攻击（贝祖系数）
│
├─ 已知部分因子分解信息？
│  ├─ 已知p的部分比特 → Coppersmith部分密钥攻击
│  ├─ p-1是B-平滑 → Pollard p-1攻击
│  └─ p ≈ q（质数接近） → 费马因子分解
│
├─ 有Oracle？
│  ├─ 奇偶校验Oracle（LSB） → LSB oracle攻击
│  ├─ 填充有效性Oracle（PKCS#1 v1.5） → Bleichenbacher攻击
│  └─ OAEP Oracle → Manger攻击
│
├─ 有故障签名？
│  └─ RSA-CRT故障攻击 → 从故障签名分解n
│
├─ 已知e·d关系？
│  └─ e·d ≡ 1 mod φ(n) → 从(e,d,n)分解n
│
└─ 以上都不符合？
   ├─ 检查factordb是否有已知分解结果
   ├─ 对中等大小的n尝试Pollard rho攻击
   ├─ 查找实现缺陷（密钥生成使用弱PRNG）
   └─ 如果有物理访问权限考虑侧信道攻击

9. TOOLS

9. 工具

Tool	Purpose	Usage
RsaCtfTool	Automated RSA attack suite	`python3 RsaCtfTool.py --publickey pub.pem --uncipherfile flag.enc`
SageMath	Mathematical computation	Coppersmith, lattice attacks, polynomial arithmetic
factordb.com	Online factor database	Check if n is already factored
yafu	Fast factorization (SIQS/GNFS)	`yafu "factor(n)"`
msieve	GNFS factorization	Large n factorization
gmpy2	Fast Python integer library	`iroot` , `invert` , `gcd`
pycryptodome	RSA primitives	Key construction from factors

工具	用途	用法
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 Quick Commands

RsaCtfTool快速命令

bash

undefined

bash

undefined

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

undefined

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

undefined

Decrypt After Factoring

因子分解后解密

python

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)

python

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)