CTF实战：从BUUCTF的RSA题解析k值爆破与脚本优化

在CTF竞赛中，RSA加密题目一直是密码学方向的热门考点。今天我们就以BUUCTF平台上的NCTF2019 babyRSA题目为例，深入探讨如何通过Python脚本爆破k值来破解RSA加密。这道题的特别之处在于它给出了e、d、c但隐藏了n，需要我们通过数学推导和编程技巧来还原加密过程。

1. 题目分析与数学基础

首先，我们需要理解题目给出的关键信息：

• 已知：公钥指数e=0x10001(65537)，私钥d，密文c
• 未知：模数n及其因子p、q

根据RSA加密原理，我们知道：

ed ≡ 1 mod φ(n)

这意味着存在某个整数k，使得：

ed - 1 = kφ(n) = k(p-1)(q-1)

题目中特别给出了p和q的关系：q是大于p的下一个素数。这个信息对我们后续的爆破至关重要。

1.1 确定k的范围

要爆破k值，首先需要确定k的可能范围。我们可以通过位数分析来估算：

• ed-1的位数：通过计算发现是2063-2064位
• φ(n)=(p-1)(q-1)的位数：p和q都是1024位素数，所以φ(n)约2048位

因此，k的位数大约是2063-2048=15-16位，即k的可能范围在2^15到2^16之间。

注意：这里的位数分析是关键，错误的范围估计会导致爆破效率低下甚至失败。

2. 爆破k值的Python实现

现在我们来编写实际的爆破脚本。我们将使用gmpy2进行大数运算，sympy处理素数相关操作。

2.1 基础爆破框架

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

# 题目给定的已知值
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
e = 0x10001

# 计算ed-1的值
ed_1 = e * d - 1

# k的可能范围
k_start = 2**15
k_end = 2**16

for k in range(k_start, k_end):
    if ed_1 % k == 0:
        phi_n = ed_1 // k
        # 后续处理...

2.2 利用p和q的关系优化搜索

题目提示q是p的下一个素数，我们可以利用这个关系进一步优化搜索：

for k in range(k_start, k_end):
    if ed_1 % k == 0:
        phi_n = ed_1 // k
        # 估算p的值：因为n≈p²，所以φ(n)≈(p-1)²
        p_approx = gmpy2.iroot(phi_n, 2)[0] + 1
        p = sympy.prevprime(p_approx)
        q = sympy.nextprime(p)
        
        # 验证(p-1)(q-1)是否等于phi_n
        if (p-1)*(q-1) == phi_n:
            n = p * q
            m = pow(c, d, n)
            print("Found flag:", long_to_bytes(m))
            break

这个优化利用了p和q相邻的特性，大大减少了需要尝试的可能性。

3. 脚本优化技巧

在实际CTF比赛中，脚本的效率往往决定了解题速度。以下是几个优化技巧：

3.1 并行计算加速

我们可以使用Python的multiprocessing模块来并行化k值的搜索：

from multiprocessing import Pool

def check_k(k):
    if ed_1 % k == 0:
        phi_n = ed_1 // k
        p_approx = gmpy2.iroot(phi_n, 2)[0] + 1
        p = sympy.prevprime(p_approx)
        q = sympy.nextprime(p)
        if (p-1)*(q-1) == phi_n:
            return p, q
    return None

with Pool() as p:
    results = p.map(check_k, range(k_start, k_end))
    for result in results:
        if result:
            p, q = result
            n = p * q
            m = pow(c, d, n)
            print("Found flag:", long_to_bytes(m))
            break

3.2 提前终止条件

在找到正确解后立即终止所有进程：

from multiprocessing import Pool, Manager

def check_k(k, return_dict):
    if ed_1 % k == 0:
        phi_n = ed_1 // k
        p_approx = gmpy2.iroot(phi_n, 2)[0] + 1
        p = sympy.prevprime(p_approx)
        q = sympy.nextprime(p)
        if (p-1)*(q-1) == phi_n:
            return_dict['result'] = (p, q)
            return True
    return False

if __name__ == '__main__':
    with Manager() as manager:
        return_dict = manager.dict()
        with Pool() as p:
            p.starmap(check_k, [(k, return_dict) for k in range(k_start, k_end)])
            if 'result' in return_dict:
                p, q = return_dict['result']
                n = p * q
                m = pow(c, d, n)
                print("Found flag:", long_to_bytes(m))

4. 数学原理深入

理解背后的数学原理对于解决类似的RSA题目至关重要。让我们更深入地分析为什么这种方法有效。

4.1 RSA密钥生成关系

在RSA中，我们通常选择两个大素数p和q，计算：

• n = p × q
• φ(n) = (p-1)(q-1)
• 选择e使得gcd(e, φ(n)) = 1
• 计算d ≡ e⁻¹ mod φ(n)

题目给出了d和e，隐藏了n。我们的目标是恢复n。

4.2 从ed-1恢复φ(n)

由ed ≡ 1 mod φ(n)，我们知道ed-1是φ(n)的倍数。设：

ed - 1 = kφ(n)

因为φ(n) ≈ n ≈ p²（因为q≈p），所以：

k ≈ (ed-1)/p²

通过估算p的大小，我们可以反推出k的范围。

4.3 相邻素数的性质

题目中q = next_prime(p)，这意味着：

• p和q非常接近
• |p - q|的值相对较小
• φ(n) = (p-1)(q-1) ≈ p²

这种关系让我们能够通过平方根近似来估算p的值。

5. 实际解题中的注意事项

在真实的CTF比赛中，除了编写脚本，还需要注意以下几点：

1. 环境准备 ：确保安装了必要的Python库（gmpy2、sympy、pycryptodome）
2. 大数处理 ：Python原生对大数的支持很好，但使用gmpy2可以显著提高性能
3. 错误处理 ：爆破脚本可能需要运行一段时间，添加适当的进度显示
4. 多方法验证 ：得到flag后，可以尝试用不同的方法验证结果正确性

以下是一个完整的、带有进度显示的脚本示例：

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

# 题目给定的已知值
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
e = 0x10001

ed_1 = e * d - 1
k_start = 2**15
k_end = 2**16

total = k_end - k_start
for i, k in enumerate(range(k_start, k_end)):
    if i % 100 == 0:
        progress = i / total * 100
        sys.stdout.write(f"\rProgress: {progress:.2f}%")
        sys.stdout.flush()
    
    if ed_1 % k == 0:
        phi_n = ed_1 // k
        p_approx = gmpy2.iroot(phi_n, 2)[0] + 1
        p = sympy.prevprime(p_approx)
        q = sympy.nextprime(p)
        
        if (p-1)*(q-1) == phi_n:
            n = p * q
            m = pow(c, d, n)
            print("\nFound flag:", long_to_bytes(m))
            break

在实际比赛中，这类题目通常需要结合数学洞察力和编程技巧。理解RSA的数学原理是基础，而高效的脚本编写能力则能帮助你在有限的时间内找到flag。