RSA

RSA 是非对称加密算法。公钥加密，私钥解密。

五个核心变量

\(p,q\) ：两个非常大的质数 -- 随机生成，为私密信息；
\(n\) ：模数，\(n = p \times q\) ，是公钥的一部分，也是密文计算的基准；
\(\phi(n)\) ：欧拉函数。\(\phi(n) = (p-1)\times(q-1)\) ，是计算私钥的关键中间值；
\(e\) ：公钥指数（通常是 65537，即 0x10001）
\(d\) ：私钥指数，是解密的唯一要是。

加密与解密公式

加密（公钥）：

\[ c = m^e\quad(mod n) \]

（明文 \(m\) 的 \(e\) 次幂对模数取模，得到密文）

解密（私钥）：

\[ m = c^d\quad(mod n) \]

（密文的 \(d\) 次幂对模数取模，还原明文 \(m\) ）

一般 RSA 题目的本质：给出 \(n\) 和 \(e\) ，想办法分解出 \(p\) 和 \(q\) ，从而算出 \(d\) 。

from Crypto.Util.number import long_to_bytes, inverse

# 假设通过某种攻击（如 yafu, factordb）拿到了 p 和 q
p = 123...
q = 456...
e = 65537 # 或者题目给的 e
c = 789... # 题目给的密文

# 1. 计算 n
n = p * q

# 2. 计算欧拉函数 phi
phi = (p - 1) * (q - 1)

# 3. 计算私钥 d (核心步骤)
# d 是 e 模 phi 的乘法逆元
d = inverse(e, phi)
# 或者用 gmpy2.invert(e, phi)，或者 python3.8+ 的 pow(e, -1, phi)

# 4. 解密 (标准公式)
m_int = pow(c, d, n)

# 5. 转成字符串
flag = long_to_bytes(m_int)
print(flag)

先看 \(e\)：
- 如果 \(e=3\) 且 \(n\) 很大：直接开方攻击（你刚才用的脚本）。
- 如果 \(e=65537\) (常态)：进入第 2 步。
看 \(n\)：
- 如果 \(n\) 比较短（比如 256 bit）：用工具（yafu, factordb.com）暴力分解 \(n\) 得到 \(p, q\)。
- 拿到 \(p, q\) 后：使用 标准解密脚本 计算 \(d\) 并解密。