从零破解BUUCTF babyRSA：Python密码学工具链深度实战

当你在CTF竞赛中遇到一道RSA题目，手头只有公钥指数e、私钥d和密文c时，该如何逆向还原出明文？本文将带你用Python密码学工具链，一步步拆解BUUCTF平台上的经典题目babyRSA。我们将重点使用 sympy 和 gmpy2 这两个库，通过数学推导和编程实践，完整复现从私钥d恢复RSA参数并解密密文的全过程。

1. 题目分析与数学基础准备

首先我们需要理解题目给出的关键信息。根据附件源码，可以提取以下已知参数：

• 公钥指数 e = 0x10001 (65537)
• 私钥 d = 192757... (一个2048位的大整数)
• 密文 c = 538272... (另一个2048位大整数)

题目特别之处在于素数生成方式：q是p的下一个素数。这意味着p和q非常接近，这在标准的RSA实现中是不安全的，但也正是我们破解的突破口。

RSA的核心数学关系是：

e * d ≡ 1 mod φ(n)

其中φ(n) = (p-1)*(q-1)。这意味着存在某个整数k，使得：

e * d - 1 = k * φ(n)

我们的目标就是找到这个k，进而恢复φ(n)和原始素数p、q。

2. 确定k的合理取值范围

为了高效爆破k值，我们需要先确定它的合理范围。已知：

• e*d-1的位数：约2063-2064位
• φ(n) = (p-1)(q-1)的位数：约2048位（因为p和q都是1024位素数）

因此k的位数应该是2063-2048=15到16位之间。我们可以用以下代码验证：

import gmpy2

d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
e = 0x10001

for i in range(1000, 3000):
    if e*d - 1 > 2**i and e*d - 1 < 2**(i+1):
        print(f"e*d-1 is between 2^{i} and 2^{i+1}")
        break

这段代码会输出e*d-1的二进制位数范围，确认我们的估算。

3. 爆破正确的k值并恢复素数p和q

有了k的范围(2^15到2^16)，我们就可以编写爆破脚本了。关键步骤如下：

1. 遍历可能的k值
2. 对每个k，计算φ(n) = (e*d - 1) // k
3. 由于p和q相邻，我们可以假设φ(n) ≈ (sqrt(n) - 1)^2
4. 使用sympy.prevprime和gmpy2.next_prime找到相邻的素数对

实现代码如下：

import sympy
from Crypto.Util.number import long_to_bytes

for k in range(2**15, 2**16):
    if (e*d - 1) % k == 0:
        phi = (e*d - 1) // k
        # 估算p和q的位置
        approx_p = sympy.prevprime(gmpy2.iroot(phi, 2)[0] + 1)
        q = gmpy2.next_prime(approx_p)
        # 验证φ(n)是否正确
        if (approx_p - 1) * (q - 1) == phi:
            p = approx_p
            break
        elif (q - 1) * (gmpy2.next_prime(q) - 1) == phi:
            p = q
            q = gmpy2.next_prime(p)
            break

n = p * q

这段代码有几个需要注意的细节：

• gmpy2.iroot 用于计算整数平方根，比普通浮点运算更精确
• sympy.prevprime 找到小于给定数的最大素数
• 需要验证找到的素数对确实满足φ(n)的关系

4. 解密获取flag

一旦我们恢复了p和q，计算n=p*q，就可以直接使用RSA解密公式：

m = c^d mod n

Python实现非常简单：

m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

但这里有几个实际编码中容易踩的坑：

1. 大整数运算效率 ：直接使用Python的pow函数处理2048位的大整数可能会很慢。gmpy2库提供了更快的实现：

m = gmpy2.powmod(c, d, n)

2. 字节转换 ：Crypto.Util.number.long_to_bytes可能会因为填充问题导致输出异常，可以尝试以下替代方案：

flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')

3. 编码验证 ：有时解密出的明文需要进一步解码，如UTF-8：

try:
    print(flag.decode('utf-8'))
except UnicodeDecodeError:
    print(flag.hex())

5. 完整攻击脚本与优化技巧

将上述步骤整合，我们得到完整的攻击脚本：

import gmpy2
import sympy
from Crypto.Util.number import long_to_bytes

# 给定参数
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
e = 0x10001

# 爆破k值
found = False
for k in range(2**15, 2**16):
    if (e*d - 1) % k == 0:
        phi = (e*d - 1) // k
        # 尝试两种可能的素数对组合
        approx_p = sympy.prevprime(gmpy2.iroot(phi, 2)[0] + 1)
        q = sympy.nextprime(approx_p)
        if (approx_p - 1) * (q - 1) == phi:
            p = approx_p
            found = True
            break
        next_q = sympy.nextprime(q)
        if (q - 1) * (next_q - 1) == phi:
            p = q
            q = next_q
            found = True
            break

if not found:
    print("Failed to find p and q")
    exit()

n = p * q
m = gmpy2.powmod(c, d, n)
flag = long_to_bytes(m)

print("Recovered primes:")
print(f"p = {p}")
print(f"q = {q}")
print("\nFlag:")
print(flag)

性能优化技巧 ：

1. 并行计算 ：使用multiprocessing库并行化k的爆破过程
2. 早期终止 ：一旦找到有效的k值就立即终止循环
3. 预计算 ：对于固定的e和d，可以预先计算e*d-1
4. 缓存 ：缓存素数检查结果，避免重复计算

6. 密码学安全启示与防御建议

通过这道题目，我们可以学到几个重要的密码学安全经验：

1. 素数生成方式的重要性 ：

   • 永远不要使用相邻的素数作为p和q
   • 使用安全的随机素数生成方法，如OpenSSL的BN_generate_prime_ex

2. 密钥参数验证 ：

   • 实现时应检查p和q的差值足够大
   • 验证gcd(p-1, e) = 1和gcd(q-1, e) = 1

3. 实际应用中的防御措施 ：

攻击类型	防御方法
因式分解攻击	使用足够大的密钥长度（至少2048位）
侧信道攻击	使用恒定时间算法
错误注入攻击	实现参数验证和错误检查

4. CTF中的常见RSA变种 ：
   • 小公钥指数e（如e=3）
   • 共模攻击
   • Wiener攻击（当d较小时）
   • 已知部分私钥信息攻击

7. 扩展练习与进一步学习

为了加深理解，建议尝试以下扩展练习：

1. 修改题目参数 ：尝试不同的e值（如e=3）观察破解难度变化
2. 更大密钥长度 ：将素数长度扩展到2048位，测试脚本的适应性
3. 其他CTF题目 ：尝试解决类似的RSA题目，如：
   • "Very Smooth" (PicoCTF)
   • "Broken RSA" (HackTheBox)
4. 性能对比 ：比较sympy、gmpy2和原生Python在大数运算中的性能差异

推荐的学习资源：

• 《应用密码学手册》中的RSA章节
• Cryptopals挑战中的RSA相关题目
• OpenSSL源码中的RSA实现

在实际CTF比赛中遇到RSA题目时，这套方法可以作为一个标准的工作流程：分析题目给出的特殊条件，利用数学关系推导可能的攻击路径，最后用Python密码学工具链实现攻击。