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

weixin_30319153

397人浏览 · 2026-06-05 15:07:37

weixin_30319153 · 2026-06-05 15:07:37 发布

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

当你面对三组看似毫无规律的五进制数字时，是否感到无从下手？这正是BUUCTF RSA4题目设计的精妙之处。本文将带你从零开始，一步步拆解这个融合了 五进制陷阱 、 中国剩余定理 和 小指数爆破 的典型RSA题目。不同于教科书式的理论讲解，我们将聚焦于 可复现的实战操作 ，用Python代码实现每一个关键步骤。

1. 题目分析与五进制处理

拿到题目时，首先需要关注三个关键信息： 模数n 、 密文c 和它们的 编码格式 。题目给出的n和c都是五进制字符串，这是第一个容易被忽略的坑点。

n1 = "331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004"
c1 = "310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243"

五进制转换要点 ：

Python的 int() 函数支持指定进制转换，但需要确保字符串完全由0-4组成
转换后的整数可能非常大，需要借助 gmpy2 库进行高精度计算
验证转换是否正确： len(n1) == 617 （五进制位数）对应十进制约 617*log10(5)≈431 位数字

实际操作代码：

from gmpy2 import mpz

def pent_to_int(pent_str):
    return mpz(int(pent_str, 5))

n_list = [pent_to_int(n) for n in [n1, n2, n3]] 
c_list = [pent_to_int(c) for c in [c1, c2, c3]]

2. 中国剩余定理(CRT)的Python实现

当遇到 多组n和c但共用相同e和m 的情况时，中国剩余定理(CRT)就是解题的关键。其数学本质可以概括为：

给定同余方程组： x ≡ a₁ mod m₁
x ≡ a₂ mod m₂
...
x ≡ aₖ mod mₖ
当m₁,m₂,...,mₖ两两互质时，存在唯一解x mod M（M=∏mᵢ）

CRT实现步骤 ：

计算所有模数的乘积： M = m₁ * m₂ * ... * mₖ
对每个mᵢ计算： Mᵢ = M / mᵢ
求Mᵢ在模mᵢ下的逆元： Mᵢ⁻¹ = invert(Mᵢ, mᵢ)
解为： x = (a₁M₁M₁⁻¹ + a₂M₂M₂⁻¹ + ... + aₖMₖMₖ⁻¹) mod M

Python实现代码：

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

m_e = crt(c_list, n_list)  # 得到m^e mod (n1*n2*n3)

关键验证点 ：

检查所有n是否两两互质： gcd(n1,n2)==1
验证CRT结果是否满足原方程： pow(m_e,1,n1) == c1

3. 小指数e的暴力破解

在CTF的RSA题目中，加密指数e通常较小（常见2、3、5等）。我们可以通过以下步骤爆破e：

对 m_e 进行e次方根运算
检查结果是否为整数
尝试将结果转换为可读字符串

优化技巧 ：

限制e的范围（通常3-20）
使用 gmpy2.iroot() 进行高效的大整数开方
处理十六进制字符串的奇数字节问题

爆破代码实现：

for e in range(1, 10):
    m, is_exact = gmpy2.iroot(m_e, e)
    if not is_exact:
        continue
    
    hex_str = hex(int(m))[2:]
    # 处理奇数字节长度
    if len(hex_str) % 2 != 0:
        hex_str = '0' + hex_str
    
    try:
        flag = binascii.unhexlify(hex_str).decode()
        print(f"Found with e={e}: {flag}")
        break
    except:
        continue

典型输出 ：

加密指数e = 3：
b'noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}'

4. 完整解题脚本与异常处理

将上述步骤整合成完整脚本时，需要考虑以下 边界情况 ：

五进制字符串包含非法字符
模数不满足两两互质条件
开方结果无法解码为有效字符串
大整数运算的内存和性能问题

增强版脚本 ：

#!/usr/bin/env python3
import gmpy2
import binascii
from functools import reduce

def validate_pent(pent_str):
    if not all(c in '01234' for c in pent_str):
        raise ValueError("Invalid pentadecimal character")

def pent_to_int(pent_str):
    validate_pent(pent_str)
    return int(pent_str, 5)

def check_coprimality(numbers):
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            if gmpy2.gcd(numbers[i], numbers[j]) != 1:
                raise ValueError(f"n_{i} and n_{j} are not coprimes")

def crt(a_list, m_list):
    M = reduce(lambda x,y: x*y, m_list)
    total = 0
    for a, m in zip(a_list, m_list):
        Mi = M // m
        try:
            Mi_inv = gmpy2.invert(Mi, m)
        except ZeroDivisionError:
            raise ValueError("Modular inverse doesn't exist")
        total += a * Mi * Mi_inv
    return total % M

def main():
    # 题目数据
    n1 = "331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004"
    c1 = "310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243"
    
    # 省略n2,c2,n3,c3...
    
    try:
        n_list = [pent_to_int(n) for n in [n1, n2, n3]]
        c_list = [pent_to_int(c) for c in [c1, c2, c3]]
        
        check_coprimality(n_list)
        
        m_e = crt(c_list, n_list)
        
        for e in range(1, 20):
            m, is_exact = gmpy2.iroot(m_e, e)
            if not is_exact:
                continue
                
            hex_str = format(int(m), 'x')
            if len(hex_str) % 2 != 0:
                hex_str = '0' + hex_str
                
            try:
                flag = binascii.unhexlify(hex_str).decode(errors='ignore')
                if all(32 <= ord(c) <= 126 for c in flag):  # 可打印字符检查
                    print(f"[+] Success with e={e}")
                    print(f"Flag: {flag}")
                    return
            except:
                continue
                
        print("[-] Failed to find flag with e < 20")
    except Exception as e:
        print(f"Error: {str(e)}")

if __name__ == "__main__":
    main()

性能优化技巧 ：