RSA dp泄露如何快速分解n：D³CTF d3factor复盘

在 NSSCTF 平台上刷 Crypto 题的同学，大概率会在 RSA 专题里撞上这道来自 D³CTF 2022 的 d3factor。它给出的信息少得可怜：n、e、c 之外只多了一个 dp。但恰恰是这个 dp，让一个本该需要亚指数级算法才能分解的 2048 位大模数在几秒内被拆成两个素数。原因并不玄乎——dp 是私钥指数 d 对 p−1 取模的结果，它把 d 与 p−1 之间的整除关系赤裸裸地暴露了出来，而公钥指数 e 又足够小，于是顺着 e·dp ≡ 1 (mod p−1) 这条线索就能反推出 p 的候选值，逐个验证即可。这篇文章就一边复盘这道题的完整推导，一边把 RSA 参数泄露类题目的通用打法讲清楚，从数学原理到可以直接跑的脚本都写明白，读完既能复现这道 d3factor，也能迁移到其他 dp、dq、d 高位泄露的题上。

1. 拿到题目先把信息捋清楚：这道 d3factor 究竟在考什么

1.1 四个参数分别扮演什么角色

先把题目输出的四个量摆出来看：n是模数，e是公钥指数，c是密文，dp是私钥指数对 p−1 取模的结果。如果只看前三项，这就是一道标准 RSA 题，在没有分解出 n 的前提下手头几乎无牌可打——2048 位的模数用常规试除、费马分解、Pollard rho 都不现实。而dp的出现改变了整个局面。

很多刚接触 RSA 变种题的同学会把dp和d搞混。d是完整的私钥指数，满足e·d ≡ 1 (mod φ(n))；而dp只是 d 对 p−1 取模的余数，取值落在[1, p−2]区间内。从表面看它像是一串没什么意义的中间量，事实上它的信息密度非常高——它几乎等价于把 p 这一侧的"半把钥匙"直接递给了你。只要能从 dp 推出 p，剩下的 q、φ(n)、d 全部迎刃而解。

按 CTF 出题的常见习惯，这道题的核心代码大致长这样（根据同类题型常见模板整理，实际发布版本可能略有出入）：

from Crypto.Util.number import * from secret import flag m = bytes_to_long(flag) p = getPrime(1024) q = getPrime(1024) n = p * q e = 0x10001 d = inverse(e, (p - 1) * (q - 1)) dp = d % (p - 1) print("n =", n) print("e =", e) print("c =", pow(m, e, n)) print("dp =", dp)

1024 位素数、65537 公钥指数、只泄露 dp——这就是一道标准的"部分私钥曝光"型 RSA 题。它的学术背景也很扎实，属于侧信道攻击（fault attack、timing attack）里经常被引用的经典泄露模型：实现方为了加速解密，通常预先计算 dp 和 dq 并写进内存，攻击者一旦能从内存转储、功耗曲线或者日志里捞到这两个值，整把私钥就形同虚设。

1.2 为什么别的攻击路线都走不通

在动手写脚本之前，值得先把"为什么不走别的路"想清楚，这个思考过程的收益比多跑一遍脚本更大。

第一，直接分解 n 不现实。n 是 2048 位，两个素数都是 1024 位，能力对等，试除、Pollard p−1、Pollard rho 这些算法在常规算力下都跑不出结果。第二，小指数攻击（e=3 那类开方攻击）用不上，因为这里 e=65537，远大于明文可能对应的整数。第三，共模攻击要求同一明文在相同 n 下用互素的 e₁、e₂ 加密两份密文，本题只有一份密文，够不着门槛。第四，低加密指数广播也同理，单单一份密文根本凑不出条件。

排除之后你会发现，题目给出的唯一"超额信息"就是 dp，它必然就是唯一正解路径。这也是做 CTF 密码题一个通用判断方法：先清点题目给出哪些量，再对照标准 RSA 该有的量，多出来的那个量或者少掉的那个量，几乎一定是出题人留的突破口。

2. 核心原理拆解：为什么 e·dp − 1 一定是 p−1 的倍数

2.1 从 RSA 密钥生成流程讲起

要理解 dp 的价值，得先从私钥指数的定义倒推回去。在 RSA 中，私钥指数 d 满足：

e·d ≡ 1 (mod φ(n))

这里的 φ(n) = (p−1)(q−1)。这个式子的含义是 e·d − 1 能被 φ(n) 整除，也就是说存在某个整数 t，使得 e·d = 1 + t·(p−1)(q−1)。

现在关键的一步来了——因为(p−1)(q−1)本身一定是p−1的倍数，所以 e·d ≡ 1 (mod (p−1)(q−1)) 这个同余式，向下取模到 p−1 这一层仍然成立：

e·d ≡ 1 (mod p − 1)

这个降维在数学上只是"同余式对模数的因子也成立"这一条基本性质，但它把一篇 2048 位的式计算问题，压缩成了一个对 1024 位数的取模关系。

2.2 把 d 换成 dp 之后发生了什么

题目给的并不是 d，而是 dp = d mod (p−1)。代入上面的式子：

e·dp ≡ e·d ≡ 1 (mod p − 1)

因为 dp 和 d 对 (p−1) 同余，乘以 e 以后，它们对 (p−1) 仍同余。于是得到：

p − 1 | e·dp − 1

把它写成等式形式，就是整道题最关键的那一行：

e·dp − 1 = k·(p − 1)

其中 k 是某个整数。这个式子的直观含义是：e·dp − 1 这个由题目直接给定的巨大数字里，蕴藏着一个 1024 位的因子 p−1。剩下的事就是把这个式子从乘积结构里拆开——而 k 的取值范围被 e 牢牢限制住了，这让暴力枚举成为可能。

2.3 k 的取值范围是怎么被压到 65537 以内的

来看 k 能取多大。因为 dp 是 d mod (p−1) 的余数，自然有 0 ≤ dp < p−1，实际上 dp ≥ 1（否则 e·dp ≡ 1 mod (p−1) 无法成立，除非 p−1 本身就是 1）。所以：

e·dp − 1 < e·(p−1) − 1 < e·(p−1)

除以 (p−1) 立刻得到 k < e。又因为 e·dp − 1 > 0（dp ≥ 1，故 e·dp − 1 ≥ e−1 > 0），k 至少是 1。于是：

1 ≤ k ≤ e − 1

e = 65537 是个固定的常数，这意味着 k 的可能取值最多也就 65536 个。这个结论把原本看起来毫无头绪的分解问题，直接扔进了一个"最多循环六万多次"的区间。对比一下 2048 位模数在通用数域筛下的分解代价，这个穷举量小到几乎可以忽略。

2.4 应用时还要多一层验证

理论上如果 k 取对了，p = (e·dp − 1) / k + 1 就应该是 n 的因子。但实际上 e·dp − 1 可能对一些非正确的 k 也恰好整除，算出来的 p 却不是 n 的因子——这种"假阳性"完全可能存在，因为整除关系只是必要条件，不是充分条件。

因此每一步都要加一道验证：n % p == 0。这一步几乎不花时间，却能过滤掉所有假阳性。逻辑上真正能筛选出正确 k 的，是"这个 p 能否整除 n"这一条，而不是"这个 k 能否整除 e·dp − 1"。很多同学写脚本时只做整除判断接着就拿着算出的 p 去求 q，结果算出来是个非整数或解出乱码——原因就是没加这一步验证。

退一步想，即使某个 k 让你算出了 p，如果 p 不是素数，或者 n 除 p 得不到整数，这一轮就该立刻跳过。这套"整除性先筛、n 可除性再验"的双重过滤，实测下来执行几十毫秒就出结果。

3. 动手复现：从构造数据到跑出 flag 的完整流程

3.1 环境与依赖

这道题对环境的依赖非常轻。Python 3.x 加上pycryptodome（提供Crypto.Util.number里的long_to_bytes和inverse）就够了，不需要 SageMath，不需要任何外部数论库。如果本机已经装过 pycryptodome 直接用，没装的话：

pip install pycryptodome

需要说明一点：Python 原生就支持任意精度整数，pow的三参数形式在底层实现的是快速幂模运算，所以「计算pow(m, e*dp, n)这种指数高达几千位的幂」这件事本身并不慢，后面 gcd 解法会用到它，不用担心性能。

3.2 用可控参数构造一组自测数据

在正式解题目之前，先自己造一组和题目结构一致的数据，用来验证脚本正确性。好处有两层：一是能完整跑通整条链路，二是当题目给你的数据因为粘贴错误等原因跑不出结果时，这组自测数据能帮你区分"脚本写错了"还是"题目数据有问题"。

from Crypto.Util.number import getPrime, inverse, bytes_to_long def build_case(bits=512): p = getPrime(bits) q = getPrime(bits) n = p * q e = 0x10001 phi = (p - 1) * (q - 1) d = inverse(e, phi) dp = d % (p - 1) m = bytes_to_long(b"flag{self_test_d3factor}") c = pow(m, e, n) return {"n": n, "e": e, "c": c, "dp": dp, "p": p, "q": q, "m": m} case = build_case() print("p =", case["p"]) print("q =", case["q"])

把 p、q 留下来是为了后面验证脚本解出来的结果对不对。真实题目不会给你 p、q，但自测阶段必须留着核对。位数我故意从 1024 缩到 512，跑得快一些——枚举 k 的流程和位数完全无关，k 始终小于 65537，位数变化只影响单次大整数运算的耗时。

3.3 枚举 k 的分解脚本与逐行解读

现在把核心脚本写出来：

from Crypto.Util.number import long_to_bytes, inverse def factor_with_dp(n, e, dp): for k in range(1, e): if (e * dp - 1) % k != 0: continue p = (e * dp - 1) // k + 1 if n % p == 0: q = n // p return p, q return None, None p, q = factor_with_dp(case["n"], case["e"], case["dp"]) print("recovered p =", p) print("match:", p == case["p"] or p == case["q"])

这段代码有几个细节值得摊开来解释。

第一，range(1, e)生成的是 1 到 e−1，正好对应 k 的完整取值范围，不多不少。这里别写成range(1, e+1)或range(e)，虽然多试一个不会错，但语义上没必要。

第二，(e * dp - 1) % k != 0这一行是整段里最耗时的操作之一，因为e * dp - 1本身接近 2048 位。Python 的取模算法已经足够高效，每个循环微秒级别，六万多次下来零点几秒的时间，实测在普通笔记本上不到半秒。

第三，(e * dp - 1) // k + 1这一步的反推逻辑很直白——从e·dp − 1 = k(p−1)里解出 p，即p = (e·dp − 1)/k + 1。注意这里一定是整除，前面已经验证过了。

第四，n % p == 0这一行的价值在前面提过——它是最终确认正确 k 的唯一标准。哪怕 k 通过了整除性检查，只要它算出来的 p 除不动 n，就必须立刻跳过。

顺手再补一个细节：p有可能是 p 也有可能是 q，取决于你程序里 p 的定义是不是按照"dp = d mod (p−1)"来的。对这道题来说，p 和 q 谁是谁无所谓——后面求 φ(n)、求 d 都是对称的。实际写脚本时把返回的 p 非正式地当作 p 就可以。

3.4 用 p、q 还原私钥并解出明文

拿到 p、q 以后，剩下的解密流程就是标准 RSA 解密：

def decrypt(n, e, p, q, c): phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(c, d, n) return long_to_bytes(m) pt = decrypt(case["n"], case["e"], p, q, case["c"]) print("plaintext =", pt)

inverse(e, phi)要求gcd(e, phi) == 1。本题 e = 65537 是素常数，phi 是两个偶数乘积（p−1 和 q−1 都是偶数），所以互素性只需保证p−1和q−1都不同时被 65537 整除，这在大素数随机生成下是默认成立的。

long_to_bytes把大整数按大端序转回字节串，得到真正的 flag。如果解出来的字节串里混杂着不可打印字符，或者开头少了一两个字符，八成是某个地方多乘、少除，回头从e·dp − 1 = k(p−1)这一行开始核对。

3.5 gcd 解法：不用枚举 k 也能分解

除了枚举 k，还有一个相当漂亮的思路——直接用 gcd 把 n 拆掉，完全绕过枚举。做法是：随机取一个整数 m（比如 2、3、7），计算

gcd(pow(m, e*dp, n) − m, n)

为什么能拆？因为对 p 来说：

m^(e·dp) ≡ m^(e·d) ≡ m (mod p)

中间这一步用的是e·dp ≡ e·d ≡ 1 (mod p−1)。也就是说p | pow(m, e·dp, n) − m。而 q 这边通常不成立（除非碰巧），所以 gcd 的结果就是 p 的倍数，通常直接是 p。

完整实现大概是这样：

from math import gcd def factor_with_gcd(n, e, dp): for base in (2, 3, 5, 7, 11, 13): g = gcd(pow(base, e * dp, n) - base, n) if 1 < g < n: return g, n // g return None, None

这种思路的优点是调用次数是常数级（最多试几个 base），缺点是工程上不严谨——如果 base 恰好是 p 的倍数，pow(base, e*dp, n) − base就整个是 p 的倍数，gcd 会返回 p 的倍数；如果 base 恰好是 q 的倍数，则 gcd 会返回 q 的倍数，也不是灾难，只要换 base 再试一次就能拿到 p。工程实践中把这两种写法都挂着，哪种先出结果用哪种，是最稳妥的做法。

实测下来，枚举 k 和 gcd 两种方法的耗时都在毫秒到百毫秒数量级，没有谁碾压谁的说法。选哪种更多看个人习惯——枚举 k 的思路完全暴露在数学推导里，任何一步都能回查；gcd 解法优雅，但对"为什么 gcd 一定是 p"这一层要转过弯来才能理解透彻。

4. 变体与进阶：dp 没给全的情况怎么办

4.1 dp 高位泄露与 Coppersmith 的介入

实际比赛里还有一种常见的变体——只给 dp 的高位，比如给出dp = dp_high * 2^t + dp_low，其中dp_low的位宽是 t，题目只输出dp_high。这种情况下枚举 k 之后得到的 p 只能精确到大约2^t·e/k的误差，不再是一个确切值。

推导一下误差：对某个确定的 k，

p = (e·dp − 1)/k + 1 = (e·dp_high·2^t + e·dp_low − 1)/k + 1

把p₀ = (e·dp_high·2^t − 1)/k + 1当近似值，那么p − p₀ = e·dp_low/k，误差量级约e·2^t / k。但注意还有−1/k项带来的偏移，且 p₀ 本身对 k 不一定整除，比较稳妥的做法是把 p₀ 向下取整。

接下来就是 Coppersmith 的舞台了——p 是 n 的素因子，且|p − p₀| < X，其中 X 大约是e·2^t/k。构造多项式f(x) = p₀ + x，去求它在模 n 意义下的小根，而根就是p − p₀。Coppersmith 处理的是"模数为 n 的因子"的情形，通常要对模 p（未知）做处理，本质上使用的是p > n^0.5这一性质，用 SageMath 的small_roots配合X上限就能跑。

关键限制是X < n^0.25（以因子情形看，误差必须显著小于n^0.25）。当 t 比较小，比如只丢了低 64 位，X ≈ e·2^64 ≈ 2^80，对 1024 位的 p 完全在可解范围内。但若 t 接近 p 的一半位数，误差可能超过n^0.25的门槛，Coppersmith 就无解了。

4.2 dp、dq 同时给出：直接走 CRT 或分别枚举

有些题会同时给出 dp 和 dq，也就是d mod (p−1)和d mod (q−1)。这种情况解法有两路选：

第一条，仍然沿用前面的枚举 k 思路，分别对 dp 求 p、对 dq 求 q，交叉验证得到两个素数。由于 e 固定，两次枚举总量仍是2e次，毫秒级。

第二条，注意到e·dp ≡ 1 (mod p−1)、e·dq ≡ 1 (mod q−1)，且p − 1和q − 1各自整除e·dp − 1和e·dq − 1，于是两个素数分别落在两个不同的整除关系里。因为 p、q 各自独立，这一步没法定序，但枚举 k 的时候一边一半地试，实测下来效率也够。

还有一个更巧的做法：由e·dp − 1 = k₁(p − 1)和e·dq − 1 = k₂(q − 1)，两式相乘再展开，可以利用两者组合搜索的思路来缩小搜索空间，效果不错但有实现复杂度，不是非必要手段。

4.3 多次采样或多组密文的联合攻击

如果是更强的变体——比如 dp 值不可直接拿到，但通过 fault attack 得到了同一个明文在相同 n 下两份密文 c₁、c₂，且 c₁ 的加密过程中 dp 出现了硬件错误（某一位翻转），那么可以用gcd(c₁ − c₂, n)的思路快速分解。这类攻击属于"故障注入攻击"的范围内，和 d3factor 的纯数学构造不是同一条线，但内核都是"利用已知信息缩小未知量搜索范围"，思路可以互相迁移。

还有一类更贴近 CTF 常见的变体：给出多组(n, e, c)且共用相同私钥的不同切片信息，配合中国剩余定理（CRT）来整合。这种题解完之后再回头复习 d3factor，会有种"殊途同归"的感觉——所有的 RSA 变种最终都在回答"如何把 1024 位未知量压进一个可以穷举的空间"。

5. 踩坑实录与常见问题速查

5.1 枚举里 p 对不上是什么原因

最常见的一种翻车情况，是脚本跑完了但没拿到正确的 p，返回值还是None。这时候按顺序排查：第一，题目输出的 dp 有没有抄错，多一位、少一位、数字顺序错都会导致整除关系不成立；第二，e是否被误当成 3 或者别的值——本题是 65537，如果题目里 e 被改小过，那枚举上限1 ≤ k < e的推导就不一样了；第三，循环有没有写成range(1, e + 1)，虽然不多错，但如果是range(e)就把 k=e 的情况跳过了——理论上 k 取不到 e，但有些题目里 k 恰好是 e 也能整除，宁可多试一个不影响结果。

还有一类隐蔽的情况：题目给出的 dp 经过了伪装，比如给的是dp >> 2或dp * 2，需要先还原。这只能在提交后根据结果不对再回头猜，具体看题目形式。做这类题一个通用习惯是，拿到 dp 先试试e * dp - 1能不能被一个小整数整除，验证一下到底是不是"原生"的 dp 定义。

5.2 明文转字节这一步的坑

第二类常见问题出在最后的明文还原上。pow(c, d, n)得出来的是一串大整数，正常应该能通过long_to_bytes转成 flag 格式的字节串。如果解出来的字节串开头多了几个\x00，那是整数本身有效位数没对齐的原因；如果末尾混杂着乱码，通常是明文转整数时用了小端序、又或者整数m的位长不够导致的。有些题目还会在加密前对明文做过 padding，这种情况下解出来的整数就不是原始 flag 字节串，需要先按题目给的 padding 方案去掉填充部分再转字节。

另外一个易踩的坑：long_to_bytes在碰到整数 0 时返回b''，而不是一个空字节。如果解出来的明文开头有真实存在的 0 字节（比如某个编码里正好是\x00），转出来会少掉它。这类问题很少见，但排查时知道有这一层就不会乱猜。

5.3 一个容易被忽略的性能问题

e·dp这个乘积的位数不算小——dp 接近 1024 位，乘上 65537 之后达到 1040 位左右。在 Python 里做e * dp - 1重新算乘积，如果循环里每次都做，虽然 Python 会缓存部分中间结果（因为 e 是常量），但最稳妥的做法是先算一遍epd = e * dp - 1存成变量，循环里直接用：

epd = e * dp - 1 for k in range(1, e): if epd % k == 0: p = epd // k + 1 if n % p == 0: ...

这种优化对 65537 次循环效果不明显（实测也就差几毫秒），但代码可读性上升不少，循环里做的事情更聚焦，出了 bug 也更容易排查。

5.4 常见问题速查表

6. 把这道题的解法迁移到其他 RSA 参数泄露题上

d3factor 最值得带走的东西不是那段枚举 k 的脚本，而是一套判断框架。碰到任何"多给了一个参数"的 RSA 题，先问三件事：这个参数和标准 RSA 里的哪个量对得上；它让你能写出哪个整除或同余关系；这个关系里的未定整数（这里就是 k）是否被某个固定参数（这里就是 e）限制在了可穷举的小范围里。

拿这套去套其他常见泄露题，几乎都能对上。若泄露的是d mod (p−1)之外的dq = d mod (q−1)，同样的推导路径，只是等式两边的 p 换成 q。若泄露的是完整的 d，那更简单，直接用 d 解密甚至不需要分解 n。若泄露的是d的高位，那通常要靠 Coppersmith 处理部分密钥暴露问题，误差要压到n^{0.25}以下才行。若泄露的是 p 的高位，那本质是"已知一个素数的高位"的分解问题，用 Coppersmith 在x很小时求根即可。

在 CTF 里更常见的是dp和dq中只给一个的变体——只要完整给出一个，这题就基本等于是送分。反过来，如果题目同时给出dp、dq却故意把其中一个给高位或给低位，那组合搜索和 Coppersmith 的复杂度都会上去一些，需要选好误差界 X 和网格参数。

还有一个容易被忽略的延伸方向：e不是 65537 的情况。如果 e 特别大，比如几百位，那 k 的取值范围0 < k < e就失去了意义，枚举 k 不再可行。这时需要转向 Coppersmith 或者其他结构性攻击（比如e与 φ(n) 的公共因子分析、Håstad 广播的变种等）。这也从另一个侧面说明 d3factor 把 e 设成 65537 是有意而为之的——固定的小公钥指数是所有这类攻击能成立的先决条件。

最后分享一个我在做这类题时的习惯：碰到任何"只多给了一个数"的 RSA 题，先不要急着写脚本，在纸上把标准 RSA 的所有关系式列出来——e·d ≡ 1 (mod φ(n))、p·q = n、φ(n) = (p−1)(q−1)、ed − 1 = t·φ(n)——然后把多出那个量代进每一个式子，看哪一条能化出新的可解关系。就 d3factor 这道题而言，把 dp 代进e·d ≡ 1 (mod p−1)得到的那一行，基本就锁定了 90% 以上的解题路径，剩下的都是执行层面的细节。这套"先列公式、再代入、最后判断搜索范围"的方法，比一上来就抓瞎试各种攻击要靠谱得多。