自动搬运

查看原文

来自洛谷，原作者为

	SatoruXia 欢迎加入 INFOI！111309！||只有不知好歹的家伙才敢叫我大佬||世界的真理由我解明||支持互关，小号必关||基尼奇&那刻夏&莱欧斯利&艾尔海森厨||音游玩家，初二OIer，初次见面，祝我们合作愉快。

搬运于2025-08-24 23:16:45，当前版本为作者最后更新于2025-07-28 22:15:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

还得是 CTF 大佬。
这题好像没什么人 A，难度确实配得上紫题。概括题意：你将获得 $9$ 组 RSA 的公钥和密文，请根据每组数据的特别之处选用合适的方法去破解它们。
观察下载的数据后会发现有些数据大得令人发指。所以除非利用几千行的高精来手写所有基本运算（甚至包括高精度开根），否则请使用 Python。况且，在运行效率上也是 Python 快。
然后我们理解了 RSA 的加密法则后即可开始破译。
:::success[一种投机取巧的方法]{open} 出题人大概觉得，它的数据可以克掉普通的质因数分解器与数据库。那是确实，因为数据普遍有 $600$ 位左右。
但 factordb 或者 yafu 比出题人的数据还强大。本题所有数据均可使用它们分解出准确数。因此我们可以用一份程序通过所有数据，只需手动把分解结果粘贴进代码即可。
当然，还是学习特定技巧为重。 :::

Case $1$

数据很小，暴力分解即可。使用大数分解器等方法这里就不提了。
至于解码部分，当然是写程序解码更快。提供一份示例程序：（注意要安装并引用 Crypto 库）

def extract_flag(m):
    try:
        flag = long_to_bytes(m).decode('utf-8')
        if '{' in flag and '}' in flag:
            return flag[flag.find('{')+1 : flag.find('}')]
        return flag
    except UnicodeDecodeError:
        hex_str = hex(m)[2:]
        # 处理非 ASCII 字节（如填充、Base64）
        if len(hex_str) % 2 != 0:
            hex_str = '0' + hex_str  # 对齐字节
        bytes_data = bytes.fromhex(hex_str)
        return f"Hex: {hex_str}, Bytes: {bytes_data}"

解码结果说 Very Simple RSA。这是签到。

Case $2$

数据已上升至 $300$ 多位，不过特殊性质说 $p$ 和 $q$ 的差距非常大。
显然地，用 Pollard-Rho 或者维纳攻击（Wiener's Attack） 就可以快速分解出答案。Pollard-Rho 可以参考我这篇文章的实现和优化方式；维纳攻击是一种专门爆破 RSA 的方法，依靠连分数展开破解，能处理的数据范围比 Pollard-Rho 大得多，代码也不是很难实现。这题用 Pollard-Rho 就可以满足需求了。
分解得 $q$ 只有十几位。所以暴力应该也可以很快解出。
解码结果说 Pollard-Rho is OK。看来 Pollard-Rho 确实是正解。

Case $3$

第一眼：$n$ 的数值已经达到 $600$ 位左右。显然要找数学方法破解。特殊性质：$p$ 与 $q$ 差值非常小。
考虑费马分解（Fermat's Factorization）。费马分解用于处理 $p$ 和 $q$ 挨得很近的情况，基于平方差公式实现，尝试将 $n$ 表示为两个平方数的差然后分解。针对于这道题，我们不必确定上界，从 $\sqrt{n}$ 开始枚举一个数，计算另一个数直至成功为止即可。
然后你会发现你爆破失败了。为什么？因为大数开根会有精度误差，需安装并使用 gmpy2 库这个高精度大数处理库。里面的 isqrt() 函数可以精确分解。
结果：Fermat is Awesome。

Case $4$

本题有两组数据。然后我们发现特殊性质说 $p_1 = p_2$，两个数据共用一个 $p$？那么自然而然就可以想到最大公约数。
最大公约数攻击，通过计算共同的 $p$ 来分解数字。这个可以直接使用 math 里的 gcd() 函数。
可能有人会问：两组数据应当有两个密文但是只有一个答案？解密得一个说 GCD Solves This Quiz，一个说 USELESSSSSSSSSSSSSSSSSSSSSSSSSSShahahah。嗯。

Case $5$

数据又变小了？特殊性质说 $e$ 也变小了。那么有没有可能 $m^e \le n$？尝试一下开立方根就成功了。
这就是低加密指数攻击，又称小指数明文爆破攻击（Low-Exponent Attack）。那么考虑一下：如果 $m^e > n$ 怎么办？爆破出一个能让 $kn+c$ 能开 $e$ 次方根的常数 $e$ 即可。
注意开方千万不要直接 c**(1/3)。
结果：$e$ is Not Useless。

Case $6$

两组数据，$n,c,e$ 均不相同，怎么办……等下！$n$ 是相同的！
毒瘤的出题人并没有写出这一点。要靠大力肉眼观察。
既然模数相同那就使用共模攻击（Common Modulus Attack）。因为 $e_1$ 和 $e_2$ 互质，所以我们计算两个数 $s_1,s_2$，使得 $s_1 e_1+s_2 e_2 = 1$ 即可。
因为明文 $m$ 相同所以只有一个解。Do Not Say It Two Times。嗯。

Case $7$

数据很吓人，因为有三组。虽然 $e$ 也很小但无法用 Case $5$ 解出。
然后我们发现它们共用 $e$ 和 $m$。有点数论基础的人就能想到中国剩余定理（CRT）。这便是三组数据的意义所在。
没错，这便是广播攻击（Håstad's Broadcast Attack）。它基于 CRT 实现解同余方程组来破解 RSA。套一个板子进去就好了。
注意：这里的取最大公约数不能用 math 的。会爆。不过 gmpy2 里刚好有一个。
Three Times is Also Weak。确实。

Case $8$

多了一个 $(p+2)(q+2)$ 的值？那 $p+q$ 岂不是可以知道了？然后解一元二次方程不就好了？是的。
这个只需八年级水平和注意力。所以：Attention is All You Need。

Case $9$

最后一个是尾杀吗？不是。$m$ 已经泄露了。直接破解就好了。
感谢您的游玩。Thanks For Your Playing。

总结：这题挺有难度的，OI选手我想都做不出来吧。赛场上能切的一定是 CTF 大佬或者去网上搜过 RSA 破解方法的选手。
至于实现，我觉得这里的就讲得很好了。大家可以参考一下。