题目背景

原题来自 2025 年洛谷愚人节比赛的 M 题。

---

已经了解 RSA 算法的选手可以略过题目背景。

RSA 算法是一种非对称加密算法。

前期准备工作：

• 生成两个很大的质数 $p$ 和 $q$。
• 计算 $n=pq$。
• 选择一个合适的质数 $e$（不需要太大）。
• 令 $r=(p-1)(q-1)$。
• 计算 $e$ 在模 $r$ 下的逆元，记作 $d$。即：解方程 $ed \equiv 1 (\bmod r)$。
• 公开 $n$ 和 $e$，即公钥。$p$、$q$、$d$ 保密，即私钥。

加密消息：

• 对于明文 $m$，计算 $c=m^e \bmod n$。$c$ 即为密文。

解密消息：

• 对于密文 $c$，计算 $m=c^d \bmod n$。$m$ 即为明文。

作为破解者，可以知道的只有公钥 $n$、$e$ 和密文 $c$。

要想计算出 $m$，就必须知道 $d$。若要通过 $n$ 计算出 $d=(p-1)(q-1)$，相当于要通过分解 $n$ 计算 $p$ 和 $q$。

但是 $p$ 和 $q$ 是很大的质数，对 $n$ 做质因数分解非常困难。这是 RSA 算法安全性的基础。

不过，如果 RSA 运用得不好（比如，$p$ 和 $q$ 选取得太小），那么还是有破解的可能（比如，因为质数太小直接暴力分解 $n$）。

请试着破解下面几组密文。

题目描述

本题为提交答案题。

密文已经下发，请在附件中下载。一共有 $9$ 批密文。请自行尝试解密这些密文。

一批密文内可能含多组 $n$ 和 $c$。若无特殊说明，$e=65537$。

解密出来的 $m$ 请转化为字符串。转化方式为：将 $m$ 标识为 16 进制字符串，按字节转化为 ASCII 编码，得到信息。信息中包含了 flag——你不需要提交整条信息，只需要提交该 flag。

flag 会用花括号包围起来，例如：This is your flag: {wxyz9876}。则 flag 是 wxyz9876。

例如，$m=581758585144958727177341$，转化为十六进制为 $\texttt{7b31323334414243447d}$，按字节转化为 ASCII 编码后得到消息 {1234ABCD}，则你需要提交 1234ABCD 作为答案。

输入格式

一个整数 $n$ 表示密文批次编号，从 $1$ 到 $9$。

输出格式

一行，包含一条字符串，对应批次解密得到的 flag。

提示

Subtask 编号	特殊性质	密文组数	分值
1		1	5
2	$p>10^{298}\times q$
3	$p$，$q$ 差值小于 $10^3$		10
4	$p_1=p_2$	2
5	$e=3$	1
6	$e_1=65537$，$e_2=70001$，$m_1=m_2$	2	15
7	$e_1=e_2=e_3=3$，$m_1=m_2=m_3$	3
8	提供 $a=(p+2)(q+2)$	1
9

如果你使用 Python，那么下面这些可能可以帮助你：

• Python 自带函数 pow(x, a, p)，计算 $x^a \bmod p$。
• $d$ 的计算可以参考如下代码（需要 primefac 包）：

from primefac import modinv
p = ...
q = ...
e = ...
r = (p - 1) * (q - 1)
d = modinv(e, r) % r