下面我按“出题脚本 → 漏洞来源 → 论文定理 → 利用代码 → 学习路径”这条线，把这道 CTF 题从头到尾非常细地讲清楚。你给的三个材料分别是：

• 论文：2025-1396.pdf，核心是针对 $n=6$ 的 generalized Wiener-type attack，给出 Theorem 8 和 Theorem 9。(2025-1396.pdf)
• 出题脚本：task.py，说明题目怎样生成 $N,e,c$。(task.py)
• 利用脚本：exp.py，说明实际怎么把论文攻击落地。(exp.py)

---

一、这道题本质上在考什么

这题本质不是普通 RSA，而是一个 RSA-like cryptosystem，使用的“欧拉函数”不再是

$$\varphi(N)=(p-1)(q-1)$$

而是

$$\phi_6(N)=(p^6-1)(q^6-1).$$

论文明确说明，这一族系统的密钥方程是

$$ed-k(p^n-1)(q^n-1)=1,$$

当 $n=1$ 就退化成普通 RSA；当 $n=6$ 时就是这道题对应的情况。(2025-1396.pdf)

而 task.py 里正是这样生成参数的：

python
phi = (p ** 6 - 1) * (q ** 6 - 1)
d = getPrime(int(nbits * 2))
e = pow(d, -1, phi)

也就是：

1. 先随机生成 512-bit 素数 $p,q$
2. 令 $N=pq$
3. 定义 $$\phi=(p^6-1)(q^6-1)$$
4. 随机选一个约 1024-bit 的素数 $d$
5. 再令 $$e \equiv d^{-1} \pmod{\phi}$$

这些都直接写在题目脚本里。(task.py)

---

二、先读懂出题脚本：为什么它会有漏洞

1. 题目生成方式

task.py 内容非常短，但信息量很大：(task.py)

python
nbits = 512

p = getPrime(nbits)
q = getPrime(nbits)
N = p * q

phi = (p ** 6 - 1) * (q ** 6 - 1)
d = getPrime(int(nbits * 2))
e = pow(d, -1, phi)
m = bytes_to_long(flag)
c = pow(m, e, N)

从这里可以立刻得到几个结论：

结论 A：模数 $N$ 是 1024-bit

因为 $p,q$ 都是 512-bit，所以 $N$ 约 1024-bit。(task.py)

结论 B：私钥 $d$ 只有约 1024-bit

而

$$\phi_6(N)=(p^6-1)(q^6-1)\approx p^6 q^6 = N^6,$$

所以 $\phi_6(N)$ 的量级大约是 6144-bit。

但出题人取的 $d$ 只有 1024-bit。也就是说，相对于模 $\phi_6(N)$，这个 $d$ 非常小。

这就是漏洞的根。

---

2. 为什么“小 $d$”会危险

普通 RSA 中，Wiener 攻击告诉你：如果

$$ed-k\varphi(N)=1$$

里的 $d$ 太小，那么 $\frac{k}{d}$ 会非常逼近 $\frac{e}{N}$ 或相关近似量，于是可以用连分数把 $k,d$ 找出来。

这篇论文做的是它的 $n=6$ 推广版。论文最后给出结论：

如果

$$d < \sqrt{\frac{N^6-162N^3+1}{2N\sqrt{N}+1100N^3}},$$

那么给定 $e,N$ 可以在多项式时间内分解 $N$。(2025-1396.pdf)

而 exp.py 第一行注释就已经把这个界写出来了：(exp.py)

python
# bound = sqrt((N ^ 6 - 162 * N ^ 3 + 1) / (2 * N * sqrt(N) + 1100 * N ^ 3))

现在看量级：

• 分子主导项是 $N^6$
• 分母主导项是 $1100N^3$

所以整个根号大约是

$$\sqrt{\frac{N^6}{N^3}}=N^{3/2}.$$

而题目里 $d$ 约是 1024-bit，即 $d\approx N$。 显然

$$N \ll N^{3/2},$$

所以它完全落在攻击范围里。

这题的核心不是加密写错了，而是密钥生成时把 $d$ 取得太小。

---

三、整个攻击链条概览

这题的完整利用流程是：

1. 利用密钥方程

   $$ed-k\phi_6(N)=1$$

   把它改写成论文里的统一形式

   $$ae-b\phi_6(N)=c$$

   在本题中其实就是

   $$a=d,\quad b=k,\quad c=1.$$

2. 论文证明：如果 $ab$ 足够小，则

   $$\frac{b}{a}$$

   会出现在

   $$\frac{e}{N^6-162N^3+1}$$

   的连分数收敛分数里。(2025-1396.pdf)

3. 所以我们枚举这个连分数的每个 convergent，把它看成 $(b,a)$ 的候选。

4. 对每个候选 $(a,b)$，论文 Theorem 8 给出一个非常精妙的公式，可以构造出一个对 $p$ 的近似值 $\hat p$，误差小于 $N^{1/4}$。(2025-1396.pdf)

5. 一旦我们有了“误差不超过 $N^{1/4}$ 的 $p$ 近似值”，就能用 Coppersmith 小根技术把真正的 $p$ 找出来。论文也明确调用了这个结论。(2025-1396.pdf)

6. 有了 $p$，就得到 $q=N/p$，接着重建

   $$\phi_6(N)=(p^6-1)(q^6-1)$$

   求出 $d$，最后解密拿到 flag。(exp.py)

---

四、先把论文里的数学对象翻译成人话

---

1. 密钥方程

题目本质满足

$$ed\equiv 1 \pmod{\phi_6(N)}$$

也就是存在整数 $k$，使得

$$ed-k\phi_6(N)=1.$$

论文统一研究更一般的形式：

$$ae-b\phi_6(N)=c.$$

对我们这题，直接代入：

• $a=d$
• $b=k$
• $c=1$

所以你在读 exp.py 时，一定要记住：

代码里的 a,b 不是随便起的变量，它们就是论文里连分数阶段要恢复出来的那两个整数，在这题里最终对应 $d,k$。(2025-1396.pdf)

---

2. 为什么会出现 $N^6-162N^3+1$

这是论文 Theorem 9 里最核心的近似中心。论文先把

$$\phi_6(N)$$

展开并整理，构造出一个“主项 + 误差项”的形式，最终得到：

$$ae-b(N^6-162N^3+1)=c-bA,$$

其中 $A$ 是一个可以被界住的误差项，而且满足

$$|A|<550N^3.$$

(2025-1396.pdf)

于是就能推出

$$\left|\frac{e}{N^6-162N^3+1}-\frac{b}{a}\right|<\frac{1}{2a^2},$$

再结合连分数经典定理：

若

$$\left|\zeta-\frac{u}{v}\right|<\frac{1}{2v^2},$$

则 $u/v$ 一定是 $\zeta$ 的某个 convergent。(2025-1396.pdf)

所以 $b/a$ 会出现在

$$\frac{e}{N^6-162N^3+1}$$

的收敛分数序列里。(2025-1396.pdf)

这就是 exp.py 为什么从这里开头：(exp.py)

python
denominator_approx = N^6 - 162 * N^3 + 1
cf = continued_fraction(e / denominator_approx)
convergents = cf.convergents()

对应关系非常直接：

• 论文里的近似中心：$N^6-162N^3+1$
• 代码里的 denominator_approx
• 论文说 $b/a$ 在该连分数的 convergents 里
• 代码就枚举 cf.convergents()

---

五、连分数部分：怎样“证明”能枚举到正确的 a,b

这是整题第一个知识点，也是最容易被“会用不会证”的地方。

1. 连分数判定定理是什么

论文第 2.1 节给了经典定理：

若

$$\left|\zeta-\frac{u}{v}\right|<\frac{1}{2v^2},$$

且 $\gcd(u,v)=1$，那么 $u/v$ 一定是 $\zeta$ 的一个收敛分数。(2025-1396.pdf)

这就是 Wiener 攻击以及各种 generalized Wiener attack 的根基。

---

2. 这里怎么把它用起来

论文第 3.2 节最终证明：

若

$$ab < \frac{N^6-162N^3+1}{2N\sqrt N+1100N^3},$$

则

$$\left|\frac{e}{N^6-162N^3+1}-\frac{b}{a}\right| \le \frac{1}{2a^2}.$$

(2025-1396.pdf)

因此 $b/a$ 会出现在这个连分数展开的收敛分数中。论文 Theorem 9 明确就是这么说的。(2025-1396.pdf)

---

3. 代码如何实现这个结论

exp.py 里：

python
cf = continued_fraction(e / denominator_approx)
convergents = cf.convergents()

for conv in convergents:
    b = conv.numerator()
    a = conv.denominator()

这里不是随便试分数，而是在严格利用“正确的 $b/a$ 必然是某个 convergent”这件事。(exp.py)

要特别注意变量方向：

• conv = b/a
• 所以 conv.numerator() 对应论文里的 $b$
• conv.denominator() 对应论文里的 $a$

这也正好解释了为什么代码写成：

python
b = conv.numerator()
a = conv.denominator()

---

六、为什么从 a,b 能反推出 p 的近似值

这是整题最关键、最有技术含量的一步。

---

1. 论文怎么处理 $\phi_6(N)$

论文定义：

• $S=p+q$
• $D=p-q$

然后把 $\phi_6(N)$ 重写成关于 $S$ 或 $D$ 的形式。对于 $S$，论文给出：(2025-1396.pdf)

$$\phi_6 = N^6 + 2N^3 - 9N^2S^2 + 6NS^4 - S^6 + 1$$

并继续整理成

$$\phi_6 = -(S^3-3NS)^2 + (N^3+1)^2.$$

然后由

$$\phi_6(N)=\frac{ae-c}{b}$$

得到

$$(S^3-3NS)^2=(N^3+1)^2-\frac{ae-c}{b}.$$

于是

$$S^3-3NS=\sqrt{(N^3+1)^2-\frac{ae-c}{b}}.$$

这就是一个三次方程。论文调用 Cardano 公式解这个三次方程，从而构造出 $\hat S$。(2025-1396.pdf)

同理，利用 $D=p-q$ 也能构造出 $\hat D$。(2025-1396.pdf)

---

2. 为什么可以近似到 $N^{1/4}$ 精度

论文的 Lemma 2 和 Lemma 3 证明：

$$|S-\hat S|<N^{1/4},\qquad |D-\hat D|<N^{1/4}.$$

(2025-1396.pdf)

于是

$$p=\frac{S+D}{2}$$

就有近似

$$\hat p=\frac{\hat S+\hat D}{2},$$

并且误差仍然小于 $N^{1/4}$。论文 Theorem 8 明确写出：(2025-1396.pdf)

$$\hat p= \sqrt[3]{\frac12\left(\sqrt{(N^3-1)^2-\frac{ae}{b}}+\sqrt{(N^3+1)^2-\frac{ae}{b}}\right)}.$$

注意这里代码里用的是 $c=1$ 且近似公式里省去了那个很小的修正项，本质上就是论文 Theorem 8 里的 $\hat p$ 公式。

---

3. 代码与公式一一对应

exp.py 里：(exp.py)

python
tmp1 = (N**3 - 1)**2 - (a * e / b)
tmp2 = (N**3 + 1)**2 - (a * e / b)

hat_p = round((0.5 * (sqrt(tmp1) + sqrt(tmp2)))^(1 / 3))

对应论文公式：

• tmp1 对应 $$(N^3-1)^2-\frac{ae}{b}$$
• tmp2 对应 $$(N^3+1)^2-\frac{ae}{b}$$
• 0.5 * (sqrt(tmp1) + sqrt(tmp2)) 对应 $$\frac12\left(\sqrt{(N^3-1)^2-\frac{ae}{b}}+\sqrt{(N^3+1)^2-\frac{ae}{b}}\right)$$
• 外层 ^(1/3) 就是立方根
• 最后 round(...) 是因为真实的 $\hat p$ 应该非常靠近整数 $p$

这一步就是把 Theorem 8 直接翻译成代码。(2025-1396.pdf)

---

七、为什么“知道 p 的近似值”就能分解 N

这是第二个核心知识点：Coppersmith 小根。

---

1. 论文使用了什么结论

论文第 2.3 节给出一个关键结论：

若给出了 $p$ 的近似值，且加法误差不超过 $N^{1/4}$，那么可以在多项式时间内分解 $N$。(2025-1396.pdf)

这就是题目攻击里“从 $\hat p$ 到真实 $p$”的桥梁。

---

2. 这个结论背后到底是什么

设

$$p=\hat p + x,$$

其中 $|x|<N^{1/4}$。

因为 $p\mid N$，所以

$$\hat p + x \equiv 0 \pmod p.$$

更常见的建模方法是在模 $N$ 下构造单变量多项式

$$f(x)=\hat p - x$$

或等价变体，然后把“真实偏差”当作一个很小的模根，再用 Coppersmith 求出这个小根 $x$。

本质上：

• 目标未知量不是整个 $p$，而只是偏移量 $x$
• 偏移量足够小，落在 Coppersmith 可解范围内
• 一旦恢复 $x$，就得到 $$p=\hat p+x$$

---

3. 代码是怎样做的

exp.py 里分两步：(exp.py)

第一步：先看看近似值是否已经正好命中

python
if hat_p > 1 and N % hat_p == 0:
    print("[!] Attack Success!")
    actual_p = hat_p
    break

这表示：有时 $\hat p$ 已经精确到就是 $p$，那直接除就行。

第二步：如果没有正中，就跑 small roots

python
R.<x> = PolynomialRing(Zmod(N))
f = hat_p - x
f = f.monic()
roots = f.small_roots(x=2**(int(nbits * 0.6)), beta=0.5, epsilon=0.1)

这段就是 Sage 里的 Coppersmith/Howgrave-Graham 风格小根求解。

它的含义是：

• 在 $\mathbb{Z}/N\mathbb{Z}$ 上建立多项式环
• 定义 $$f(x)=\hat p-x$$
• 找一个小根 $r$，使得 $$\hat p-r \equiv 0 \pmod{p}$$ 且 $r$ 足够小

然后代码继续：

python
for r in roots:
    actual_p = int(hat_p + r)
    if actual_p > 1 and N % actual_p == 0:
        print("[!] Attack Success!")
        print(f"Found p: {actual_p}")
        break

这里变量号写法有点“工程化”，但本质就是把 small root 给出的偏差补回去，得到真正的质因子 $p$。(exp.py)

---

八、恢复出 p,q,d 之后，怎样拿到 flag

一旦找到 $p$，剩下就是纯还原。

exp.py 后半段：(exp.py)

python
p = actual_p
q = N // p
phi6 = (p ** 6 - 1) * (q ** 6 - 1)
d = pow(e, -1, phi6)
m = pow(c, d, N)
flag = long_to_bytes(m)
print(flag)

每一步都很标准：

1. q = N // p

   $$q=\frac{N}{p}$$

2. phi6 = (p ** 6 - 1) * (q ** 6 - 1)

   $$\phi_6(N)=(p^6-1)(q^6-1)$$

3. d = pow(e, -1, phi6) 因为题目定义了

   $$e \equiv d^{-1}\pmod{\phi_6(N)},$$

   所以重新求逆元即可恢复 $d$。

4. m = pow(c, d, N) 解密。

5. long_to_bytes(m) 转回字节串，得到 flag。

最后利用脚本打印出的结果是：(exp.py)

python
# nctf{98b1e5c-9a3c-4d8e-9f1a-2b3c4d5e6f7g}

---

九、把每一个知识点和代码逐段绑定

下面这一段最适合你拿来复盘。

---

知识点 1：RSA-like 系统的密钥方程

数学

普通 RSA：

$$ed-k\varphi(N)=1$$

本题：

$$ed-k(p^6-1)(q^6-1)=1$$

题目代码

python
phi = (p ** 6 - 1) * (q ** 6 - 1)
e = pow(d, -1, phi)

(task.py)

利用代码

后面所有攻击都在恢复这条方程里的 $d,k$，只是改写成论文通用符号 $a,b,c$。(exp.py)

---

知识点 2：小私钥导致可攻击

数学

论文结论： 若 $d$ 小于某个界，则可分解 $N$。(2025-1396.pdf)

题目代码

python
d = getPrime(int(nbits * 2))

这里 $d$ 只有约 1024 bit，而 $\phi_6(N)\approx N^6$ 很大。(task.py)

为什么危险

因为它落入 generalized Wiener attack 适用区间。

---

知识点 3：连分数恢复候选 $(b,a)$

数学

若

$$\left|\zeta-\frac{u}{v}\right|<\frac{1}{2v^2},$$

则 $u/v$ 是 convergent。(2025-1396.pdf)

论文证明正确的 $b/a$ 是

$$e/(N^6-162N^3+1)$$

的某个 convergent。(2025-1396.pdf)

利用代码

python
denominator_approx = N^6 - 162 * N^3 + 1
cf = continued_fraction(e / denominator_approx)
convergents = cf.convergents()
for conv in convergents:
    b = conv.numerator()
    a = conv.denominator()

(exp.py)

---

知识点 4：由 $(a,b)$ 估计 $p$

数学

论文 Theorem 8 给出

$$\hat p= \sqrt[3]{\frac12\left(\sqrt{(N^3-1)^2-\frac{ae}{b}}+\sqrt{(N^3+1)^2-\frac{ae}{b}}\right)}$$

并证明

$$|p-\hat p|<N^{1/4}.$$

(2025-1396.pdf)

利用代码

python
tmp1 = (N**3 - 1)**2 - (a * e / b)
tmp2 = (N**3 + 1)**2 - (a * e / b)
hat_p = round((0.5 * (sqrt(tmp1) + sqrt(tmp2)))^(1 / 3))

(exp.py)

---

知识点 5：Coppersmith 小根恢复真实 p

数学

若知道 $p$ 的近似值，误差 $<N^{1/4}$，则可多项式时间分解 $N$。(2025-1396.pdf)

利用代码

python
R.<x> = PolynomialRing(Zmod(N))
f = hat_p - x
f = f.monic()
roots = f.small_roots(x=2**(int(nbits * 0.6)), beta=0.5, epsilon=0.1)

(exp.py)

验证

python
actual_p = int(hat_p + r)
if actual_p > 1 and N % actual_p == 0:

(exp.py)

---

知识点 6：恢复私钥并解密

数学

$$\phi_6(N)=(p^6-1)(q^6-1),\quad d=e^{-1}\bmod \phi_6(N).$$

利用代码

python
q = N // p
phi6 = (p ** 6 - 1) * (q ** 6 - 1)
d = pow(e, -1, phi6)
m = pow(c, d, N)
flag = long_to_bytes(m)

(exp.py)

---

十、这道题里最值得学的“证明套路”

你问的是“具体是怎样证明怎样利用”，这里我把证明思想抽成模板。

---

模板 1：先找到一个“近似中心”

普通 Wiener 攻击里，近似中心是 $N$ 或 $\varphi(N)$ 的某种近似。 这题里，论文构造出的近似中心是：

$$N^6-162N^3+1.$$

这一步的本质是：

• 真正未知的是 $\phi_6(N)$
• 但它可以展开成“主项 + 可控制误差项”
• 于是可以把 $$\frac{b}{a}$$ 看成逼近 $$\frac{e}{\text{主项}}$$

这是 generalized Wiener attack 的标准思路。

---

模板 2：用连分数把“非常好的有理逼近”枚举出来

只要你能证明某个未知分数 $b/a$ 满足

$$\left|\zeta-\frac{b}{a}\right|<\frac{1}{2a^2},$$

那么你就不用暴力枚举 $a,b$，而是直接枚举 $\zeta$ 的 convergents。

这就是“从指数级猜测”变成“多项式级遍历”的关键。

---

模板 3：从恢复关系参数，到恢复质因子近似值

这题很漂亮的一点是：

• 连分数恢复出来的不是 $p,q$
• 而是 $a,b$（本题中就是 $d,k$）
• 再通过代数变形把 $\phi_6(N)$ 转成 $S=p+q$、$D=p-q$ 的方程
• 然后用 Cardano 公式显式写出近似解

这是“数论近似 + 代数求根”结合的经典套路。

---

模板 4：近似到 $N^{1/4}$ 就交给 Coppersmith

这几乎是很多 RSA 变种题的通用终局：

• 先用各种分析拿到一个足够好的近似
• 再用 Coppersmith 补最后一小段误差

所以你要把 Coppersmith 理解成“最后一公里技术”。

---

十一、这份 exp 的工程细节，也值得注意

---

1. 为什么要 try/except

python
try:
    ...
except Exception:
    continue

因为很多错误候选的 $(a,b)$ 会让：

• $(N^3\pm1)^2-ae/b$ 变成负数
• 开平方失败
• 或者产生数值/类型问题

所以工程上直接跳过错误候选。

---

2. 为什么检查 bit_length

python
if hat_p.bit_length() > nbits or hat_p.bit_length() < nbits:
    continue

因为本题 $p$ 是 512-bit。错误 convergent 往往导出离谱的 $\hat p$，位数先不对。这个剪枝很实用。(exp.py)

---

3. 为什么先直接试除，再 small_roots

python
if hat_p > 1 and N % hat_p == 0:

这是因为理论上 $\hat p$ 只是近似值，但有时已经四舍五入刚好命中真实 $p$。先试一下几乎不花代价。

---

4. 为什么 small_roots 的界写成 2**(int(nbits * 0.6))

python
roots = f.small_roots(x=2**(int(nbits * 0.6)), beta=0.5, epsilon=0.1)

这不是论文里精确推导出来的常数，而是利用者根据实际经验给的参数。因为只要误差明显小于 $p$ 本身，往往就能搜出来。工程实现里常会有这种“理论保证 + 经验参数”的写法。

---

十二、这题和普通 Wiener 攻击的关系

你可以把它理解为普通 Wiener 攻击的升级版。

普通 Wiener 攻击

针对：

$$ed-k\varphi(N)=1$$

当 $d$ 很小时，$k/d$ 是 $e/N$ 的良好逼近，于是连分数能恢复 $d$。

本题 generalized Wiener attack

针对：

$$ed-k(p^6-1)(q^6-1)=1$$

因为模数结构更复杂，不能直接逼近 $e/N$，而要逼近

$$e/(N^6-162N^3+1).$$

恢复出 $(d,k)$ 的候选后，还要进一步通过一个更复杂的公式去近似 $p$，最后再用 Coppersmith 完成分解。(2025-1396.pdf)

所以这题比普通 Wiener 多了两层：

1. 更复杂的近似中心
2. 更复杂的“从 $a,b$ 到 $p$”的桥梁

---

十三、你应该怎样系统学习这题涉及的知识

我给你一个非常实用的学习路径，按顺序来。

---

第一阶段：夯实 RSA 基础

先确保这些你完全熟：

1. RSA 的密钥方程 $$ed\equiv 1 \pmod{\varphi(N)}$$
2. 为什么知道 $p,q$ 就能还原私钥
3. 模逆、快速幂、字节转整数

练习建议：

• 自己手写一份最小 RSA
• 自己手写 pow(e,-1,phi) 的扩展欧几里得版本
• 做几道基础 CTF RSA 题：共模攻击、低加密指数、小明文

---

第二阶段：学 Wiener 攻击

这是这题的根。

重点掌握：

1. 为什么 $$\frac{k}{d}\approx \frac{e}{N}$$
2. 连分数收敛分数是什么
3. 判定定理 $$\left|\zeta-\frac{u}{v}\right|<\frac{1}{2v^2} \Rightarrow \frac{u}{v}\text{ 是 convergent}$$
4. 为什么枚举 convergents 就能拿到候选 $d$

学习方法：

• 先只学普通 Wiener
• 手推 1~2 个小例子
• 自己写一遍不用 Sage 的 continued_fraction / convergents

---

第三阶段：学 Coppersmith 小根

这是很多高阶 RSA 题的通解核心。

要理解的不是“会调 Sage 参数”，而是：

1. 什么是 small root
2. 为什么知道高位/低位/近似值可以转成多项式求根
3. LLL 在这里起什么作用
4. 单变量模方程和双变量整数方程的区别

学习方法：

• 先学“已知 $p$ 高位分解 $N$”
• 再学“已知近似值，误差小于 $N^{1/4}$”
• 再学 Boneh-Durfee

---

第四阶段：学 generalized Wiener / RSA variants

当你已经熟 Wiener + Coppersmith 后，再来看这篇论文就会很顺。

你会发现它本质上就是：

• 连分数恢复关系参数
• 代数近似恢复素因子
• 小根补误差

这时论文就不再显得神秘。

---

十四、具体的练习方法

给你一个真正能提升的练法。

练法 1：手抄变量对应表

每看一篇论文，都先写：

• 论文里的 $a,b,c$ 对应题里什么
• $S,D$ 定义是什么
• 最终要恢复哪个量
• 代码里的哪个变量对应哪个数学对象

对这题，表就是：

• $a=d$
• $b=k$
• $c=1$
• $S=p+q$
• $D=p-q$
• hat_p 对应 $\hat p$

---

练法 2：把利用脚本拆成 4 个函数

你可以把 exp.py 重构成：

1. gen_convergents(e, N)
2. recover_hat_p(a, b, e, N)
3. recover_p_from_hat_p(hat_p, N)
4. decrypt_with_pq(p, q, e, c)

这样你会更容易看懂“每一段数学到底在干什么”。

---

练法 3：自己验证攻击界

不要只会跑 exp。

你可以在 Sage 里自己算：

• 题目中的 $N$
• 论文给的 bound
• 再比较题目里 $d$ 的量级

这会让你真正理解“为什么这个题必然能被打”。

---

练法 4：从普通 RSA 变种往上爬

建议顺序：

1. 普通 Wiener
2. Boneh-Durfee
3. 已知高位/低位分解
4. $n=2$ 的 RSA-like
5. $n=4$
6. $n=6$

这样爬最稳。

---

十五、这题最容易卡住的点

---

1. 误以为 pow(c, d, N) 不该对 RSA-like 系统成立

这题虽然论文背景来自更一般的 RSA-like 系统，但 task.py 实际上还是直接做了：

python
c = pow(m, e, N)

也就是普通整数模 $N$ 的幂运算。(task.py)

它只是把“私钥逆元的模”换成了 $(p^6-1)(q^6-1)$。这正是题目故意设计的地方：把 RSA 的密钥关系换成更大群阶下的逆元关系，制造小私钥漏洞。

---

2. 误以为连分数直接恢复的是 p/q

不是。

连分数阶段恢复的是满足

$$ae-b\phi_6(N)=c$$

的那个有理比 $b/a$。在本题里就是 $k/d$，不是 $p/q$。

---

3. 误以为 hat_p 是拍脑袋公式

不是。

它来自论文 Theorem 8，背后是：

• $\phi_6$ 的代数展开
• $S,D$ 变量代换
• Cardano 三次方程求根
• 误差估计

是严格推出来的。(2025-1396.pdf)

---

4. 误以为 Coppersmith 是“暴力枚举附近整数”

不是。

真正的 Coppersmith 是基于 LLL 的格攻击方法，利用的是“小根在模方程中可恢复”的理论。论文也在 preliminaries 部分明确回顾了 Howgrave-Graham、LLL 和 Coppersmith。(2025-1396.pdf)

---

十六、最后给你一个“最短复述版”

如果你要在比赛中快速复盘，这题一句话概括是：

题目把 RSA 的逆元模数改成了 $(p^6-1)(q^6-1)$，但私钥 $d$ 仍然取得很小，落入 generalized Wiener attack 范围。先通过连分数从 $e/(N^6-162N^3+1)$ 的 convergents 中恢复候选 $(k,d)$，再用论文给出的公式构造 $p$ 的近似值 $\hat p$，最后用 Coppersmith 小根恢复真实 $p$，从而分解 $N$、重建 $\phi_6$、求出 $d$ 并解密。(2025-1396.pdf) (exp.py)

---

十七、你接下来最值得做的事

建议你下一步就做这三件事：

1. 自己把 exp.py 改写成带注释的函数版。
2. 自己手推一次“为什么 $b/a$ 是连分数收敛分数”。
3. 再找一题普通 Wiener，比较它和这题的差别。

你上传的材料我都已经对应好了：论文在 (2025-1396.pdf)，利用脚本在 (exp.py)，出题脚本在 (task.py)。

如果你愿意，我下一条可以继续帮你做一份“逐行注释版 exp.py”，把每一行代码旁边都写上对应数学公式和作用。