还得是数论大佬 Ver 1.0 & 爆破RSA闪耀时刻有感

· · 题解

还得是 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 破解方法的选手。
至于实现，我觉得这里的就讲得很好了。大家可以参考一下。