之前给NepCTF 2022出了几道密码题，其中就包括这道… 官方题解WP在这里。当时是想出一道反论文题，不过赛后发现做出来的选手中很多还是看论文做的。题目对应的论文本身写得很差，不推荐阅读。

后来跟shallow师傅讨论了一下，又看了下当时的WP发现有很多细节没说，并且有点小问题。因此现在补充一下。

本题涉及内容

Carmichael定理, $\mathbb{Z}_{N}^{\ast}$ 的阶, Minkowski定理, Gauss reduction算法

模N乘法群中元素的阶（一个Carmichael定理的推导）

(2023.8 补充)： 不知道为什么之前自己写得那么复杂，实际上在群同构$\mathbb{Z}_{N}^{\ast} \cong \mathbb{Z}_{p}^{\ast} \times \mathbb{Z}_{q}^{\ast}$ 的视角下Carmichael定理是很容易看出来的。取模$p$原根$g_1$，模$q$原根$g_2$，$\mathbb{Z}_{N}^{\ast}$ 的元素在同构下对应某一个$(g_{1}^{x}, g_{2}^{y})$，于是他们的阶显然整除$\lambda(N)$。

以下思路过于繁琐，不过这里仍然保留一下。

WP中已经说明本题 $m^{1-e} \pmod n$ 比较小，这意味着$1-e$以极大的概率接近 $\text{ord}(m)$的倍数 ，据此我们可以推断出$1-e$的形式。现在关键问题是 $\text{ord}(m)$ 应该是什么样的形式？当时在这个问题上，很多师傅都翻车了。当时一位师傅做这个题的时候把 $\text{ord}(m)$ 想成了$\phi(N)$。那么 $\text{ord}(m)$ 实际上应该是什么样的形式呢？

先说结论：$\text{ord}(m)$ 整除 $\lambda := \lambda(N)=\text{lcm}(p-1, q-1)$

定理：设 $G$ 是有限Abel群，记 $ o = \max_{a \in G}{\text{ord}(a)} $ （ $o$ 为 $G$ 中阶最大的元素的阶 ），那么 $\forall a \in G, \ \text{ord}(a) \,| \,o$

为了说明 $ m^{\lambda} \equiv 1 \pmod{N} $，考虑群 $G = \mathbb{Z}_{N}^{}$. 这是一个有限交换的乘法群。假设$\mathbb{Z}_{N}^{}$中阶最大的元素是 $g$ ，考虑中国剩余定理。那么想让 $\text {ord}(g) = o$ 尽量最大的话，最好的可能就是 $g$ 同时是模 $ p $ 和 模 $ q $ 的原根。这时 $o = \text{lcm}(p-1, q-1) = \lambda$.

如果不存在一个元素同时是模 $ p $ 和 模 $ q $ 的原根，那么 $o$ 也一定整除 $\text{lcm}(p-1, q-1)$.

_不过根据原根的数量这种情况的概率应该很低？也可能根本不存在这种情况？我不清楚。好像有限Abel群结构定理能说明存在性，懒得想了。_

总之， $o$ 一定整除 $\lambda = \text{lcm}(p-1, q-1)$.

结合上个定理，可以推出以下定理。

Carmichael定理： 设 $N = p \cdot q$，其中 $p, q$ 皆为素数。设 $\lambda = \text{lcm}(p-1, q-1) $，则

$$\forall a \in \mathbb{Z}_{N} ^{\ast}, \ a^{\lambda} \equiv 1 \pmod{N}$$

因此 $\text{ord}(m)$ 整除 $\lambda$ ，因此 $\text{ord}(m)$ 也必然整除 $\phi(N)$

解题思路

总体概括

1. 在challenge.sage中结合Description.md的提示发现 get_e()是从secret中import的没有给出，但是 $e$ 的值是给出的，猜测这个 $e$ 可能有特殊形式所以不能给出。

   分析出attack_experiment.sage 攻击原理，写出使用的格。

2. 再根据参数满足理论上的攻击条件使用Minkowski定理（上界），分析出 $e$ 约等于 $\text{ord}(m)$ 的倍数，然后开始找 $e$ 和 $\phi(N)$ 的关系。

3. 计算 $N/e$ 发现非常接近7，因此 $\phi(N)/e$ 也非常接近7。

4. 据此对$\phi(N)$进行爆破，然后用 $\phi(N)$ 分解 $N$ 。

具体细节

1. 阅读attack_experiment.sage代码，推出其攻击原理如下：

$$c \equiv m^{e} \pmod{n} \Rightarrow \ c \equiv m^{x} \cdot m^{e-x} \pmod{n} \\ \Rightarrow m^{x-e} \cdot c \equiv m^{x} \pmod{n} \\ \text{令} \ x = 1, \text{则有} \ \ m^{1-e} \cdot c \equiv m \pmod{n} \ \text{。记}\ A = m^{1-e} \! \mod{n}，可得 \\ A\cdot c = m + B\cdot n \ \Rightarrow \ m = A \cdot c - B\cdot n \\ \Rightarrow \begin{bmatrix} A\\m \end{bmatrix} = A \begin{bmatrix} 1\\c \end{bmatrix} - B \begin{bmatrix} 0\\n \end{bmatrix} \ \ \text{，其中} \ A,B \in \mathbb{Z} \text{。} \\ 因此 \begin{bmatrix} A\\m \end{bmatrix} 为格中非零最短向量时可用格基规约算法恢复明文 m。$$

1. 根据分析，$\begin{bmatrix} A\\m \end{bmatrix}$ 满足Minkowski界. 于是有

$$A^{2} + m^2 = ( m^{1-e} \ \text{mod}\ n )^2 + m^2 \leq 2n$$

可见 $m^{1−e} \mod n$ 的量级最大为 $\sqrt{n}$ ，然而很难找到一般的 $e$ 来满足这一点.

1. 可以猜测出 $1−e$ 约等于 $\text{ord}(m)$ 的倍数。考虑找 $e$ 和 $\phi(N)$ 的关系。计算$N/e$发现很接近7，于是 $\phi(N)/e$很接近7。因此 $e= \phi(N)/7 - b$， 并且 $b$ 很小。

2. 对 $b$ 进行穷举。已知 $ \phi(N) = (p-1)(q-1) $ 分解 $N=pq$ 是容易的（中学数学），用 $n \mod p = 0$ 来判断当前分解是否正确即可。之后再做常规RSA解密就好了。

出题反思

1. get_e()没给出，可能有一点脑洞。应该写得再明白一些，e是为了试图满足原攻击条件的特殊的e。

2. 应该直接告诉大家，x在这里等于1。当时是想让大家不看论文并根据attack_experiment.sage的代码逻辑，自己推出论文中那个攻击的原理。但是CTF中大家无疑都是会去看论文的…

3. 附件中Description.md中的提示还是有点少，应该写明白预期解不是基于格的攻击。

4. WP的一个小问题：这道题的 $\phi(n)/7$ 是 $\text{ord}(m)$ 吗？不可能，注意到 $\lambda$ 是偶数，实际上两者是倍数关系。但是当时太懒就少打了几个字。

5. 正解的思路太复杂，招新赛出这个有点难了。