AI摘要
Rabin 密码体制与 e=2 解密
1. 为什么 e=2 不能直接用 RSA
标准 RSA 的加解密依赖于欧拉定理 $m^{ed} \equiv m \pmod{n}$，其成立的充要条件是 $ed \equiv 1 \pmod{\varphi(n)}$。要解出私钥 $d = e^{-1} \bmod \varphi(n)$，必须满足：
$$ \gcd(e, \varphi(n)) = 1 $$
其中 $\varphi(n) = (p-1)(q-1)$。当 $e=2$ 时：
- $p, q$ 均为奇素数，故 $p-1$ 与 $q-1$ 均为偶数；
- $\varphi(n) = (p-1)(q-1)$ 必为偶数；
- 因此 $\gcd(2, \varphi(n)) \ge 2$。
结论： $e=2$ 在模 $\varphi(n)$ 下不存在乘法逆元 $d$，标准 RSA 的私钥推导不可行。
但 Michael O. Rabin 在 1979 年指出：$e=2$ 的加密本质上是一个二次剩余问题，可以换一种完全不同的思路求解——这就是 Rabin 密码体制。
2. 加密与解密方程
加密
与 RSA 完全相同：
$$ c \equiv m^2 \pmod{n}, \qquad n = pq $$
解密
解密等价于求解二次同余方程：
$$ m^2 \equiv c \pmod{n} $$
由于 $n=pq$ 是两个互素整数的乘积，可以利用中国剩余定理 (CRT) 将一个模合数方程拆为两个模素数方程：
$$ \begin{cases} m^2 \equiv c \pmod{p} \\[4pt] m^2 \equiv c \pmod{q} \end{cases} $$
每个方程都是一元二次同余式 $x^2 \equiv c \pmod{p}$，即求 $c$ 在模 $p$ 下的二次剩余根。
3. 二次剩余与模素数平方根
3.1 定义
设 $p$ 为奇素数，$a \in \mathbb{Z}_p^*$。若存在 $x$ 使得 $x^2 \equiv a \pmod{p}$，则称 $a$ 为模 $p$ 的二次剩余 (quadratic residue)。
勒让德符号 (Legendre symbol) 给出判定：
$$ \left(\frac{a}{p}\right) = a^{(p-1)/2} \bmod p $$
结果：$+1$ 为二次剩余，$-1$ 为非二次剩余，$0$ 为 $p \mid a$。
3.2 $p \equiv 3 \pmod{4}$ 时的开平方公式
Rabin 密码要求素数满足 $p \equiv 3 \pmod{4}$，$q \equiv 3 \pmod{4}$。原因在于此类素数有一个简洁的平方根公式。
当 $p \equiv 3 \pmod{4}$ 时，记 $p = 4k+3$，则 $(p+1)/4 = k+1$ 是整数。对于二次剩余 $c$，其一平方根为：
$$ m_p = c^{(p+1)/4} \bmod p $$
验证：
$$ (m_p)^2 \equiv c^{(p+1)/2} \equiv c^{(p-1)/2+1} \equiv c^{(p-1)/2} \cdot c \equiv \left(\frac{c}{p}\right) \cdot c \equiv c \pmod{p} $$
最后一步利用了 $c$ 是二次剩余 ($\left(\frac{c}{p}\right)=1$)。另一根为 $p - m_p$，二者互为相反数。
为什么不用 $p \equiv 1 \pmod{4}$？ 此时 $(p+1)/4$ 不是整数，开平方需要 Tonelli-Shanks 或 Cipolla 等更复杂的算法。Rabin 刻意限制 $p,q \equiv 3 \pmod{4}$ 就是为了计算简单、效率高。
同理得 $m_q = c^{(q+1)/4} \bmod q$ 及其相反根 $q - m_q$。
4. 为什么有 4 个明文
模 $p$ 下 $c$ 有两个平方根：$\{m_p, \, p-m_p\}$。
模 $q$ 下 $c$ 有两个平方根：$\{m_q, \, q-m_q\}$。
CRT 组合两两配对，共 $2 \times 2 = 4$ 个模 $n$ 下的解：
| 模 p 取 | 模 q 取 | CRT 组合 |
|---|---|---|
| $+m_p$ | $+m_q$ | $r$ |
| $-m_p$ | $-m_q$ | $n - r$ |
| $+m_p$ | $-m_q$ | $s$ |
| $-m_p$ | $+m_q$ | $n - s$ |
这 4 个根恰好呈两对相反数：$\{r, -r\}$ 与 $\{s, -s\}$。解密时得到 4 个候选明文，必须从中甄别真实消息。
5. CRT 组合的数学细节
中国剩余定理的常见形式：
设 $n = p q$，$\gcd(p, q)=1$。给定方程组：
$$ \begin{cases} x \equiv a \pmod{p} \\ x \equiv b \pmod{q} \end{cases} $$
解为：
$$ x \equiv a \cdot q \cdot y_q + b \cdot p \cdot y_p \pmod{n} $$
其中 $y_p = p^{-1} \bmod q$，$y_q = q^{-1} \bmod p$，满足：
$$ y_p \cdot p \equiv 1 \pmod{q}, \qquad y_q \cdot q \equiv 1 \pmod{p} $$
代码中的四根推导（$r, rr, s, ss$）如下。
5.1 取 $a = m_p$、$b = m_q$ → 根 $r$
$$ r \equiv m_p \cdot q \cdot y_q + m_q \cdot p \cdot y_p \pmod{n} $$
验证：$r \bmod p = m_p \cdot q \cdot y_q \bmod p$。由于 $y_q \cdot q \equiv 1 \pmod{p}$，故 $r \equiv m_p \pmod{p}$。同理 $r \equiv m_q \pmod{q}$。成立。
$r$ 的相反根为 $rr = n - r$，这对应 4 组合表中取 $-m_p, -m_q$ 的情况。
5.2 取 $a = m_p$、$b = -m_q$ → 根 $s$
将 $b \gets -m_q \equiv q - m_q \pmod{q}$ 代入 CRT：
$$ s \equiv m_p \cdot q \cdot y_q - m_q \cdot p \cdot y_p \pmod{n} $$
$s$ 的相反根为 $ss = n - s$，对应取 $-m_p, +m_q$ 的情况。
5.3 代码中的计算技巧
代码将四项写为：
r = (yp * p * mq + yq * q * mp) % n
rr = n - r
s = (yp * p * mq - yq * q * mp) % n
ss = n - s其中 yp * p * mq 即 $m_q \cdot p \cdot y_p$（注意变量命名：yp = p^{-1} mod q，乘以 p 后得 $p \cdot p^{-1} \bmod q \equiv 1 \pmod{q}$ 的系数项），yq * q * mp 同理。
实际上 $r$ 的表达式就是标准 CRT 合并。两式相加得同符号组合，两式相减得异符号组合。
6. 消息冗余与唯一解甄别
因为 4 个候选明文中只有一个有意义，解密者需要额外信息。常用手段：
- 明文填充 (padding)：在消息头部填入固定比特/字节模式，解密后检验。
- 消息重复：将消息复制两份加密，解密后比对。
- 上下文筛选：通常 flag 有固定格式（如
flag{...}），遍历 4 个根取有意义者即可（代码正是如此）。
7. 安全性分析
Rabin 密码的安全性等价于大整数分解。可以证明：
如果敌手能够对任意密文 $c$ 给出平方根，则他可以高效分解 $n$。
证明思路： 随机选 $x$，计算 $c \equiv x^2 \pmod{n}$，交给解密预言机得到 $y$（$y \ne \pm x$ 的概率为 $1/2$）。由 $x^2 \equiv y^2 \pmod{n}$ 得：
$$ (x-y)(x+y) \equiv 0 \pmod{n} $$
计算 $\gcd(x\pm y, n)$ 即可得到 $p$ 或 $q$。因此破译 Rabin ≡ 分解 $n$。
8. 完整解密流程总结
- 验证素数条件：$p \equiv q \equiv 3 \pmod{4}$（否则 $(p+1)/4$ 不是整数，算法不适用）。
- 开平方：$m_p = c^{(p+1)/4} \bmod p$，$m_q = c^{(q+1)/4} \bmod q$。
- 计算 CRT 系数：$y_p = p^{-1} \bmod q$，$y_q = q^{-1} \bmod p$。
- 组合四根：使用 $r, n{-}r, s, n{-}s$ 公式。
- 筛选真实明文：通过填充规则或格式过滤。
9. 代码解读
关键点：
(p+1)//4整除非偶然——这依赖于 $p \equiv 3 \pmod{4}$ 的前提。gmpy2.invert用于计算模逆，$y_p$ 与 $y_q$ 互相对偶。- 遍历 4 根用
bytes.fromhex尝试解码，非 ASCII 的根自然地通过异常被忽略。
10. 总结
Rabin 密码是 RSA 的"极端版本"：取 $e=2$ 使得加密速度极快（仅一次模乘），但代价是解密输出不唯一，需要额外信息去歧义。其数学核心从 RSA 的模逆运算转向二次剩余与 CRT 的组合——思路的转换比具体的公式计算更为重要。
下次 CTF 遇到 $e=2$ 的题目时，不妨直接套用 Rabin 四根解密公式，别忘了检查 $p, q \equiv 3 \pmod{4}$ 的前提。
参考文献
- Rabin, M. O. (1979). Digitalized Signatures and Public-Key Functions as Intractable as Factorization. MIT/LCS/TR-212.
- Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography, Chapter 8. CRC Press.
- Silverman, J. H. (2008). A Friendly Introduction to Number Theory, 4th ed. Pearson.
- Stinson, D. R., & Paterson, M. B. (2018). Cryptography: Theory and Practice, 4th ed. CRC Press.
