RSA的dp泄露，在CTF密码学里属于那种"原理一句话、实战随手写"的经典题型。题目名经常就叫leak，打开压缩包看到一个Python源文件或者txt文本，里面躺着几个大数：n、e、dp、c，然后要求你解出明文。我第一次做这类题是在几年某高校赛2020的leak题目上，当时连dp是私钥参数都不知道，更想不通为什么网上都说"dp泄露等于RSA被攻破"。这篇文章我就从dp的来历说起，把攻击的数学推导和可以直接跑的攻击脚本完整过一遍。适合刚接触RSA攻击面、想在CTF里稳定拿分的选手，也适合那些做密钥管理、想知道"私钥拆分参数为什么不能乱打印"的工程同学。

1. 拿到leak题：先搞清手里有什么，别急着上脚本

CTF里RSA方向的题目有个通病，就是很多初学者一看到大整数就下意识想"是不是能直接分解n"，或者在factordb上查一查。但实际上了2020位左右的模数n，只要不是用已知脆弱素数生成，在线分解根本没戏。这类题的价值不在于硬刚因子分解，而在于题目给了你一把"额外钥匙"——dp。

先说题目文件的常见样子。通常是下面这种格式：

n = 0x... e = 65537 dp = 0x... c = 0x...

也有可能是一个txt文本，用换行分隔，甚至带注释。第一步要做的是把每个参数完整读进来，并快速确认它们的量级：

肉眼扫一遍就知道，n是2048位，e是常用的65537，dp大约1024位。这正好是标准RSA私钥中用中国剩余定理加速解密时该有的大小。所以题目一点都不"偏"，它考的是一个真实存在的私钥组成部分。

拿到题目之后，我习惯先做一个"攻击面排除清单"：

• 能不能直接分解n？2048位随机素数，不能。
• 是不是共模攻击？只有一个n、一个c，没有多个密文，排除。
• 低加密指数攻击？e=65537不算低，排除。
• 低解密指数攻击（Wiener之类）？不知道d，题目也没暗示d很小，排除。
• 已知p、q？没有直接给。
• 那剩下的突破口就是dp了。

为什么dp能成为突破口，这正是第二小节要展开的内容。但先别急，动手之前我还要再检查一件事：e*dp-1是否太大或太小，以及dp和n的位数关系是否正常。正常情况下dp略小于p，也就是1024位左右。如果题目里dp比n的一半还长，反而说明数据格式有可能读错了，比如把十六进制字符串当成十进制读，或者把d当成了dp。

另外一个小经验：题目数据如果是十六进制，一般带0x前缀；如果是从文件里粘贴出来，偶尔会混进换行符、空格甚至中文逗号。写脚本的时候我建议养成"暴力清理"的习惯，把所有非十六进制字符过滤掉，再用int(x, 16)统一转换。这一步能避免后面百分之八十的"灵异bug"。

2. dp是怎么来的：中国剩余定理加速，顺便留了个后门

2.1 私钥里为什么会有dp和dq

标准RSA里，私钥本质上只需要(n, d)就够了：解密时直接算m = c^d mod n。但实际工程里几乎没人这么写私钥，因为大整数模幂运算太慢了。解密指数的位数和n一样，意味着指数乘法次数巨大。为了解决性能问题，从PKCS#1开始，私钥文件里除了n和d，还会保存p、q、dp、dq、qInv这一堆CRT参数。

CRT加速的原理很简单：解密之后需要算c^d mod n。由于n=p*q，可以分别算：

m1 = c^d mod p m2 = c^d mod q

但d直接对p和q取模时，指数还能进一步缩小。根据费马小定理的推广，c^d mod p只取决于d对p-1的余数，c^d mod q只取决于d对q-1的余数。于是人们定义：

dp = d mod (p-1) dq = d mod (q-1)

这样两个模幂运算的指数从2048位直接降到1024位。一次模幂的大数乘法复杂度约是位数的三次方量级，2048位指数的成本大约是两个1024位指数各自成本之和的四倍左右，所以CRT差不多能把解密速度提升到原来的四倍。对高频解密的服务器来说，这是巨大优化。

代价是什么？代价就是私钥材料变多了，任何一个参数泄露，都可能把整把私钥拆掉。dp就是其中最致命的一个。

2.2 dp泄露为什么致命：一个整除关系就能倒出p

设私钥满足最常用的生成方式，也就是：

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

其中 φ(n) = (p-1)(q-1)。因为φ(n)是(p-1)的倍数，所以等式两边同时对(p-1)取模，一定有：

e*d ≡ 1 (mod p-1)

又因为dp = d mod (p-1)，所以d与dp对(p-1)同余，于是：

e*dp ≡ 1 (mod p-1)

展开成等式就是：

edp - 1 = k(p-1)

其中k是某个正整数。你看，这个等式里e、dp都是已知的，唯一不知道的是k。但k的范围有一个天然限制：因为dp一定小于p-1，所以：

edp - 1 < e(p-1)

也就是说：

k = (e*dp - 1) / (p-1) < e

所以k一定落在区间 [1, e-1] 里。当e=65537时，最多枚举65536个k。对计算机来说，这个数量小到可以忽略。每一个候选k都能算出一个候选p：

p = (e*dp - 1) // k + 1

只是需要确认这个候选p是不是真的等于N的因子。验证方法也简单：用p去除n，能整除就说明找对了。

这里我常用一个生活化类比帮助记忆：假设你知道一把钥匙的"齿根余数"（dp），又知道齿轮比（e），你只要在很小的范围内猜"圈数"（k），就能反推出齿轮的周长（p-1）。圈数上限取决于齿轮比，所以只要e不大，猜起来非常快。

2.3 为什么e=65537是攻击能成立的关键

前文推导里最关键的一环，就是k的枚举上限是e。如果e取65537，枚举6万多次完全没压力。但假如出题人把e换成一个大随机数，比如10^30量级的素数，那这个暴力枚举方案就直接失效了。这也是为什么CTF里几乎所有dp泄露题都把e固定成65537——不是为了降低难度，而是因为工程实践中RSA公钥指数几乎默认就是65537，出题人只是还原了真实场景。

顺带一提，如果真遇到e特别大的dp泄露题，通常还有更高级的解法，涉及连分数逼近或格基约化来估计k，但那种题已经超出"leak"这种入门题的范围了。先把65537这套玩明白，再做扩展。

3. 实战攻击脚本：从n、e、dp、c到flag的完整链条

3.1 先造一个可复现的教学靶场

真实的CTF题目数据很长，贴出来既占篇幅，又不利于独立验证。我更推荐的做法是自己现场生成一组RSA参数，把dp当作"泄露值"输出，然后用攻击脚本还原明文。这样整个流程完全可控，读者也能复现。

下面是生成靶场数据的脚本：

from Crypto.Util.number import getPrime, bytes_to_long, inverse # 生成两个1024位素数，模拟真实RSA密钥 p = getPrime(1024) q = getPrime(1024) n = p * q e = 65537 phi = (p - 1) * (q - 1) d = inverse(e, phi) # 计算CRT加速参数dp，也就是我们要泄露的值 dp = d % (p - 1) # 加密一段明文，模拟题目给的密文 m = bytes_to_long(b'flag{demo_dp_leak_attack}') c = pow(m, e, n) print(f'n = 0x{n:x}') print(f'e = {e}') print(f'dp = 0x{dp:x}') print(f'c = 0x{c:x}')

运行之后，你会得到一组类似题目格式的输出。注意这里dp低位看起来可能比p短一点，这很正常，因为dp是d对p-1取余的结果，天然小于p。

我特意把n、dp、c都打印成十六进制，就是为了模拟题目文件里最常见的样式。有些题目直接用十进制整数，其实原理一样，脚本里去掉int转换即可。

3.2 攻击脚本逐行解读

现在写攻击脚本。核心思路就是枚举k，计算候选p，验证整除性，找到p之后一切就都顺了。

from Crypto.Util.number import long_to_bytes from gmpy2 import invert # 把题目给的十六进制字符串填进来 n = int('0x...', 16) e = 65537 dp = int('0x...', 16) c = int('0x...', 16) for k in range(1, e): # 必须整除，否则e*dp-1不可能是k*(p-1) if (e * dp - 1) % k == 0: p = (e * dp - 1) // k + 1 # 验证找到的p真的是n的因子 if n % p == 0: q = n // p phi = (p - 1) * (q - 1) d = invert(e, phi) m = pow(c, d, n) print(long_to_bytes(m)) break

这段脚本短，但每一行都有讲究。

先看for循环：range(1, e)覆盖了1到e-1所有整数，k=e的情况不可能成立，因为那把p-1算得太小，会导致dp等于p-1，而dp作为余数最大只可能是p-2。所以这个区间是精确命中。

再看整除判断：(edp-1) % k == 0。这个判断不是可有可无的优化，而是逻辑正确性的保证。因为从数学上说，k(p-1) = edp-1是严格等式，如果k不能整除edp-1，那这个k对应的p本身就无意义，直接跳过。

n % p == 0是第二道保险。理论上正确的k只会有一个，整除验证能排除掉那些虽然整除条件满足但算出来的p不是n因子的情况。

找到p之后，q = n // p，φ(n) = (p-1)(q-1)，然后用invert(e, phi)求模逆得到d，最后正常解密。这里我用gmpy2.invert而不是Python内置的pow(e, -1, phi)，主要是考虑到CTF环境里gmpy2更通用、速度也更好。如果本机没装gmpy2，pip install gmpy2就能搞定；Windows上通常有预编译wheel，Linux下可能需要先装libgmp。

3.3 跑一遍，看到flag

把上一节生成的演示数据填进攻击脚本，运行效果大致是：

b'flag{demo_dp_leak_attack}'

整个过程从启动到出结果，通常一两秒就完事。65536次循环里绝大多数k在第一道整除判断就被过滤掉了，实际进入第二轮判断的可能只有几个。这一步跑通之后，你就亲手复现了完整的dp泄露攻击。

说实话，第一次跑通这个脚本时，我是有点震撼的。因为从头到尾我并没有拿到真正的私钥d，只是泄露了一个看起来"无关紧要"的余数dp，结果整个私钥结构就跟多米诺骨牌一样塌了。这种感觉会让人对"私钥参数敏感性"产生非常直观的敬畏。

4. 边界条件和踩坑：这类题最容易挂掉的地方

4.1 数据格式导致的心智崩坏

CTF题目给的"大数"经常以各种奇怪形态出现。我见过最坑的几种：

• 十六进制字符串大写0X开头，直接int(s, 16)没问题，但如果混入换行和空格，转换会报错。解决办法是先过滤：''.join(filter(lambda x: x in '0123456789abcdefABCDEF', s))
• 有的题目把n、e、dp、c放在JSON或字典里，键名大小写不一致，读的时候别顺手写错。
• 有的题目故意把dp的高位裁掉，或者补上无意义的0，需要观察位数是否合理。

我的习惯是，无论什么格式，先打印每个参数的字符串长度和十六进制位长，确认都符合"n约2048位、dp约1024位"的预期。一旦发现dp长度明显偏大或偏小，先怀疑解析问题，再怀疑题目另有玄机。

4.2 整除判断和循环边界

如果攻击脚本死活不出结果，最常见的原因是循环写成了range(1, e+1)且中间多了一个不该有的break条件？其实range(1, e+1)也能跑通，因为k=e时算出的p基本不可能通过n%p验证。真正容易出问题的地方是：

• 忘记判断(e*dp-1) % k == 0就直接用整数除法，分母虽然不会为0，但会产生大量无效候选p。
• p算出来之后没有验证n % p，而是直接拿它当素数用，导致后面的phi算错，解出来一堆乱码。
• dp读成了十进制而不是十六进制，虽然数值上也能跑，但枚举效率瞬间退化到不可接受。

另外说一下，如果题目给的e不是65537而是几百、几千的小素数，循环照样能跑，只是更快。如果e是65537这个标准值，性能完全不用担心，普通笔记本一秒内出结果。

4.3 变体和"看似dp但其实不是"的情况

有些题目会同时给出dp和dq，这种就更简单了，用dp或者dq任意一个都能走通上面的流程，不用两个都用。如果题目只给dq，把脚本里的dp换成dq、p换成q，逻辑完全对称，照样能解。

还有一种阴间出题法：文件名叫leak，实际给的却是p的高位或者d的低位，那就不是dp泄露题了，得走Coppersmith部分密钥泄露攻击的路子。所以做题前一定要先确认参数名和数值关系，别拿着dp的脚本死磕。判断标准很简单：dp是否满足e*dp-1能整除某个小k且推出p整除n。如果试了几千个k都没结果，也许就该重新审题了。

还有一个值得说的坑：如果m比n大，bytes_to_long之后加密没问题，但解密后long_to_bytes可能解出比预期长的内容。实际RSA加密里m必须小于n，题目也会保证这一点，所以一般不用管。但如果你自己造靶场时不小心用超过n长度的明文，就会看到"解密出来一个很长的奇怪bytes"，那不是脚本错了，是初始条件不合法。

5. 更进一步：dp泄露的本质，以及怎么防

5.1 从私钥文件视角看泄露面

很多人以为RSA私钥只有(n, d)两个参数，所以泄露dp不算"泄露完整私钥"。但看完前面的推导应该已经明白：只要知道n、e、dp，就能恢复p和q，进而算出d。这意味着dp的敏感程度和d完全等价。

实际工程里，PKCS#1格式的私钥文件里本来就存了一整套CRT参数：p、q、dp、dq、qInv，全部是明文结构。无论哪个环节把它们打印到日志、写入临时文件、报错堆栈，或者通过侧信道被提取出来，整把私钥就都完了。所以做密钥管理的人看这类题，不应该只当笑话看，而应该当成安全审计的警钟。

举几个真实项目里常见的泄露场景：

• 调试代码时print(dp)，然后忘了删，上线后日志系统把私钥参数一起存了。
• 内存崩溃后dump文件被收集分析，里面带着解密中间过程的临时变量。
• 加密机或HSM的API设计不当，允许查询CRT参数而不做权限校验。
• 代码仓库意外提交了包含测试私钥的配置文件，而测试私钥是拿真实参数生成的。

以上每一条，攻击者拿到dp之后都能离线恢复完整私钥，连在线爆破都不需要。

5.2 防御角度怎么落地

防御的核心原则很简单：CRT参数和d本身一样敏感，任何非必要场景都不应输出。

实际操作建议如下：

• 生产环境日志里禁止对私钥对象直接调用toString、repr、json.dumps这类操作。
• 密钥备份文件要整体加密存储，不能只保护d而忽视p、q、dp这些伴生参数。
• 内存中使用完私钥参数后，如果有条件可以主动清零缓冲区。
• 使用硬件安全模块或专业密钥库时，尽量只暴露解密/签名接口，不暴露底层参数。
• 代码评审时把"私钥参数是否可能通过异常路径泄露"作为必查项。

如果是在CTF出题角度，想加大难度也很简单：把e换成大随机数，让k的枚举空间爆炸；或者只泄露dp的低若干位，逼选手用Coppersmith恢复完整dp。但反过来讲，一切变体的根基都是对dp和p之间这个整除关系的理解。

5.3 扩展阅读：从dp到其他参数泄露

理解了dp泄露的数学本质之后，整条知识线可以延伸出很多相似攻击：

• dq泄露：与dp完全对称，把脚本里的p、q互换即可。
• p或q的高位泄露：可以用Coppersmith方法在部分已知素数位的情况下分解n。
• d的低位泄露：如果d的低位泄露且e比较小，可以结合Boneh-Durfee或部分密钥泄露攻击恢复d。
• 密文、私钥参数一起泄露时的混淆分析：先判断攻击面主次，优先走路径最短的那条。

这些方向都很有意思，但每一类都值得单独写一篇长文。这里我只想强调一点：RSA的安全性建立在私钥的每一比特都被妥善保护之上，而dp泄露恰恰提醒我们，私钥不是只有d一个"要害"。

我个人做CTF题的习惯是，碰到RSA先列参数，再想关系式，最后才开跑。用dp这类题练手最大的收获，不是记住脚本，而是理解私钥参数之间那些看似不起眼的整除关系。它们平时静静躺在PKCS#1标准里，一旦泄露其中一环，整座密码体系就会像抽掉积木一样倒塌。希望这篇从leak题展开的整理，能让你在赛场上少踩几个坑，在工程里多一分敬畏。