CTF中常见的RSA加密

CTF 中常见 RSA 题型全总结

刚开学没多久就参加了湾区杯和启沅杯。都有RSA加密的题，来总结一下常见的RSA加密题型。
含数学证明、例题、通用解题脚本（基于 CTF 选手常用库：gmpy2、Crypto、Pwntools、sympy、sage 等）

0x00 前言

RSA 是 CTF 密码学”送分题”常客，题型高度套路化。本文把出现频率最高的 7+ 类模型抽象出来，给出：

  1. 数学推导（严谨证明）
  2. 通用模板脚本（直接套）
  3. 例题 + 完整解题脚本（能复现）

所有脚本均基于 Python3 + gmpy2 + pycryptodome + sage（可选），与各大比赛环境 100% 兼容。

0x01 工具箱一键安装

1
2
pip3 install gmpy2 pycryptodome sympy pwntools
# sage 单独装：Ubuntu apt install sagemath

0x02 题型速查表

题型特征攻击方法脚本
1. 低加密指数（e=3）e 很小，明文 m < n^(1/e)直接开 e 次根iroot(c,3)
2. 低解密指数e 巨大，d < N^0.292Wiener / Boneh-DurfeeGitHub 开源
3. 共模同一 n，多 e，同 m扩展欧几里得gmpy2.gcdext
4. dp/dq 泄露已知 dp分解 n本文 10 行脚本
5. 因子光滑（p-1 光滑）p-1 光滑Pollard p-1sympy.factorint
6. 部分密钥泄露（LSB/MSB）已知 d 或 p 部分比特CoppersmithSage small_root
7. 选择密文（CCA）给定解密 oracle盲化解密pow(s,e,n)技巧
8. 已知 p 高位已知 p 的部分高位CoppersmithSage small_root
9. 已知 d 低位已知 d 的部分低位CoppersmithSage small_root
10. Fermat 分解p 和 q 接近Fermat 分解gmpy2.isqrt

0x03 详细推导 + 脚本

题型 1 低加密指数 e=3（无填充）

数学
若 m^3 < n，则 m = c^(1/3) 直接整数开方。如果 m^3 稍大于 n，可能存在 m^3 = k*n + c，可通过遍历小整数 k 来求解。

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import getPrime, bytes_to_long

# 生成弱e的RSA密钥
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 3

# 确保消息很小，使得 m^3 < n
m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
from Crypto.Util.number import long_to_bytes

def small_e_attack(c, e, n, max_k=1000000):
    for k in range(max_k):
        root, exact = gmpy2.iroot(k * n + c, e)
        if exact:
            return root
    return None

n =  # 从题目获取
e = 3
c =  # 从题目获取

m = small_e_attack(c, e, n)
if m is not None:
    print(long_to_bytes(int(m)))

题型 2 低解密指数 —— Wiener 攻击

数学
Wiener 定理：若 d < (1/3)N^(1/4)，则 k/d 是 e/n 的连分数收敛子之一。

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

# 生成小d的RSA密钥
def generate_weak_key():
    while True:
        p = getPrime(512)
        q = getPrime(512)
        n = p * q
        phi = (p-1)*(q-1)
        
        # 寻找小d
        d = gmpy2.next_prime(1 << 100)  # 小d
        try:
            e = gmpy2.invert(d, phi)
            if e.bit_length() == n.bit_length():
                return n, e, d
        except:
            continue

n, e, d = generate_weak_key()
m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
# https://github.com/pablocelayes/rsa-wiener-attack
from RSAwienerHacker import HackRSA

n =  # 从题目获取
e =  # 从题目获取

d = HackRSA(e, n)
if d is not None:
    from Crypto.Util.number import long_to_bytes
    c =  # 从题目获取
    m = pow(c, d, n)
    print(long_to_bytes(m))

题型 3 共模攻击

数学
给定两组 (e1,n),(e2,n) 加密同一 m，且 gcd(e1,e2)=1，则存在 x,y 使
e1*x + e2*y = 1
⇒ m = (c1^x * c2^y) mod n

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

# 生成共模RSA密钥
p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p-1)*(q-1)

e1 = 65537
e2 = 65539
# 确保e1和e2互素
assert gmpy2.gcd(e1, e2) == 1

m = bytes_to_long(b"flag{This_is_a_test_flag}")
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f"n = {n}")
print(f"e1 = {e1}")
print(f"e2 = {e2}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
from Crypto.Util.number import long_to_bytes

def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, x, y = gmpy2.gcdext(e1, e2)
    if gcd != 1:
        return None
    if x < 0:
        c1 = gmpy2.invert(c1, n)
        x = -x
    if y < 0:
        c2 = gmpy2.invert(c2, n)
        y = -y
    m = (pow(c1, x, n) * pow(c2, y, n)) % n
    return m

n =  # 从题目获取
e1 =  # 从题目获取
e2 =  # 从题目获取
c1 =  # 从题目获取
c2 =  # 从题目获取

m = common_modulus_attack(c1, c2, e1, e2, n)
print(long_to_bytes(m))

题型 4 dp 泄露攻击（考频最高）

数学
已知 dp = d mod (p-1)
⇒ e·dp ≡ 1 mod (p-1)
⇒ p - 1 | e·dp - 1
⇒ 遍历小因子 x | (e·dp - 1)，令 p = (e·dp - 1)/x + 1，检查 n % p == 0

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
d = gmpy2.invert(e, phi)

# 计算dp = d mod (p-1)
dp = d % (p-1)

m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"dp = {dp}")

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
from Crypto.Util.number import long_to_bytes

def dp_leak_attack(e, n, c, dp, max_x=1000000):
    k = e * dp - 1
    for x in range(1, max_x):
        if k % x != 0:
            continue
        p = (k // x) + 1
        if n % p == 0:
            q = n // p
            d = gmpy2.invert(e, (p-1)*(q-1))
            m = pow(c, d, n)
            return m
    return None

n =  # 从题目获取
e =  # 从题目获取
c =  # 从题目获取
dp =  # 从题目获取

m = dp_leak_attack(e, n, c, dp)
if m is not None:
    print(long_to_bytes(int(m)))

题型 5 Pollard p-1 分解

数学
若 p-1 所有素因子均 < B，则
a^(B!) ≡ 1 mod p
⇒ gcd(a^(B!) - 1, n) 非平凡

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

# 生成p-1光滑的素数
def generate_smooth_prime(bits, smoothness):
    while True:
        p = 2
        for i in range(2, smoothness):
            p *= i
            p = gmpy2.next_prime(p)
        if gmpy2.is_prime(p) and p.bit_length() == bits:
            return p

# 使用小素数生成p，使其p-1光滑
p = generate_smooth_prime(512, 1000)
q = getPrime(512)
n = p * q
e = 65537

m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2
from Crypto.Util.number import long_to_bytes

def pollard_p_minus_1(n, B=1000000):
    a = 2
    for i in range(2, B+1):
        a = pow(a, i, n)
        d = gmpy2.gcd(a-1, n)
        if 1 < d < n:
            return d
    return None

n =  # 从题目获取
e =  # 从题目获取
c =  # 从题目获取

p = pollard_p_minus_1(n)
if p is not None:
    q = n // p
    d = gmpy2.invert(e, (p-1)*(q-1))
    m = pow(c, d, n)
    print(long_to_bytes(m))

题型 6 部分私钥泄露 —— Coppersmith

场景
已知 d 低 256 位，或 p 高 128 位。

数学
利用 Howgrave-Graham 定理，把问题转化为 单变量模方程小根

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
d = gmpy2.invert(e, phi)

# 只泄露d的低256位
d_low = d & ((1 << 256) - 1)

m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"d_low = {d_low}")

解题脚本 (Sage)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Sage
n =  # 从题目获取
e =  # 从题目获取
d_low =  # 从题目获取
c =  # 从题目获取

kbits = 256  # 未知的位数

R.<x> = PolynomialRing(Zmod(n))
f = e * (d_low + x) - 1
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
    d = d_low + roots[0]
    m = pow(c, d, n)
    print(bytes.fromhex(hex(int(m))[2:]))

题型 7 选择密文攻击（CCA）

场景
服务器提供 decrypt(c) 返回 m = c^d mod n，但过滤 flag 关键字。

技巧
盲化：选随机 s，发送 c' = c · s^e mod n，得到
m' = m · s mod n
⇒ m = m' · s^(-1) mod n

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
d = gmpy2.invert(e, phi)

m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

# 模拟解密oracle，但过滤flag关键字
def decrypt_oracle(c):
    m = pow(c, d, n)
    msg = long_to_bytes(m)
    if b"flag" in msg:
        return b"Filtered: contains flag"
    return m

# 测试
print(decrypt_oracle(c))

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
from Crypto.Util.number import long_to_bytes

def cca_attack(decrypt_oracle, c, e, n):
    s = gmpy2.mpz_random(gmpy2.random_state(), n)
    c_prime = (c * pow(s, e, n)) % n
    m_prime = decrypt_oracle(c_prime)
    if m_prime == b"Filtered: contains flag":
        return None
    m = (m_prime * gmpy2.invert(s, n)) % n
    return m

n =  # 从题目获取
e =  # 从题目获取
c =  # 从题目获取

# 假设decrypt_oracle是远程服务
m = cca_attack(decrypt_oracle, c, e, n)
if m is not None:
    print(long_to_bytes(m))

题型 8 已知 p 高位攻击

数学
已知 p 的高位部分，设未知部分为 x，则 p = p_high + x，可建立方程：
(p_high + x) * q = n
利用 Coppersmith 方法求小根。

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537

# 只泄露p的高位（前400位）
p_high = p >> 112  # 512-400=112，保留高位

m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"p_high = {p_high}")

解题脚本 (Sage)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Sage
n =  # 从题目获取
e =  # 从题目获取
p_high =  # 从题目获取
c =  # 从题目获取

# 未知的位数
kbits = 112
R.<x> = PolynomialRing(Zmod(n))
f = p_high * (2^kbits) + x
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
    p = p_high * (2^kbits) + roots[0]
    q = n // p
    d = inverse_mod(e, (p-1)*(q-1))
    m = pow(c, d, n)
    print(bytes.fromhex(hex(int(m))[2:]))

题型 9 已知 d 低位攻击

数学
已知 d 的低位 d_low，设未知部分为 x，则 d = d_low + x 2^k。由 ed ≡ 1 mod φ(n)，可建立方程求小根。

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
d = gmpy2.invert(e, phi)

# 只泄露d的低位（后256位）
d_low = d & ((1 << 256) - 1)

m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"d_low = {d_low}")

解题脚本 (Sage)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Sage
n =  # 从题目获取
e =  # 从题目获取
d_low =  # 从题目获取
c =  # 从题目获取

kbits = 256  # 未知的位数

R.<x> = PolynomialRing(Zmod(n))
f = e * (d_low + x * 2^kbits) - 1
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
    d = d_low + roots[0] * 2^kbits
    m = pow(c, d, n)
    print(bytes.fromhex(hex(int(m))[2:]))

题型 10 Fermat 分解

数学
当 p 和 q 接近时，即 |p-q| 较小，令 a = (p+q)/2, b = (p-q)/2，则 n = a^2 - b^2。通过枚举 a 从 sqrt(n) 开始，检查 a^2 - n 是否为完全平方数。

加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2

# 生成接近的p和q
base = getPrime(512)
p = gmpy2.next_prime(base)
q = gmpy2.next_prime(p)  # p和q非常接近

n = p * q
e = 65537

m = bytes_to_long(b"flag{This_is_a_test_flag}")
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
from Crypto.Util.number import long_to_bytes

def fermat_factorization(n):
    a = gmpy2.isqrt(n)
    b2 = a*a - n
    while not gmpy2.is_square(b2):
        a += 1
        b2 = a*a - n
    b = gmpy2.isqrt(b2)
    return a + b, a - b

n =  # 从题目获取
e =  # 从题目获取
c =  # 从题目获取

p, q = fermat_factorization(n)
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))

0x04 综合例题 —— 0CTF 2021 Final rsa_revenge

题目附件

  • n = p*q 2048 bit
  • e = 0x10001
  • dp = ...
  • c = ...

解题流程

  1. 用 题型 4 脚本 秒出 p, q
  2. 正常 RSA 解密得 m
  3. 输出即为 flag

完整脚本（一步直达）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#!/usr/bin/env python3
import gmpy2
from Crypto.Util.number import long_to_bytes

e = 0x10001
n =  # 从题目获取
dp =  # 从题目获取
c =  # 从题目获取

def dp_leak_attack(e, n, c, dp, max_x=1000000):
    k = e * dp - 1
    for x in range(1, max_x):
        if k % x != 0:
            continue
        p = (k // x) + 1
        if n % p == 0:
            q = n // p
            d = gmpy2.invert(e, (p-1)*(q-1))
            m = pow(c, d, n)
            return m
    return None

m = dp_leak_attack(e, n, c, dp)
if m is not None:
    print(long_to_bytes(int(m)))

0x05 结语 & 资料汇总

资源链接
Wiener 攻击源码https://github.com/pablocelayes/rsa-wiener-attack
Boneh-Durfee Sagehttps://github.com/mimoo/RSA-and-LLL-attacks
CTF RSA 题库https://github.com/yifeng-lee/RSA-In-CTF
在线分解https://factordb.com

把本文脚本保存为 工具箱，下次比赛遇到 RSA 直接 python solve.py 拿 flag！