T574918 【CTF】RuShiA
题目背景
> 已经了解 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` 作为答案。
输入格式
无
输出格式
无
说明/提示
| Subtask 编号 | 特殊性质 | 密文组数 | 分值 |
| :-----------: | :-----------: | :-----------: | :-----------: |
| 1 | | 1 | 5 |
| 2 | $p>10^{298}\times q$ | 1 | 5 |
| 3 | $p$,$q$ 差值小于 $10^3$ | 1 | 10 |
| 4 | $p_1=p_2$ | 2 | 10 |
| 5 | $e=3$ | 1| 10 |
| 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 | 15 |
| 8 | 提供 $a=(p+2)(q+2)$ | 1| 15 |
| 9 | | 1 | 15 |
如果你使用 Python,那么下面这些可能可以帮助你:
- Python 自带函数 `pow(x, a, p)`,计算 $x^a \bmod p$。
- $d$ 的计算可以参考如下代码(需要 `primefac` 包):
```python
from primefac import modinv
p = ...
q = ...
e = ...
r = (p - 1) * (q - 1)
d = modinv(e, r) % r
```