CTF BUUOJ [HDCTF2019]bbbbbbrsa 详细题解

一、题目描述

题目来源：[HDCTF2019] bbbbbbrsa
题目类型：Crypto (RSA)
题目附件：

• enc：包含加密参数的文件
• encode (1).py：加密脚本

二、题目分析

下载附件后，首先查看加密脚本 encode (1).py 和密文文件 enc。

1. 源码审计

打开 encode (1).py，关键代码如下：

from base64 import b64encode as b32encode  # 亮点1：这里有个混淆，名为b32encode，实际是b64encode
from gmpy2 import invert,gcd,iroot
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
import random
flag = "******************************"
nbit = 128
p = getPrime(nbit)
q = getPrime(nbit)
n = p*q
print p
print n
phi = (p-1)*(q-1)
e = random.randint(50000,70000) # 亮点2：e的范围很小，且已知
while True:
	if gcd(e,phi) == 1:
		break;
	else:
		e -= 1;
c = pow(int(b2a_hex(flag),16),e,n)
print b32encode(str(c))[::-1] # 亮点3：先Base64编码，再反转字符串

代码逻辑分析：

1. 变量名混淆：脚本开头 from base64 import b64encode as b32encode，虽然变量名叫 b32encode，但实际调用的是 Base64 编码函数。这是一个典型的“障眼法”。
2. 公钥指数 $e$：$e$ 是在 [50000, 70000] 之间随机生成的。虽然 $e$ 不是固定的，但范围很小，这意味着我们可以通过爆破 $e$ 来还原明文。
3. 密文处理：密文 $c$ 生成后，先转成字符串，然后进行 Base64 编码，最后将字符串反转。

2. 密文文件分析

打开 enc 文件：

p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c = ==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM

我们已知 $p$ 和 $n$，可以直接分解 $n$ 得到 $q$。

三、解题步骤

第一步：还原密文 $c$

根据源码逻辑，密文的还原过程为：反转字符串 -> Base64解码 -> 得到整数c。

• 原始密文：==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM
• 反转后解码，得到的数字为：2373740699529364991763589324200093466206785561836101840381622237225512234632

第二步：计算 RSA 参数

• 已知 $p$。
• 计算 $q=n/p$。
• 计算欧拉函数 $\varphi (n)=(p-1)\times (q-1)$。

第三步：爆破私钥 $d$ 并解密

由于 $e$ 的范围已知为 [50000, 70000]，我们可以遍历这个区间内的每一个整数：

1. 判断该数是否与 $\varphi (n)$ 互质。
2. 如果互质，计算私钥 $d$。
3. 使用 $d$ 解密密文 $c$ 得到明文 $m$。
4. 将 $m$ 转换为 bytes，检查是否包含 flag 关键字或可打印字符。

四、完整解题脚本

import base64
import math
from Crypto.Util.number import long_to_bytes, inverse
# =====================
# 1. 数据准备
# =====================
p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c_b64 = "==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM"
# =====================
# 2. 解析密文 c
# =====================
# 根据源码：print b32encode(str(c))[::-1]
# 逆操作：[::-1] 反转 -> base64解码 -> int
c_rev = c_b64[::-1]
c_bytes = base64.b64decode(c_rev)
c = int(c_bytes.decode())
print(f"[*] 解析得到的密文 c: {c}")
# =====================
# 3. 计算 q 和 phi
# =====================
q = n // p
phi = (p - 1) * (q - 1)
print(f"[*] 计算 q: {q}")
# =====================
# 4. 爆破 e 并解密
# =====================
print("[*] 开始爆破 e...")
flag = b""
# 题目中 e 的范围是 50000 到 70000
for e in range(50000, 70001):
    # 判断是否互质
    if math.gcd(e, phi) == 1:
        try:
            # 计算私钥 d
            d = inverse(e, phi)
            # RSA 解密
            m = pow(c, d, n)
            # 转换为字节流
            msg = long_to_bytes(m)
            
            # 简单的过滤，尝试解码为字符串查找 flag
            # 这里利用 try-except 忽略解码错误，或者检查 flag 关键字
            if b"flag" in msg:
                flag = msg
                print(f"[+] Found e = {e}")
                print(f"[+] Flag found: {flag.decode()}")
                break
        except Exception:
            continue
if not flag:
    print("[-] 未找到 Flag，请检查范围或逻辑。")

五、运行结果

运行脚本后，成功爆破出 $e$ 并解密得到 Flag：

[*] 解析得到的密文 c: 2373740699529364991763589324200093466206785561836101840381622237225512234632
[*] 计算 q: 211330365658290458913359957704294614589
[*] 开始爆破 e...
[+] Found e = 51527
[+] Flag found: flag{rs4_1s_s1mpl3!#}

六、总结

这道题虽然难度不高，但考察了几个 CTF 中常见的知识点：

1. 代码审计能力：识别 import as 这种简单的变量名混淆。
2. 编码逆运算：熟练处理字符串反转和 Base64 解码。
3. RSA 基础：理解 $n=p\times q$ 的分解以及小指数 $e$ 的爆破风险。
   最终的 flag 为：flag{rs4_1s_s1mpl3!#}