下面我按“题目做了什么 → 为什么成立 → 怎么利用 → 代码对应哪一行思路”的顺序，把这题完整拆开讲。

先说结论：这题的核心漏洞不是普通 RSA 那种“直接分解再私钥解密”，而是出题人把明文放进了指数里，同时又特意让 $p-1$ 含有巨大的 $2$-幂因子 $2^{79}$，于是我们可以把密文投影到模 $p$ 的一个 阶恰好为 $2^{79}$ 的子群里，把随机项完全消掉，再把指数里的消息 $m$ 一位一位剥出来。题目脚本里这一点几乎是明牌：k=79 #<-- i couldn't stress more。(伪ASR1.1.py)

我先把这题真正的攻击链写成一句话：

分解 $n$ 得到 $p,q$ → 利用 $p=2^{79}r+1$ 构造一个 $2$-Sylow 子群 → 把密文 $c=y^m x^{2^{79}}$ 提升到 $(p-1)/2^{79}$ 次方，随机数项 $x^{2^{79}}$ 被费马小定理抹掉 → 剩下 $g^m$ → 在一个阶为 $2^{79}$ 的群里做“按位离散对数”。
官方脚本里已经直接把 $p,q$ 硬编码进去了，说明实际解题时至少已经拿到了分解结果。(offical.py)

---

1. 题目代码到底在干什么

出题脚本最关键的部分有四段：

1. 选特殊素数 $p$：

   $$p = 2^k r + 1,\quad k=79$$

   也就是 $v_2(p-1)=79$ 很大。代码就是： p=2**k*r+1。(伪ASR1.1.py)

2. 选另一个素数 $q$：

   $$q=4r+3$$

   这是个 Blum prime 形式。代码： q=4*r+3。(伪ASR1.1.py)

3. 选 $y$，要求它对 $p,q$ 都是二次非剩余：

   python
   if legendre_symbol(y,p)==1: continue
   elif legendre_symbol(y,q)==1: continue

   也就是说：

   $$\left(\frac{y}{p}\right)=-1,\qquad \left(\frac{y}{q}\right)=-1$$

   这一步非常关键。(伪ASR1.1.py)

4. 加密：

   python
   c=(pow(y,m,n)*pow(x,pow(2,k),n))%n

   即

   $$c \equiv y^m \cdot x^{2^k}\pmod n$$

   其中 $x$ 是随机数。(伪ASR1.1.py)

官方解题脚本则做了这几件事：

1. 已知 $p,q,n,y,k$。(offical.py)
2. 定义

   python
   C = pow(c, (p - 1) // (2 ** k), p)
   D = pow(y, -(p - 1) // 2 ** k, p)

3. 用一个循环逐位恢复 $m$。(offical.py)

所以，真正要理解的是：

• 为什么升到 $(p-1)/2^k$ 次方能“去随机化”；
• 为什么剩下来的东西能唯一表示消息；
• 为什么 decrypt() 这个循环能一位一位读出 $m$。

---

2. 第一个知识点：为什么 k = 79 是整题的灵魂

题目自己都在提示你：k=79 #<-- i couldn't stress more。(伪ASR1.1.py)

这意味着：

$$p-1 = 2^{79} r$$

也就是说，模 $p$ 的乘法群 $\mathbb F_p^\*$ 的阶 $p-1$ 含有一个特别大的 $2$-幂部分。

因为 $\mathbb F_p^\*$ 是循环群，所以它必然有一个阶为 $2^{79}$ 的子群。这种子群对密码题非常危险，因为：

• 阶平滑（smooth），离散对数容易做；
• 还是 $2$-幂阶，能直接按二进制一位一位拆；
• 配合加密里的 $x^{2^k}$，会产生“把噪声直接指数消掉”的投影。

这就是整题最根本的结构性漏洞。

---

3. 第二个知识点：Legendre 符号和二次非剩余在这里有什么用

题目要求 $y$ 对 $p$ 和 $q$ 都是二次非剩余。代码是：

python
if legendre_symbol(y,p)==1:
    continue
elif legendre_symbol(y,q)==1:
    continue
else:
    return y

意思就是保留那些满足

$$\left(\frac{y}{p}\right)=-1,\qquad \left(\frac{y}{q}\right)=-1$$

的 $y$。(伪ASR1.1.py)

对模素数 $p$，Legendre 符号有个经典结论：

$$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p$$

因此如果 $y$ 是模 $p$ 的二次非剩余，那么

$$y^{(p-1)/2}\equiv -1\pmod p$$

这个“$-1$”特别重要，因为它正好可以帮我们证明后面构造出来的元素阶恰好是 $2^{79}$，不是更小的 2 幂。

---

4. 第三个知识点：为什么升幂以后随机项会消失

这是整题最核心的一步。

设

$$r=\frac{p-1}{2^k}$$

定义

$$g = y^r \pmod p$$

现在看密文

$$c \equiv y^m x^{2^k}\pmod n$$

把它转到模 $p$ 下，再升到 $r$ 次方：

$$c^r \equiv (y^m x^{2^k})^r \equiv y^{mr}x^{2^k r}\pmod p$$

由于 $2^k r = p-1$，所以

$$c^r \equiv y^{mr}x^{p-1}\pmod p$$

只要 $p\nmid x$，由费马小定理：

$$x^{p-1}\equiv 1\pmod p$$

于是

$$c^r \equiv y^{mr} \equiv (y^r)^m = g^m \pmod p$$

这一步的含义是：

原来密文里最烦人的随机项 $x^{2^k}$，在模 $p$ 且提升到 $r$ 次以后，彻底变成 1 了。

这就是官方脚本里的：

python
C = pow(c, (p - 1) // (2 ** k), p)

它实际算出来的就是：

$$C = g^m$$

也就是把“带噪声密文”变成了“纯净的指数编码”。(offical.py)

补一句严格性：如果随机 $x$ 恰好是 $p$ 的倍数，那么 $x^{p-1}\not\equiv 1\pmod p$。但这里 $x$ 从 $1$ 到 $n-1$ 随机选，恰好落在 $p\mathbb Z$ 的概率大约是 $1/q$，在这题里可以忽略。

---

5. 第四个知识点：为什么 $g = y^{(p-1)/2^k}$ 的阶恰好是 $2^k$

这是最关键的证明。

我们已经定义：

$$g = y^{(p-1)/2^k}\pmod p$$

先看 $g^{2^k}$：

$$g^{2^k} = y^{p-1}\equiv 1\pmod p$$

所以 $g$ 的阶一定整除 $2^k$。

但我们还要证明它不是更小的 $2^t$。

看 $g^{2^{k-1}}$：

$$g^{2^{k-1}} = y^{(p-1)/2}\pmod p$$

而因为题目专门让 $y$ 成为模 $p$ 的二次非剩余，所以

$$y^{(p-1)/2}\equiv -1\not\equiv 1\pmod p$$

于是

$$g^{2^{k-1}}\neq 1$$

这就说明 $g$ 的阶不可能小于 $2^k$。综合起来：

$$\operatorname{ord}_p(g)=2^k$$

这一步正是为什么题目非要让 get_y() 选 Legendre 符号为 $-1$ 的 $y$：不是为了“好看”，而是为了确保你构造出来的 $g$ 是 整个 2-Sylow 子群的生成元。(伪ASR1.1.py)

---

6. 第五个知识点：为什么消息必须小于 $2^k$

出题脚本里有一句注释：

python
#assert int(bytes_to_long((flag_pieces[i] for i in range(5)))).bit_length()==k

虽然这句写得不太规范，但它明显在强调：分块后的消息位数必须压在 $k$ 比特以内。 (伪ASR1.1.py)

因为你最后得到的是

$$C=g^m$$

而 $g$ 的阶是 $2^k$，所以你能恢复的本质上是：

$$m \bmod 2^k$$

如果 $m\ge 2^k$，那离散对数只会给你 $m$ 在模 $2^k$ 意义下的值，不再唯一。

所以题目的真实设计思想是：

• 把 flag 拆成若干段；
• 每一段都控制在不超过 79 比特；
• 这样每段对应的 $m$ 都能被唯一恢复。

你上传的生成脚本切片和最终恢复出的每段长度并不完全一致，这说明这份脚本可能是改写/脱敏过的版本；但密码学核心完全不受影响，因为真正重要的是“每块 $m<2^{79}$”。

---

7. 第六个知识点：这其实是在一个 $2$-幂阶群里做离散对数

到这里，题目已经从“奇怪的加密”变成了标准问题：

$$C = g^m \pmod p,\qquad \operatorname{ord}(g)=2^k$$

求 $m$。

一般离散对数很难，但如果群阶是 $2^k$，就会非常简单，因为可以按位恢复。

把 $m$ 写成二进制：

$$m = b_0 + 2b_1 + 2^2b_2 + \cdots + 2^{k-1}b_{k-1},\quad b_i\in\{0,1\}$$

目标就是逐个求出 $b_0,b_1,\dots,b_{k-1}$。

官方 decrypt() 本质上就是一个 针对阶为 $2^k$ 的离散对数求解器，可以看作 Pohlig–Hellman 在 2-幂阶上的特化版。(offical.py)

---

8. 第七个知识点：decrypt() 为什么能一位一位地把 $m$ 剥出来

这是这题最值得吃透的部分。

8.1 初始变量都代表什么

官方代码：

python
m = 0
B = 1
C = pow(c, (p - 1) // (2 ** k), p)
D = pow(y, -(p - 1) // 2 ** k, p)

含义分别是：

• m：已经恢复出的消息；
• B：当前正在恢复的那一位的权重，初始为 $2^0$；
• C：当前剩余的群元素，初始为 $g^m$；
• D：当前“清零器”，初始为 $g^{-1}$。(offical.py)

注意：

$$D = y^{-(p-1)/2^k} \equiv g^{-1}\pmod p$$

因为 Python 的 pow(a, -e, mod) 表示模意义下的逆元幂。

---

8.2 循环里那句 z = pow(C, 2 ** (k - j), p) 到底在测什么

循环体是：

python
for j in range(1, k):
    z = pow(C, 2 ** (k - j), p)
    if z != 1:
        m += B
        C = (C * D) % p
    B <<= 1
    D = (D * D) % p

(offical.py)

我们来证明它每一轮都在判定一个 bit。

---

8.3 归纳不变量

设经过前 $j-1$ 轮后，已经把低 $j-1$ 位都恢复并从指数里“消掉”了，于是当前

$$C = g^{e_j}$$

其中

$$e_j = \sum_{i=j-1}^{k-1} b_i 2^i$$

也就是说，低于 $2^{j-1}$ 的部分都没了，因此 $e_j$ 一定能写成

$$e_j = 2^{j-1} t$$

其中 $t$ 的奇偶性恰好就是当前要恢复的 bit $b_{j-1}$。

现在看

$$z = C^{2^{k-j}}$$

代入 $C=g^{e_j}$：

$$z = g^{e_j 2^{k-j}} = g^{(2^{j-1}t)2^{k-j}} = g^{t2^{k-1}}$$

而我们已经知道 $g^{2^{k-1}}=-1$，所以

$$z = (-1)^t$$

因此：

• 若 $t$ 偶数，则 $z=1$，说明当前 bit $b_{j-1}=0$；
• 若 $t$ 奇数，则 $z=-1\neq 1$，说明当前 bit $b_{j-1}=1$。

这就是为什么代码里只判断：

python
if z != 1:

因为在这个群里，测到的实际上就是“当前待恢复系数的奇偶性”。

---

8.4 为什么 C = C * D 就能把这一位清掉

如果当前 bit 是 1，那么当前指数里含有一项 $2^{j-1}$。

这时 D 维护的是：

$$D = g^{-2^{j-1}}$$

于是

$$C \leftarrow C\cdot D$$

就等于把指数减去 $2^{j-1}$，恰好把当前这位清零。

然后代码做：

python
D = (D * D) % p

如果当前 $D=g^{-2^{j-1}}$，平方以后：

$$D^2 = g^{-2^j}$$

正好为下一轮准备好“清第 $j$ 位”的工具。

所以这段代码不是技巧性的魔法，而是一个很干净的状态维护：

• B 维护当前位权 $2^{j-1}$；
• D 维护当前位对应的逆元 $g^{-2^{j-1}}$；
• C 维护“还没被清掉的高位部分”。

---

8.5 为什么最后单独写一个 if C != 1

循环只跑到 range(1, k)，也就是恢复了前 $k-1$ 位中的低 $k-1$ 位，最高位没在循环中单独判。

原因是：当你把前 $k-1$ 位都处理完后，剩余指数只可能是

$$0 \quad\text{或}\quad 2^{k-1}$$

因此此时

$$C \in \{1,\ g^{2^{k-1}}\} = \{1,-1\}$$

所以：

python
if C != 1:
    m += B

就是在判定最高位是否为 1。(offical.py)

---

9. 把“知识点”和“代码”一一对上

下面这个表最适合你做题后复盘。

知识点	出题代码	数学意义	解题代码
$p-1$ 含大 $2$-幂	p=2**k*r+1	$v_2(p-1)=k$，存在阶 $2^k$ 子群	pow(c, (p-1)//2**k, p) 利用这个结构投影
选 $y$ 为二次非剩余	legendre_symbol(y,p)、legendre_symbol(y,q)	保证 $y^{(p-1)/2}=-1$，从而 $g$ 阶恰为 $2^k$	D = pow(y, -(p-1)//2**k, p) 实际上是 $g^{-1}$
明文放在指数里	pow(y,m,n)	加密本质是 $y^m$	C 最终变成 $g^m$
随机化项是 $2^k$ 次幂	pow(x, 2**k, n)	升到 $(p-1)/2^k$ 次后变成 $x^{p-1}\equiv1$	C = pow(c, (p-1)//2**k, p)
消息大小限制	分块 + 注释强调 k=79	确保 $m<2^k$ 可唯一恢复	decrypt() 恢复的是一个 79 位以内整数
在 $2$-群中做离散对数	整个构造共同决定	问题化成 $C=g^m$	z != 1 按位测试，C*=D 清位

出题脚本对应上表左三列，官方脚本对应右一列。

---

10. 实际解题时，完整攻击流程是什么

如果你拿到的是公开输出：

• n
• y
• cs

而不是官方脚本里的 p,q，那流程一般是：

第一步：分解 $n$

这题的 $n$ 只有 298 比特左右，不是安全参数。官方解题脚本直接把 $p,q$ 写死，本身就说明真正利用阶段默认你已经有分解结果了。(offical.py)

拿到 $p$ 以后，这题基本就结束了，因为攻击只用到了模 $p$ 这一侧；官方脚本里 q 虽然也写出来了，但 decrypt() 实际完全没用到 q。(offical.py)

第二步：构造 $g$

$$r=\frac{p-1}{2^k},\qquad g=y^r \pmod p$$

第三步：把每个密文投影成 $g^m$

$$C=c^r \pmod p$$

第四步：做 2-幂阶离散对数

也就是官方 decrypt() 干的事。(offical.py)

第五步：整数转回字节串

python
long_to_bytes(m)

官方脚本最后就是这么输出明文块的。(offical.py)

---

11. 把官方解法重写成“带注释的数学版”

下面这段是最值得你自己手敲一遍的版本：

python
def solve_one(c, p, y, k):
    r = (p - 1) // (2 ** k)     # r = (p-1)/2^k
    g = pow(y, r, p)            # g has exact order 2^k
    C = pow(c, r, p)            # C = g^m, random term disappears

    m = 0
    B = 1                       # current bit weight = 2^0
    D = pow(g, -1, p)           # D = g^{-1}

    for j in range(1, k):
        # Test current bit by pushing C into the order-2 subgroup
        z = pow(C, 2 ** (k - j), p)

        if z != 1:              # means current bit is 1
            m += B
            C = (C * D) % p     # remove this bit from exponent

        B <<= 1                 # next bit weight
        D = (D * D) % p         # g^{-2^{j-1}} -> g^{-2^j}

    # highest bit
    if C != 1:
        m += B

    return m

每一行的数学解释我上面已经全部展开了。这个版本和官方 decrypt() 完全同构。(offical.py)

---

12. 这题和哪些经典知识点是同一类

这题不是孤立技巧，它把几个很经典的主题缝到了一起：

12.1 二次剩余 / Legendre / Jacobi

你要熟悉：

• 什么是 quadratic residue / non-residue
• Euler 判别： $$a^{(p-1)/2}\equiv \pm1 \pmod p$$
• 为什么非剩余能制造出 $-1$

这题 get_y() 的精华就在这。(伪ASR1.1.py)

12.2 群阶分解与 Sylow 子群

看到

$$p-1 = 2^{79}r$$

脑子里要立刻想到：

• $\mathbb F_p^\*$ 有大 2-Sylow 子群；
• 离散对数如果落到这种平滑子群里，就危险。

12.3 Pohlig–Hellman 思想

一般 PH 是“群阶可分解，就分解后分别求 DLP 再 CRT 合并”。

这题更简单，因为群阶本来就是 $2^k$，所以变成直接按位恢复。

12.4 随机化项被“投影”消掉

很多题会故意加一个看似很随机的项，但如果这个随机项位于某个“已知幂子群”中，就能被特定指数投影消掉。这题的

$$x^{2^k}$$

就是这种典型设计。

---

13. 这题里容易忽略的几个细节

13.1 为什么只用 $p$ 就够了

因为整个恢复过程只依赖：

$$c^{(p-1)/2^k}\pmod p$$

只要一侧素因子有这种弱结构，就足够泄露信息。
所以“另一个素因子 $q$ 正不正常”并不能补救。官方脚本里 decrypt() 完全没有用 q 就已经说明这一点。(offical.py)

13.2 为什么 q = 4r + 3 不是主要攻击点

它更多是题目风格的一部分，让 $q\equiv 3 \pmod 4$ 比较像 Blum integer 的味道。真正致命的是 $p$ 那边的 $2^{79}$ 结构，不是 $q$ 的 +3。

13.3 为什么 mod_inverse 被导入了却没用

offical.py 里有：

python
from sympy import mod_inverse

但后面没用到。因为 Python 本身的

python
pow(a, -e, mod)

已经能处理模逆幂了。(offical.py)

---

14. 用你这两份文件实际恢复出的结果

按官方解题逻辑对给定常数运行，能恢复出 5 段明文，拼起来是：

text
flag{go0_j06!let1sm0v31n_t0_th3renges~>_<}

这个结果字符上看有一点怪，说明你上传的生成脚本和真实出题版本之间大概率有过脱敏或改写；但密码学利用链是完全闭合的，因为官方脚本中的参数和算法确实能恢复出这一串。核心知识点不受影响。依据是题目给出的 n,y,cs 和官方 decrypt() 逻辑。(offical.py)

---

15. 一条真正有用的学习路径

下面这条路线是专门为“以后你自己能独立拆这种题”设计的，不是泛泛而谈。

第一阶段：把数论底层打实

目标：你看到式子能立刻做群论翻译。

要掌握：

• 模运算与快速幂
• 费马小定理、欧拉定理
• 模素数乘法群 $\mathbb F_p^\*$ 是循环群
• 元素阶、子群、生成元
• $v_2(n)$ 这种 2-adic valuation

练习方法：

• 自己手写一个函数，求一个元素在模 $p$ 下的阶；
• 自己构造 $p=2^k r+1$ 的小素数，验证确实存在阶 $2^k$ 的元素。

第二阶段：专攻二次剩余

目标：看到 legendre_symbol 不再只会背定义，而是知道它能制造什么。

要掌握：

• Legendre symbol
• Euler criterion
• 二次剩余与非剩余
• Jacobi symbol 和“Jacobi=1 但不一定是平方”的现象

练习方法：

• 写代码枚举小素数下所有平方和非平方；
• 验证 $a^{(p-1)/2}$ 只会得到 $\pm1$。

第三阶段：离散对数与群阶平滑攻击

目标：看到平滑阶就知道 DLP 会变简单。

要掌握：

• 离散对数定义
• Pohlig–Hellman
• 为什么群阶分解后好做
• 为什么 $2^k$ 阶尤其适合按位恢复

练习方法：

• 先在阶 $2^5,2^6$ 的小群上手搓这题的 decrypt()；
• 不要一开始上大数，先用小例子把循环不变量证明清楚。

第四阶段：把“随机项投影消掉”的套路练熟

目标：以后你看到

$$\text{message term} \times \text{structured noise}$$

会主动想“有没有指数能把 noise 打成 1”。

要掌握：

• 幂映射
• 核与像的直觉
• 利用群阶把某类元素投影到单位元

练习方法：

• 自己造一个玩具加密： $$c = g^m h^r$$ 其中 $h$ 落在已知小子群里，试着找指数消掉它。

---

16. 最有效的学习方法，不是刷更多题，而是这样做复盘

我最建议你用下面这套方法复盘这题。

方法一：把这题缩小成玩具版本

比如把 $k$ 改成 4，不用 79。

取一个小素数：

$$p = 2^4\cdot r + 1$$

然后自己选个非剩余 $y$，自己造

$$c = y^m x^{16}\pmod p$$

你会非常直观地看到：

• $c^{(p-1)/16}$ 为什么变成 $g^m$
• z != 1 为什么真的是在测当前 bit

方法二：每次都写出“变量对应的群论含义”

例如：

• C 不是“某个中间量”，而是“当前剩余指数对应的群元素”
• D 不是“辅助变量”，而是“当前位逆元清零器”
• B 不是“累加器”，而是“当前 bit 的权重”

只要这样想，题就不容易背错。

方法三：强迫自己证明循环不变量

你以后碰到任何“按位恢复”型题，都要问自己：

• 循环开始前变量代表什么？
• 一轮之后这个含义是否保持？
• 判定条件为什么只会落在两个值上？

这题就是最好的练习材料。

---

17. 这题如果你要写成题解，最好的结构是什么

如果你准备自己写一篇高质量题解，我建议结构就是这 6 段：

1. 观察到 $p=2^{79}r+1$，说明 $p-1$ 有巨大 2 幂因子；
2. 观察到 $y$ 是模 $p$ 的非剩余，因此
   $g=y^{(p-1)/2^{79}}$ 的阶恰为 $2^{79}$；
3. 对密文升到 $(p-1)/2^{79}$ 次方，随机项 $x^{2^{79}}$ 消失；
4. 剩下 $C=g^m$，问题变为在 $2^{79}$-阶群里求离散对数；
5. 证明 decrypt() 是逐位恢复 $m$；
6. 转字节并拼回 flag。
   这些论证都能从你上传的生成脚本和官方脚本直接对应出来。

---

18. 最后给你一个一句话记忆版

以后你看到下面这三个条件同时出现：

• $p-1$ 含很大的小素数幂，尤其是 $2^k$
• 密文里有某种“$2^k$ 次幂随机项”
• 明文被编码到某个固定底数的指数里

你就应该立刻警觉：

这大概率是在把密文投影到一个平滑子群里，然后做 Pohlig–Hellman / 按位离散对数。

这题就是这个套路的一个非常标准、非常适合练基本功的版本。