CTF实战笔记：当RSA的dp参数泄露时，我是如何用Python脚本5分钟拿到flag的

第一次参加CTF比赛时，遇到一道RSA题目卡了整整三小时。直到队友提醒"检查dp参数泄露"，我才意识到自己错过了关键突破口。这次经历让我深刻理解到： RSA的dp泄露简直是CTF中的"速通密码" 。本文将用最直白的语言，带你复现从懵逼到破解的全过程。

1. 理解dp泄露的本质

dp是RSA私钥d对(p-1)取模的结果，即 dp ≡ d mod (p-1) 。正常情况下它应该和私钥一样保密，但某些题目会故意泄露这个参数。为什么这很危险？因为通过dp我们可以反推出p的值。

数学原理 ：
根据定义 e*d ≡ 1 mod φ(n) 和 dp ≡ d mod (p-1) ，可以推导出：

e*dp ≡ e*d ≡ 1 mod (p-1)
=> e*dp - 1 = k*(p-1)  (k为整数)

这意味着我们只需要遍历k的可能值，就能暴力破解出p。具体操作时，k的取值范围其实非常有限——通常e不会太大（比如常见的65537），这使得爆破成为可能。

注意：实际编码时要处理的是 (e*dp -1) 能被k整除的情况，同时要满足n能被候选p整除。

2. 实战解题步骤拆解

以BUUCTF平台上的[RSA2]题目为例，给定参数：

• n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
• e = 65537
• dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
• c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

2.1 爆破p值的Python实现

关键点在于确定k的遍历范围。由于 k = (e*dp -1)/(p-1) ，而p是n的大素数因子，所以k的取值不会超过e：

import gmpy2

n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
e = 65537
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for k in range(1, e):  # 遍历1到e-1
    if (e * dp - 1) % k == 0:  # 检查是否能整除
        p = (e * dp - 1) // k + 1
        if n % p == 0:  # 验证p是否是n的因子
            q = n // p
            break

2.2 完整解密流程

得到p和q后，就是标准的RSA解密过程了：

phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))

常见坑点 ：

1. 整数除法要用 // 而不是 / ，否则会得到浮点数导致后续计算错误
2. 遍历范围上限设为e即可，不需要更大（节省计算时间）
3. 得到p后一定要验证 n%p==0 ，避免假阳性结果

3. 性能优化技巧

虽然这个解法已经很快，但在更复杂的场景下可能需要优化：

3.1 并行计算加速

对于更大的e值，可以使用多进程加速爆破：

from multiprocessing import Pool

def crack(k):
    if (e * dp - 1) % k == 0:
        p = (e * dp - 1) // k + 1
        if n % p == 0:
            return p
    return None

with Pool(4) as p:  # 使用4个进程
    results = p.map(crack, range(1, e))
    primes = [x for x in results if x]
    if primes:
        p = primes[0]

3.2 数学范围缩小

通过分析可知k必须是 (e*dp-1) 的约数，可以先计算这个数的所有因数：

from math import gcd

temp = e * dp - 1
factors = set()
for i in range(1, int(temp**0.5)+1):
    if temp % i == 0:
        factors.add(i)
        factors.add(temp//i)
        
for k in sorted(factors):
    if k >= e:
        continue
    p = temp // k + 1
    if n % p == 0:
        break

4. 防御措施与题目变种

在实际系统中，dp泄露之所以危险，是因为它让攻击者绕过了大数分解的难题。防护措施包括：

• 永远不要存储或传输dp参数
• 使用标准密钥生成工具 （如OpenSSL）
• 定期更换密钥

CTF中常见的变种题型：

1. 给出dq（d mod q-1）而不是dp
2. 结合其他攻击方式（如共模攻击）
3. 隐藏dp的真实含义（需要先逆向分析）

遇到这类题目时，我的经验是：

1. 先确认所有给定参数的含义
2. 搜索参数组合的已知攻击方式
3. 尝试用小规模数据验证猜想