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 ```