场景概述

题目给出三个文件：

目标是解析公钥、计算私钥，并用私钥将 flag.enc 解密出明文 flag。

基础知识

RSA 数学回顾

$$ \begin{aligned} n &= p \times q \\ \varphi(n) &= (p-1)(q-1) \\ d &\equiv e^{-1} \pmod{\varphi(n)} \end{aligned} $$

• 加密：$c = m^e \bmod n$
• 解密：$m = c^d \bmod n$

.enc 文件的本质

flag.enc 不是某种标准容器格式——它仅仅是密文 $c$ 的原始大端序字节表示。

这意味着：

• 直接用 open("flag.enc", "rb").read() 读到的字节串，按大端序解析为一个整数，就是 $c$。
• 解密后得到明文字节串，同样是 $m$ 的大端序表示。

PKCS#1 v1.5 填充

实际 RSA 加密几乎不会直接对原始消息 $m$ 做模幂，而是使用 PKCS#1 v1.5 或 OAEP 填充。pycryptodome 的 Crypto.Cipher.PKCS1_v1_5 和 rsa 库的 rsa.decrypt 默认均采用 PKCS#1 v1.5 填充。

PKCS#1 v1.5 的密文格式为：

00 02 [non-zero random padding bytes] 00 [message]

解密后需按此格式去填充，才能得到原始明文。

若使用裸 pow(c, d, n) 解密，则得到的字节串包含填充，需要手动去除。而 rsa.decrypt() 或 PKCS1_v1_5.new(key).decrypt() 会自动完成去填充。

方案一：借助已知 p, q 构造私钥

适用场景：题目直接给出了 p 和 q（如原始 pqe-enc.py 所示）。

为什么需要去填充

上述代码打印出的 plain 不是理想的 flag 明文，而是一段以 \x00\x02 开头的 PKCS#1 填充数据。原因是 pow(c, d, n) 只是数学上的模幂运算，不处理填充协议。

去填充需要识别 00 02 头，跳过随机 pad，直到遇到 00 分隔符为止。更推荐的方法是让库自动处理。

使用 rsa 库的 PrivateKey 构造

方案二：从 PEM 文件解析公钥

适用场景：题目只给了 public.pem 和 flag.enc，没有直接给出 p, q, e, n。

PEM 文件格式

PEM（Privacy-Enhanced Mail）是一种 Base64 编码的证书/密钥容器格式，常见头部有：

公钥 PEM 文件内容为 DER 编码后 Base64，其结构（X.509 SPKI）如下：

SEQUENCE {
  SEQUENCE {
    OBJECT IDENTIFIER rsaEncryption (1.2.840.113549.1.1.1)
    NULL
  }
  BIT STRING {
    SEQUENCE {
      INTEGER n
      INTEGER e
    }
  }
}

使用 pycryptodome 导入 PEM

from Crypto.PublicKey import RSA

with open("public.pem", "rb") as f:
    pubkey = RSA.import_key(f.read())

n = pubkey.n   # 提取模数
e = pubkey.e   # 提取公钥指数
print(f"n = {n}")
print(f"e = {e}")

解析后获得 $n$ 和 $e$。接下来要对 $n$ 进行因数分解以获得 $p, q$。

方案三：对 n 进行因数分解

使用 yafu

yafu-x64.exe "factor(86934482296048119190666062003494800588905656017203025617216654058378322103517)"

使用 factordb

访问 factordb.com，输入 $n$ 查询已知分解。

使用 SageMath

# sage
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
factor(n)

若 $n$ 较小（$< 2^{256}$）也可用 sympy 的 factorint 或直接 yafu。一旦获得 $p$ 和 $q$，后续步骤与方案一相同。

统一解密脚本

将以上整合为一个脚本 decrypt.py：

若不用 PKCS1_v1_5，直接用 rsa 库

两种手动解密方式对比

常见问题

Q1: 解密后得到乱码或报错 ValueError: Decryption failed

• 检查是否使用了正确的填充方式（PKCS#1 v1.5 vs OAEP）。
• 确认 sentinel 参数在 PKCS1_v1_5.decrypt() 中是必需的。
• pow(c, d, n) 得到的结果包含填充字节，直接 decode() 会乱码。

Q2: not enough data 或 Message too large

• .enc 文件的字节长度应等于 $n$ 的字节长度（即 $n.\text{bit\_length}() / 8$ 取上整）。若长度不对，说明密文可能被截断或使用了其他编码方式。
• 确保 open 时使用 "rb" 二进制模式。

Q3: PEM 文件报 ValueError: RSA key format is not supported

• 确认 PEM 文件头是 -----BEGIN PUBLIC KEY----- 还是 -----BEGIN RSA PUBLIC KEY-----，两者均可被 Crypto.PublicKey.RSA.import_key() 识别。
• 若为 SSH2 格式（ssh-rsa AAA...），需先转换为 PEM：ssh-keygen -f key.pub -e -m PKCS8 > pub.pem。

Q4: 如何判断题目用的是 PKCS#1 v1.5 还是 OAEP

• 大多数 CTF 简单 RSA 题目默认使用 PKCS#1 v1.5。若 rsa.decrypt() 或 PKCS1_v1_5 失败，可尝试 OAEP：

from Crypto.Cipher import PKCS1_OAEP
cipher = PKCS1_OAEP.new(key)
plain = cipher.decrypt(ciphertext)

工具链与依赖

总结

RSA .enc 文件解密的通用流程：

1. 从 PEM 提取 $n, e$（Crypto.PublicKey.RSA.import_key）
2. 对 $n$ 进行因数分解得到 $p, q$（yafu / factordb / 给定值）
3. 计算 $\varphi(n)$ 和私钥指数 $d = e^{-1} \bmod \varphi(n)$
4. 构造私钥对象并解密密文
5. 对密文执行 PKCS#1 v1.5（或 OAEP）解密，得到明文