RSA 深入实战：原理、小 n 分解与共模攻击

一、现实背景：DH 与公钥密码学

HTTPS（TLS）流程中：先用 DH 协商对称密钥，再用 RSA/ECDSA 证书认证身份。DH 解决"公开信道建立共享密钥"，RSA 解决"身份认证与加密"。

DH 最小实现（见密码学全景篇）：

p, g = 0xffffffffffffffc5, 2
a, b = 1234567, 7654321
A, B = pow(g, a, p), pow(g, b, p)
assert pow(B, a, p) == pow(A, b, p)   # 双方共享密钥一致

RSA 的安全基础是：已知 n 求 p、q（分解）在计算上不可行。CTF 题把参数做小或做错，让分解或绕过分解成为可能。

二、环境准备

pip3 install pycryptodome sympy gmpy2

三、核心知识：RSA 公式

n = p × q
φ(n) = (p-1)(q-1)
e × d ≡ 1 (mod φ(n))        # d 是 e 的模逆元
加密：c = m^e mod n
解密：m = c^d mod n

三个必须会用的 Python 运算：

pow(3, 4, 7)        # 快速幂取模 = 4
pow(e, -1, phi)     # 求 e 在模 phi 下的逆元

四、核心步骤 1：手算验证

目的：用最小参数亲手跑通 RSA 的生成与加解密，确认公式理解正确。

思路：先算 n 与 φ(n)，再求 d（e 的模逆元），最后验证 pow(c,d,n) 能还原 m。这四步是后面所有攻击的基础。

p, q, e = 61, 53, 17
n = p * q
# n = 3233，公钥模数。
phi = (p - 1) * (q - 1)
# φ(n) = 60 × 52 = 3120，欧拉函数值。
d = pow(e, -1, phi)
# pow(e, -1, phi)：求 e 在模 phi 下的乘法逆元，即私钥 d = 2753。

m = 65
c = pow(m, e, n)
# pow(m, e, n)：快速幂取模，即 m^e mod n，加密得 c = 2790。
print("n =", n)
print("phi =", phi)
print("d =", d)
print("c =", c)
print("解密 =", pow(c, d, n))
# pow(c, d, n)：用私钥解密，应还原 65，验证公式正确。

实际输出：

n = 3233
phi = 3120
d = 2753
c = 2790
解密 = 65

攻击者只有 (n=3233, e=17, c=2790)，没有 d。要解密，第一步就是分解 n。

五、核心步骤 2：小 n 分解

目的：拿到公钥后第一步永远是"尝试分解 n"——一旦分解成功，私钥直接可算。

思路：n 小 → 本地工具直接分解；n 大 → 先查 FactorDB 是否有人分解过。分解出 p、q 后按公式算出 d 解密。

5.1 用 sympy 分解

from sympy import factorint

print(factorint(3233))

实际输出：

{53: 1, 61: 1}

得到 p=53, q=61。

5.2 完整解密（验证公式）

思路：分解得到 p、q → 算 φ(n) → 算 d → pow(c,d,n) → long_to_bytes 转回文本。

from Crypto.Util.number import long_to_bytes
# long_to_bytes(x)：把大整数转成字节串（高位在前），用于查看解密出的文本。

n = 3233
e = 17
c = 2790
p, q = 53, 61

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
# 解密：m = c^d mod n。

print("m =", m)
print(long_to_bytes(m))
# 65 对应 ASCII 字符 'A'，说明这个最小例子只能承载一个字节的明文；
# 真实题目的 n 足够大，能装下整个 flag，方法完全一样。

实际输出：

m = 65
b'A'

65 对应的 ASCII 字符是 A。真实的明文是 flag 对应的长整数，但解密公式完全相同。

5.3 用 FactorDB 查

如果 n 太大本地分解不动，去 https://factordb.com 粘贴 n 查询，或：

from factordb.factordb import FactorDB

f = FactorDB(n)
f.connect()
p, q = f.get_factor_list()

六、核心步骤 3：共模攻击

6.1 场景

同一个 n、两个互质的 e1, e2、同一明文：

c1 = m^e1 mod n
c2 = m^e2 mod n

6.2 数学原理

目的：理解为什么"两个密文能拼出明文"。

思路：扩展欧几里得求出 a、b 使 a×e1+b×e2=1；把两个密文分别取 a、b 次方再相乘，指数恰好合并成 1，明文就还原了。验证方式：恢复结果与原始 m 相等。

扩展欧几里得算法求出 a, b 使：

a × e1 + b × e2 = 1

则：

c1^a × c2^b
= m^(a×e1) × m^(b×e2)
= m^(a×e1 + b×e2)
= m^1 = m (mod n)

6.3 完整代码

def egcd(a, b):
    # 扩展欧几里得算法：返回 (gcd, x, y)，满足 a*x + b*y = gcd(a,b)。
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

n = 3233
e1, e2 = 17, 19
m = 65
c1 = pow(m, e1, n)      # 2790：e1 加密结果
c2 = pow(m, e2, n)      # 232：e2 加密结果

_, a, b = egcd(e1, e2)
# 忽略第一个返回值（gcd=1），取 a、b。
print("a =", a, "b =", b, "a*e1+b*e2 =", a*e1 + b*e2)
# 应输出 a=9, b=-8，验证 9×17 + (-8)×19 = 1。

# 负指数要先取模逆元
if a < 0:
    c1 = pow(pow(c1, -1, n), -a, n)
    # pow(c1, -1, n)：c1 在模 n 下的逆元；再取 -a 次方（-a 为正）。
else:
    c1 = pow(c1, a, n)
if b < 0:
    c2 = pow(pow(c2, -1, n), -b, n)
else:
    c2 = pow(c2, b, n)

recovered = (c1 * c2) % n
# c1^a × c2^b = m^(a·e1 + b·e2) = m^1 = m (mod n)。
print("恢复 m =", recovered)
# 预期 65，与原始 m 相等，攻击成功。

实际输出：

a = 9 b = -8 a*e1+b*e2 = 1
恢复 m = 65

七、其他常见攻击速查

场景	攻击
`e=3` 且 `m^e < n`	直接开立方根（`gmpy2.iroot(c, 3)`）
同一明文发给 3 个不同 n	Håstad 广播攻击（中国剩余定理 + 开方）
e 特别大（d 很小）	Wiener 攻击（连分数）
p、q 很接近	Fermat 分解（平方差）
泄露 dp	枚举 k，`p = (e*dp-1)//k + 1`

八、必学工具

工具	3 个核心功能	示例
pycryptodome	`long_to_bytes`、`inverse`、`pow(m,e,n)`	见上文
sympy	`factorint` 分解	`factorint(3233)`
RsaCtfTool	自动尝试多种攻击、从公钥文件读取	`./RsaCtfTool.py -n N -e E --uncipher C --attack all`

FactorDB（https://factordb.com）用于查 n 的已知分解。

九、小 CTF 实战

题目：

n = 1000000016000000063
e = 65537
c = 856868007642616233

说明：真实题目的 n 有数百位，这里为了能在本地秒级分解，使用 19 位 n；分解方法完全一致。

第一步：分解

思路：n 只有 19 位，sympy 的 factorint 用试除/快速算法秒级分解；若 n 更大，改用 yafu 或查 FactorDB。

from sympy import factorint
print(factorint(1000000016000000063))

实际输出：

{1000000007: 1, 1000000009: 1}

第二步：解密

思路：与 5.2 完全相同的公式，只是参数换成实际值；输出 b'flag' 说明解密成功。

from Crypto.Util.number import long_to_bytes

n = 1000000016000000063
e = 65537
c = 856868007642616233
p, q = 1000000007, 1000000009

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, n)))

实际输出：

b'flag'

第三步：工具验证

./RsaCtfTool.py -n 1000000016000000063 -e 65537 --uncipher 856868007642616233 --attack all

十、小结

RSA 解题顺序：先查 n 能否分解（FactorDB/sympy）→ 能分解就按公式解密 → 不能分解就检查共模、低指数、Wiener、Fermat 等结构性错误。每个攻击对应一种"实现错误"，识别特征后套模板即可。