RSA基本概念

本文适合

已经理解模运算和大整数表示，准备处理 n,e,c 参数题、PEM 公钥题和裸 RSA 攻击题的 CTF 学习者。学完你能：根据 RSA 参数判断低指数、共模、共享素因子、近素数、dp/dq 泄露、Wiener 和 Coppersmith 等路线，并写出最小验证脚本。

一句话判断

RSA 题不是“破解 RSA”，而是找参数生成、填充、随机数或接口使用中的弱点；只要能从公开信息恢复 p,q,d 或直接恢复 m，就能解密。

题目中常见信号

给出 n, e, c

优先检查：基础 RSA 参数分析

e = 3 或很小，且无 padding

优先检查：小指数或广播攻击

多组 n

优先检查：批量 gcd 查共享素因子

p、q 位数接近或题目提示 consecutive

优先检查：Fermat/近素数分解

泄露 dp、dq、qinv、phi

优先检查：私钥参数恢复

d 很小或 e 异常大

优先检查：Wiener/Boneh-Durfee

明文有已知高位/低位

优先检查：Coppersmith 小根

有解密/签名 oracle

优先检查：同态、padding oracle 或签名伪造

核心概念

RSA 的公开参数是 (n, e)，其中 n = p*q。安全性依赖大整数分解困难和安全 padding。如果 n 可分解，就能计算 phi 和 d；如果没有 padding，m^e mod n 会保留太多代数结构，低指数、共模和相关消息攻击就有机会。

CTF 中要把参数先做成表：位数、组数、是否共模、是否同密文、是否共享素因子、是否有私钥残片。只有参数表清楚，后面的攻击选择才不会乱。

最小分析流程

1. 提取参数：从源码、文本或 PEM 中拿到 n,e,c，记录 bit 长度。
2. 小因子检查：用 gcd、factorint、FactorDB 或 RsaCtfTool 试快速分解。
3. 多组参数检查：批量 gcd(n_i, n_j) 找共享素因子。
4. 指数检查：e 是否很小，是否存在多组同明文广播。
5. 私钥残片检查：是否泄露 phi,d,dp,dq,qinv,p+q。
6. 如果简单路线失败，再考虑 Coppersmith、格攻击、oracle 或实现逻辑。

最小验证示例

from math import gcd
from Crypto.Util.number import inverse, long_to_bytes

n = 3233
e = 17
c = 855

# 示例里 n 很小，先直接分解。真实题可换成 factorint、FactorDB 或 RsaCtfTool。
p, q = 61, 53
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

# 多组 n 时的共享素因子验证骨架：
ns = [3233, 3599]
for i in range(len(ns)):
    for j in range(i + 1, len(ns)):
        g = gcd(ns[i], ns[j])
        if 1 < g < ns[i]:
            print("shared factor", g)

输出能转成可读 bytes 或 flag{...}，才说明当前分解/私钥恢复路线成立。

常见利用 / 解题路线

路线总览：

• 直接分解：n 太小、有小因子、FactorDB 已收录。
• Fermat：p 和 q 太接近，围绕 sqrt(n) 搜索。
• 共模攻击：同一 n、同一明文、不同互素指数。
• 低指数攻击：m^e < n 或 Hastad 广播攻击。
• 泄露私钥参数：由 phi、dp、dq、qinv 恢复 p,q,d。
• 小私钥指数：Wiener 或 Boneh-Durfee。
• 部分已知明文/素数：Coppersmith 小根，转向 格密码与LLL入门。

常见失败原因

解密 bytes 乱码

排查动作：检查 p,q 是否反了无所谓，但 phi 是否适合多素数或 p=q 特例

低指数开根失败

排查动作：判断是否真的 m^e < n，或需要 CRT 合并多组密文

共模脚本报 inverse 错

排查动作：检查 gcd(e1,e2)=1，不互素要走其他路线

FactorDB 查不到

排查动作：换 Pollard、Fermat、yafu、RsaCtfTool 或观察参数结构

Coppersmith 无根

排查动作：小未知量界限可能过大，先确认已知位方向和 padding 格式

迷你案例

题目给两份公钥和两个密文，n 相同，e1=3、e2=65537，描述说加密了同一条消息。先算 gcd(e1,e2)=1，再用扩展欧几里得求 a,b，满足 a*e1 + b*e2 = 1。于是：

m = c1^a * c2^b mod n

如果 a 或 b 为负，就对对应密文求模逆。最后 long_to_bytes(m) 得到 flag。这个链条比“跑共模攻击脚本”更适合写入 WP，因为它说明了为什么两个密文能合成明文。