CTF实战：手把手教你用Python的gmpy2库破解BUUCTF RSA4（含五进制转换与e值爆破）

在CTF竞赛中，RSA加密题目一直是密码学方向的热门考点。今天我们将通过一道典型题目，详细讲解如何利用Python的gmpy2库实现RSA攻击。这道题目来自BUUCTF的RSA4，特点是给出了多组五进制的模数n和密文c，但隐藏了加密指数e。我们将从数据预处理开始，逐步演示完整的解题流程。

1. 题目分析与数据预处理

拿到题目后，首先需要仔细观察给出的数据格式。题目提供了三组n和c值，但特别需要注意的是这些数值都是以五进制表示的。这是CTF题目中常见的陷阱，很多选手会忽略这一点直接当作十进制处理，导致后续计算全部出错。

五进制转换示例：

n1 = "331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004"
c1 = "310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243"

处理五进制数据的关键步骤：

1. 使用Python的 int() 函数进行进制转换
2. 验证转换结果是否正确
3. 将转换后的数值存入列表备用

实际操作代码：

n_list = [int(n1,5), int(n2,5), int(n3,5)]
c_list = [int(c1,5), int(c2,5), int(c3,5)]

2. 中国剩余定理(CRT)原理与应用

中国剩余定理是解决本题的核心数学工具。当给出多组同余方程时，CRT可以帮助我们找到满足所有方程的解。在RSA攻击场景中，这相当于恢复出了m^e的值。

CRT数学表达： 给定同余方程组：

x ≡ a1 mod m1
x ≡ a2 mod m2
...
x ≡ an mod mn

当模数m1,m2,...,mn两两互质时，存在唯一解x mod M，其中M=m1 m2 ...*mn。

实现CRT的关键步骤：

1. 计算所有模数的乘积M
2. 对每个模数计算Mi = M/mi
3. 求Mi在模mi下的逆元Mi_inv
4. 构造解x = Σ(ai Mi Mi_inv) mod M

3. 使用gmpy2实现CRT求解

Python的gmpy2库提供了大整数运算和模逆计算的高效实现。下面我们编写CRT求解函数：

import gmpy2

def CRT(a_list, m_list):
    M = 1
    for m in m_list:
        M *= m  # 计算模数的乘积
    
    x = 0
    for a, m in zip(a_list, m_list):
        Mi = M // m
        Mi_inv = gmpy2.invert(Mi, m)  # 计算逆元
        x += a * Mi * Mi_inv
    
    return x % M

常见问题处理：

• 库安装问题 ：如果提示gmpy2未安装，使用 pip install gmpy2 安装
• 数据类型问题 ：确保传入的参数都是整数类型
• 模不互质情况 ：如果模数不互质，CRT将无法直接应用

4. 加密指数e的爆破技巧

题目没有给出加密指数e，这是CTF中常见的设置。通常e会取较小的值（如3、5、7等），我们可以通过遍历可能的e值来尝试解密。

e值爆破的实现步骤：

1. 使用CRT求出m^e的值
2. 遍历可能的e值（一般从3开始）
3. 对m^e开e次方，检查是否为整数
4. 如果找到整数解，则成功破解

关键代码实现：

m_e = CRT(c_list, n_list)  # 使用CRT求出m^e

for e in range(3, 10):  # 尝试常见的e值
    m, is_perfect_root = gmpy2.iroot(m_e, e)
    if is_perfect_root:
        print(f"Found e = {e}")
        break

5. 完整解题代码与结果解析

将上述步骤整合，我们得到完整的解题代码：

import gmpy2
import binascii

def CRT(a_list, m_list):
    M = 1
    for m in m_list:
        M *= m
    
    x = 0
    for a, m in zip(a_list, m_list):
        Mi = M // m
        Mi_inv = gmpy2.invert(Mi, m)
        x += a * Mi * Mi_inv
    
    return x % M

# 五进制数据转换
n1 = "331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004"
c1 = "310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243"

n2 = "302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114"
c2 = "112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344"

n3 = "332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323"
c3 = "10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242"

# 转换为十进制
n_list = [int(n1,5), int(n2,5), int(n3,5)]
c_list = [int(c1,5), int(c2,5), int(c3,5)]

# 使用CRT求解
m_e = CRT(c_list, n_list)

# 爆破e值
for e in range(1, 10):
    m, is_perfect_root = gmpy2.iroot(m_e, e)
    if is_perfect_root:
        print(f"Found e = {e}")
        m_hex = hex(m)[2:]
        # 处理十六进制字符串长度为偶数
        if len(m_hex) % 2 != 0:
            m_hex = '0' + m_hex
        flag = binascii.unhexlify(m_hex)
        print("Flag:", flag.decode())
        break

运行结果分析：

Found e = 3
Flag: noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}

6. 实战经验与技巧分享

在实际CTF比赛中，处理这类RSA题目时，有几个关键点需要注意：

1. 数据格式检查 ：始终确认题目给出的数据格式，特别是进制表示
2. 常见e值范围 ：爆破e值时，优先尝试3、5、7、65537等常见值
3. 性能优化 ：对于大整数运算，使用gmpy2等专用库可以显著提高计算速度
4. 错误处理 ：添加适当的异常处理，特别是对于模逆计算可能失败的情况

进阶技巧：

• 当e值较大时，可以考虑使用Coppersmith方法
• 如果模数n有共同因数，可以直接分解n
• 对于padding不规范的情况，可以尝试相关攻击方法