2026 AIS3 Pre Exam Official Writeup - Crypto

, , , , , , ,

Before all

完整題目可以從: https://github.com/William957-web/My-CTF-Challenges/tree/main/AIS3-Pre-Exam/2026/crypto 下載

整體而言這次題目 code base 和解題腳本都偏大，要了解細節建議對照著 Github 看。

預期難度(由易到難)
EasyWEB < EasyJWT < EasyZKP < EasyPAINT < EasyFAULT <= EasyRSA

🤔 其實這次真的沒有往死裡出，詳情請看接下來的 writeup！

Writeup

EasyWEB

Web Crypto 黑箱題目，可以輸入 username 和 note 內容
選擇使用 Cloudflare 五秒盾 + 後來失效的 Google Recaptcha 防 Agent 自動化解題，可以擋一下但認真唱一唱其實唱的過去，笑死
image

應該會注意到送出後會拿到一個 session cookie
也會注意到前端（後端也有）禁止 username 以 . 和 / 開頭，可以猜測是 Path Traversal 的 Patch

這時候如果在 name 輸入各種 input 像是 100 個 a 之類的會得到兩個資訊

  1. 輸入內容都是 16 的倍數 bytes 的 hex string
  2. 會有重複的 block 出現

ECB Mode!
進行 ECB Copy and Paste Attack 就可以做到 LFI
Payload 就如同 a*16 + /etc/passwd\x05\x05\x05\x05\x05，再把拿到的 session 去除前 16 Bytes 複製貼上拿去當新的 session 即可讀到 /etc/passwd (在這邊要特別去記得處理 )

最後就是讀取 /proc/self/cmdline 取得當前 process cmdline + 讀取 app.py 就可以拿到原始碼 (flag)

EasyJWT

一樣是一個看起來很像 Web 題的題目，目標是要透過 XSS 去戳到限制內網的網站 /flag URI 拿取 flag

XSS 觸發點在這: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@app.route("/")
def index():
    token = request.cookies.get("token")
    if token is None:
        return """
        <form action="/login">
          <input name="text" autocomplete="off">
          <button>login</button>
        </form>
        """
    if jwt.verify_jwt(token) == "OK":
        data = jwt.payload_json(token)
        user = data["user"]
        text = data["text"] 
        return f"Welcome {user}, you said {base64.b64encode(text.encode()).decode()}"
    return jwt.payload_bytes(token), 500

如果在 verify_jwt 的時候發生 error，那就會回傳 500 然後把 jwt token 內容 payload (JSON) 完全送出

稍微介紹一下 RS256 的 JWT 是怎麼實作的，簡單說就是把 Token 內的資料取 SHA256 後，做 RSA Signing，也就是把加密的過程反過來做：利用私鑰 $d$ 把訊息取 $H(m)^d(mod\space N)$ 作為簽章值交出

仔細 code review 一下 jwt.py 會發現是固定了公鑰 $e$ 後使用輾轉相除法，針對 $e, \phi(N)$ 構造一個 $ed-\phi(N)x=1$ 的過程求模逆元(其中 $x$ 值不重要 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
E = 677676677


def is_prime(n):
    for _ in range(1337):
        if pow(random.randrange(1, n), n - 1, n) != 1:
            return False
    return True


def inverse(a, m):
    old_r, r = a, m
    old_s, s = 1, 0

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
    return old_s

欸，等等等，不對不對。
首先我們的 $e=673 * 1006949$ … 其實沒什麼大問題，但是在求取 inverse 的時候，如果 $e$ 與 $\phi(N)$ 不互質，那麼輾轉相除法解出來的是 $ed-\phi(N)x=gcd(e, \phi(N))$，而 673 其實不是一個大質數…不會難撞到。
如果撞到了，就會導致在驗證簽名的時候有 $\operatorname{sign}^e \equiv H(m)^{ed} \equiv H(m)^{gcd(e, \phi(N))} \not\equiv H(m) \space (mod \space N)$
進而產生 error，而 JWT 初始化的時候會吃一個 text 參數存進去，在 /login 路由是一個 GET 參數，可以用來把 XSS Payload 寫入 JWT Token 

1
2
3
4
5
6
7
8
9
@app.route("/login")
def login():
    text = request.args.get("text", "")
    user = "admin" if local_addr() else "user"
    token = jwt.sign_jwt({"user": user, "text": text})
    resp = make_response(redirect("/"))
    resp.set_cookie("token", token, httponly=True, samesite="Lax")
    resp.headers["X-Token"] = token
    return resp

再來，雖然 673 不算大，但是要一次命中也不容易，儘管題目有開 challenge instancer，但重複去洗個 600 多次對選手或出題團隊其實也是個負擔 T^T
注意到這個 Flask 網站有開啟 debug mode，並且在 /upload 上傳路由中有個 t 參數可以指定檔案來做 os.utime 更新檔案時間，如果我們一直去更新網站程式檔（如 app.py 之類的），因為 debug 模式開啟所以會一直重啟整個服務，這時候就會生成新的 RSA 參數，直到 $\phi(N)$ 與 $e$ 不互質我們就贏了！ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@app.route("/upload", methods=["GET", "POST"])
def upload():
    if request.method == "GET":
        return """
        <form method="post" enctype="multipart/form-data">
          <input type="file" name="file" accept=".jpg,.jpeg,image/jpeg">
          <button>upload</button>
        </form>
        """
    f = request.files["file"]
    name = f.filename.lower()
    if request.args.get('t') is not None:
        test = request.args.get('t')
        os.utime(os.path.join(BASE_DIR, test))
    
    data = f.read()
    if (name.endswith(".jpg") or name.endswith(".jpeg")) and data.startswith(b"\xff\xd8\xff") and local_addr():
        path = os.path.join(UPLOAD_DIR, secrets.token_hex(16) + ".jpg")
        with open(path, "wb") as out:
            out.write(data)
        
        return "OK"
    return "Wrong", 403

最後還有一點就是，在繳交 URL 的時候會驗證一個 PoW (Proof of Work) 的 Challenge，本來我設計的 challenge size 是 36 bits 並提供了 PoW Script，但這樣在 instancer 給的 15 分鐘內幾乎不可能跑得完。所以還有一點是要自己改寫腳本，去申請比較多 challenge （像是　$2^{12}$ 組），再離線去計算大約 $2^{24}$ 量級的 Challenge 會比較合理（就是做 Meet in the Middle）。

解題腳本有點長就請看我 Github Repo 吧 XD

EasyZKP

一個架構題，內部有個 HTTP Server 作為 Proover，外部跟你 nc 互動的則會作為 client 去請求新的 Proof 下來，整體偏向 Σ-protocol 的 ZKP?!（其實不是 lol，只是概念像而已但隨便
目標是能在題目給定 seed 和 server challenge 的情況下 fake 十六個 proof 出來 (注意到這邊還是可以給 user challenge)

整體的模式是，以 Flag 作為 Secret，每次可以提供一個 user challenge，而 client 會再生成一個隨機的 seed $s$ 與 server challenge，結合的 Challenge 是 user||server
最後會以 sha256(FLAG||Challenge) 生成一個 state (256 bits state)
最後要產出的 proof $p$ 初始是 0，如果現在 state 的 bit = 0
$p \equiv p+s \space (mod \space N)$
否則就是
$p \equiv p^s \space (mod \space N)$
這樣做 256 次後會產出 proof，而這個 proof 只有持有 FLAG 的人可以拿出，最後證明的方法就類似事後才有持有者給出該　Challenge 的 Hash value 再讓大家自己算算看（不過這 part 沒在題目中出現，題目設定中沒有直接的 Hash 值可以拿）

另外，這題還有加入一個 fault attack condition，玩家可以選擇一個 bit 位置然後每次 sha256 產出的結果那一個位元會被翻轉
而限制是只能 query 領 proof 128 次 + fault attack 128 次

參數範圍的 $N$ 在電腦上可以用 cado-nfs 幾分鐘完成因數分解拿到 p, q，也可以直接去查 factordb
第一個漏洞在這邊，在我們提供 Challenge 的時候： 

1
2
3
4
5
6
7
8
9
10
11
12
def fetch_proof(user_part_b64, server_part_b64, seed, bit_flip_indices=None):
    flip_query = ""
    if bit_flip_indices is not None:
        for index in bit_flip_indices:
            flip_query += f"&f={index}"
    url = f"{PROVER_URL}?p={server_part_b64}{flip_query}&d={user_part_b64}&s={seed}"
    with urlopen(url, timeout=5) as response:
        payload = json.loads(response.read().decode())
    proof = payload.get("proof")
    if not isinstance(proof, int):
        raise ValueError("invalid prover response")
    return proof

這邊是直接把 user_part_b64 變數放進去 URL 裡面，但是 seed 參數在它的位置後面，等於我們可以透過多注入一段 &s=... 去控制 seed value。

回顧剛剛的流程，接下來我們可以考慮可控的 seed value 可以怎麼攻擊，先把目標定為還原 sha256 計算結果（因為我們給定的 user challenge 就是部分後綴，一但有一筆計算結果，可以利用 Length Extension Attack 在未知秘密 FLAG 的情況下計算出 sha256 value）。
首先 seed 有個範圍限制 必須介於 $2 \sim N-1$，阻絕了直接把 seed 設為 1 做很簡單 oracle 的可能性。
這時候考慮到 高次剩餘 (link)，我們可以把 seed 設成 $\phi(N)$ 的某個大因數，接著拿到數字結果後判斷它是不是一個 s 次剩餘，如果是的話那目前執行到的最後一個 bit 就很高機率是 1（大因數的原因是讓加法後產出的數字幾乎不可能剛好是個 s 次剩餘）
但是 s 次剩餘共有 s 個根，一旦我們為了攻擊穩定性把 s 調高，那逆推就顯得極為困難了，這時候如果當前測試的最後一個 bit 是 1 就把它 flip 成 0，後面解下一個 state 的時候記得先減去 s 即可。
如果測試出來 bit 是 0 那運氣挺好的，等等計算的時候只需直接把它減去就可以解下一個 state 了。

最後，因為 sha256 結果有 256 bits，我們可預期期望值大概有 128 個 1 和 0，query 和 fault attack 各 128 次操作有很高機率會讓我們能還原整個 sha256 算出來的結果。
結束後就是在申請 challenge 的時候使用 sha256 length extenstion attack 利用剛剛還原的 sha256 state + 我們控制後綴來解出 sha256 推算值，並依樣畫葫蘆算出 proof 去驗證就好，唯一的麻煩是 LEA 跟 salt(前綴，也就是 flag)長度有關，所以要去爆破一下。

EasyPAINT

我希望選手在畫畫的時候是開心的

原本在 64*64 的畫布上是長這樣的。 XD
螢幕擷取畫面 2026-03-23 200336

這題其實是 Reverse + Crypto，用 Pygame 寫了支加密玩具後用 Nuitka 做包裝，其中 Nuitka 的原理其實就是把 Python source code parse 出來後 compile 成 pyc 包進去，最後再把需要的 lib 作為 dependencies 一起裝進去。

一開始打開是一個密碼輸入介面，如果有逆向的話就會知道密碼 charset 是這些 "abcdefghijklmnopqrstuvwxyz_0OABCDEFG"，而密碼比對是去比對一個 sha256 value，而密碼大小是 512 chars。

接下來的加密流程是用 LWE，整個加密流程是透過 512 x 512 的畫布畫出來的黑白建立 0/1 的 Public Key Matrix $A$，把密碼的每一個字元都建取 sha256 排成一個 512 維的 secret vector $s$，$Q \sim 256 \space bits$ 而 $p=257$，會生成一組 mod p 的 error vector $e$，最後我們要加密的訊息（對稱式解密訊息用的密鑰）的 key vector 是 $k$，其中每一位都是 1 byte 的某個數字

LWE 的流程是：
$$A\times s + 256 e + k$$
只有持有 $A$ 以及私鑰 $s$ 的人可以 unmask，最後再把每一項 mod $p$ (256) 來提取 $k$
這題要解決的問題有幾個：

  • 沒有公鑰 $A$
  • 我們到底持有多少 $s$ 的資訊

注意到雖然我們沒有私鑰 $s$ 的內容，但我們知道它的每一項都是某個字母取 sha256 後的 hash value，所以 $A\times s$ 可以想像成產出的每一列都是 “該字母這次被 0/1 Vector 數了幾次”，而這個次數其實挺小的，是已知項的線性組合其中每個 entry (數幾次) 都很小
最後因為 $e$ 其實量級(16 bits) 相對於整個 mod 和前面的運算 (256 bits) 極小，所以其實 $A\times s \approx A\times s + 256 e + k$，可以直接做 CVP(link) 或者把 $256e$ 當作另一個小根利用 LLL(link) 解線性方程都是可以的！ （不過這邊可能會需要調整配重）

至於 LLL 解小根方程的簡單介紹可以看我以前出的題目：
NoHackNoCTF 2024(link)
配種可以看這個
THJCC CTF 2025 (link)

EasyFAULT

LLL 大題，其實分成三個階段：

  1. 從 blob 裡還原 base
  2. 用 base 把 data 裡被 XOR mask 掉的 exponent fault 還原
  3. 利用很多組
    $$
    y_i \equiv c^{d \oplus r_i} \pmod n
    $$
    的關係，先還原 RSA modulus $n$，再還原明文 $m$

題目核心程式碼如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
c, n, d = gen()
rows = [randbits(BITS) for _ in range(ROUNDS)]
base = randbits(WIDTH - 1) | (1 << (WIDTH - 1))

print(f"c = {c}")
print("blob = [")
for item in bundle(base):
    print(f"    {item},")
print("]")
print("data = [")
for i, row in enumerate(rows):
    print(f"    ({row ^ f(base, i)}, {pow(c, d ^ row, n)}),")
print("]")

其中：

  • $d$ 是 448 bits 的 RSA private exponent
  • $r_i$ 是 448 bits random row
  • 輸出的第一項是 $r_i \oplus f(\text{base}, i)$
  • 輸出的第二項是
    $$
    y_i \equiv c^{d \oplus r_i} \pmod n
    $$

如果可以知道 base，就可以算出所有 $f(\text{base}, i)$，進而還原所有 $r_i$。

第一步也是一種叫做 HSSP/AHSSP 的問題：
https://eprint.iacr.org/2020/461.pdf

Step 1: Recover base

先看 bundle(base)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def bundle(base):
    rows = [randbits(NBITS) for _ in range(NROWS)]
    cols = [[(row >> i) & 1 for row in rows] for i in range(NBITS)]
    out = []
    for _ in range(SETS):
        mod = getPrime(MODBITS)
        coeffs = [randbelow(mod) for _ in range(NBITS)]
        bias = [randbits(SMALL - 1) | (1 << (SMALL - 1)) for _ in range(NROWS)]
        vals = []
        for j in range(NROWS):
            total = -base * bias[j]
            for i in range(NBITS):
                total += coeffs[i] * cols[i][j]
            vals.append(total % mod)
        out.append((mod, bias, vals))
    return out

對每一個 set，有 72 個方程：

$$
v_j \equiv \sum_{i=0}^{31} a_i x_{i,j} - \text{base} \cdot b_j \pmod p
$$

其中：

  • $p$ 是 mod
  • $b_j$ 是 bias[j]
  • $v_j$ 是 vals[j]
  • $a_i$ 是未知的 coeffs[i]
  • $x_{i,j}$ 是第 $j$ 個 32-bit random row 的第 $i$ 個 bit

移項後：

$$
v_j + \text{base} \cdot b_j
\equiv
\sum_{i=0}^{31} a_i x_{i,j}
\pmod p
$$

右邊其實只落在一個由 32 個 column span 出來的低維線性空間裡。

如果我們找到一組係數 $\lambda_j$，使得：

$$
\sum_j \lambda_j x_{i,j} = 0
\quad
\text{for all } i = 0, 1, \dots, 31
$$

那麼把所有方程乘上 $\lambda_j$ 加起來，右邊會消失：

$$
\sum_j \lambda_j v_j
+
\text{base} \sum_j \lambda_j b_j
\equiv 0 \pmod p
$$

因此只要 $\sum_j \lambda_j b_j \not\equiv 0 \pmod p$，就可以推出：

$$
\text{base}
\equiv
-\frac{\sum_j \lambda_j v_j}{\sum_j \lambda_j b_j}
\pmod p
$$

這題有兩個 set，真正的 base 對兩邊都一樣，所以可以用兩個 modulus 算出來的結果交叉驗證。

Auxiliary lattice

實作上先對每個 set 建立模 $p$ 的 kernel：

$$
\sum_j \lambda_j v_j \equiv 0 \pmod p
$$

$$
\sum_j \lambda_j b_j \equiv 0 \pmod p
$$

也就是對矩陣：

$$
\begin{bmatrix}
v_0 & v_1 & \cdots & v_{71} \
b_0 & b_1 & \cdots & b_{71}
\end{bmatrix}
$$

找 kernel。

這個 kernel 裡會包含很多短向量，而真正有用的是來自於那些低維 bit column 結構的 relation。因為 72 個 samples 只由 32 個 bit columns 生成，所以理論上會有大約：

$$
72 - 32 - 1 = 39
$$

個短 relation。

把這些短 relation 找出來後，再取 right kernel，就可以回復出原本由 bit columns span 出來的 32 維 lattice。兩個 set 都做一次後，取交集，可以得到穩定的 auxiliary lattice。

最後對這個 lattice 再取 right kernel，就可以得到滿足：

$$
\sum_j \lambda_j x_{i,j} = 0
\quad
\forall i
$$

的 relation。

對這些 relation 逐一測試：

$$
\text{base}
\equiv
-\frac{\sum_j \lambda_j v_j}{\sum_j \lambda_j b_j}
\pmod p
$$

如果兩個 set 算出來的 base 一樣，就成功還原 base。

Step 2: Unmask all rows

題目輸出的 data 是：

1
(row ^ f(base, i), pow(c, d ^ row, n))

還原 base 後，就可以算：

1
row = masked ^ f(base, i)

因此我們現在有很多組：

$$
(r_i, y_i)
$$

其中：

$$
y_i \equiv c^{d \oplus r_i} \pmod n
$$

接下來的目標是利用這些資料把 $n$ 和 $m$ 找回來。

注意這題沒有直接輸出 $n$。

Step 3: Rewrite the faulty exponent

令：

$$
r_i = \sum_{k=0}^{447} r_{i,k} 2^k
$$

$$
d = \sum_{k=0}^{447} d_k 2^k
$$

則：

$$
d \oplus r_i=r_i + d - 2(d & r_i)
$$

如果展開成 bit：

$$
d \oplus r_i=r_i+\sum_{k=0}^{447} d_k (1 - 2r_{i,k})2^k
$$

現在考慮一組整數係數 $\alpha_i$，如果它滿足：

$$
\sum_i \alpha_i = 0
$$

以及對每個 bit position $k$ 都有：

$$
\sum_i \alpha_i r_{i,k} = 0
$$

那麼：

$$
\sum_i \alpha_i r_i = 0
$$

且：

$$
\sum_i \alpha_i(d & r_i) = 0
$$

所以：

$$\sum_i \alpha_i(d \oplus r_i)=\sum_i \alpha_i r_i+d \sum_i \alpha_i-2\sum_i \alpha_i(d & r_i)=0$$

因此：

$$\prod_i y_i^{\alpha_i}\equiv\prod_i c^{\alpha_i(d \oplus r_i)}\equiv c^0\equiv 1\pmod n$$

也就是：

$$\prod_{\alpha_i > 0} y_i^{\alpha_i}-\prod_{\alpha_i < 0} y_i^{-\alpha_i}\equiv 0 \pmod n$$

這個差值會是 $n$ 的倍數。

所以只要找到很多這種 relation，對所有差值取 gcd，就能把 $n$ 找回來。

Recover modulus $n$

要找 relation，就把每個 $r_i$ 寫成 bit vector，並且額外加上一個常數 1：

$$(r_{i,0}, r_{i,1}, \dots, r_{i,447}, 1)$$

找係數 $\alpha_i$，使得：

$$\sum_i \alpha_i(r_{i,0}, r_{i,1}, \dots, r_{i,447}, 1)=0$$

這可以用 lattice reduction 找短 relation。

對每個 relation，計算：

$$\Delta=\prod_{\alpha_i > 0} y_i^{\alpha_i}-\prod_{\alpha_i < 0} y_i^{-\alpha_i}$$

理論上：

$$
n \mid \Delta
$$

所以：

$$
n = \gcd(\Delta_1, \Delta_2, \dots)
$$

實作時 gcd 可能會帶一些小因數或雜訊，所以可以把小質數除掉，再用所有 $y_i$ 跟目前的候選 $n$ 做 gcd 清理。

Step 4: Recover plaintext

目前已知：

$$
y_i \equiv c^{d \oplus r_i} \pmod n
$$

而 RSA 裡：

$$
c^d \equiv m \pmod n
$$

所以如果我們可以湊出：

$$
\sum_i \alpha_i(d \oplus r_i) = d
$$

那麼：

$$
\prod_i y_i^{\alpha_i}
\equiv
c^d
\equiv
m
\pmod n
$$

不過直接湊出 $d$ 很難。可以先湊出 $t d$。

這次 relation 條件稍微放寬，只要求：

$$
\sum_i \alpha_i r_{i,k} = 0
\quad
\forall k
$$

但不要求：

$$
\sum_i \alpha_i = 0
$$

令：

$$
t = \sum_i \alpha_i
$$

則：

$$\sum_i \alpha_i(d \oplus r_i)=\sum_i \alpha_i r_i+d\sum_i \alpha_i-2\sum_i \alpha_i(d & r_i)$$

因為每個 bit 的 weighted sum 都是 0，所以：

$$
\sum_i \alpha_i r_i = 0
$$

且：

$$
\sum_i \alpha_i(d & r_i) = 0
$$

因此：

$$\sum_i \alpha_i(d \oplus r_i)=td$$

所以：

$$
\prod_i y_i^{\alpha_i}
\equiv
c^{td}
\equiv
(c^d)^t
\equiv
m^t
\pmod n
$$

我們可以用 lattice 找到很多組 relation，得到很多個：

$$
m^{t_1}, m^{t_2}, m^{t_3}, \dots
$$

如果這些 $t_i$ 的 gcd 是 1，也就是：

$$
\gcd(t_1, t_2, \dots, t_s) = 1
$$

那就可以用 extended gcd 找到整數 $\beta_i$，使得：

$$
\sum_i \beta_i t_i = 1
$$

於是：

$$
\prod_i (m^{t_i})^{\beta_i}
\equiv
m^{\sum_i \beta_i t_i}
\equiv
m
\pmod n
$$

這樣就可以直接還原 flag。

Flag 是 

1
AIS3{lll_then_lll_then_lll_then_lll_owob}

XDDD

EasyRSA

短短的程式碼 大大的鯨喜！ 

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *

flag = b'AIS3{TEST_ME}'

p = getPrime(512)
q = (p**2+1)
r = getPrime(2048)
e = 677676677
N = p*q*r
c = pow(bytes_to_long(flag), e, N)

print(f"{e=}\n{c=}\n{N*getPrime(512)=}")

首先最後的 N*getPrime(512) 根本不用管，假設我們能分解出 $p$，我們可以先想辦法用 $mod \space p*q$ 的量（或他的某個因數）去嘗試解密 flag，理論上 flag 通常不那麼長。
開胃小菜想完了，現在是主角。

我們考慮 $\mathbb{F}_p$ 下的多項式環，假設今天上面有個不可約多項式 $f_1(x)=ax^4+bx^3+cx^2+dx+e$
我們來考慮 $\mathbb{F}_p[x] / \langle f_1(x) \rangle$，我們知道它的 order 會是 $p^4-1$
注意到 $p^4-1=(p^2+1)(p^2-1)$，剛剛是不是哪裡有個 $p^2+1$？沒錯，就是我們 $N$ 裡面因數的 $q$
再來我們考慮某個 $\mathbb{F}_p[x] / \langle f_1(x) \rangle$ 上的三次多項式 $g_1(x)$，取 $g_1(x)^N = g_2(x)^{p^2+1}$ 會得到某個 order 剩下 $p^2-1$ 的生成元 $g_3(x)=g_2(x)^{p^2+1}$。
$p^2-1$ 代表的是某個二次多項式形成的多項式環的 order，也就是說在 $\mathbb{F}_p$ 下這個多項式的2, 3 次項退化成 0 了。
等等，那假設我們考慮 $\mathbb{Z}[x] / \langle f_1(x) \rangle$ 呢？
隨機挑選多項是 $f_1, g_1$ 一直做這些操作，再取計算後的生成元 $g_3$ 的 2, 3 次項，它很可能會跟 $N$ 產生最大公因數 $p$ (因為本來在 mod $p$ 的時候變成 $0$了)。

Solved!
Exploit 一樣看 GitHub XDD

P.S. 中間 Threads 上還有選手互動的 part xDD
image

After all

TL;DR 一下為什麼這次 Crypto 整個領域除了我還是我出的 :)
image

上次出 Pre Exam / EOF 都沒寫完整 writeup，一方面是沒空（現在其實更忙），另一方面是後面在討論區其實都跟大家聊的差不多了（？
怎麼說呢，但這次情況特殊好像值得寫一篇文章紀念一下 XDDDD
情況特殊不單單是指整場的密碼學被一個人包下，也想順手紀錄下這次的對抗 LLM 之旅

如大家所知，比賽的題目分數會在 100~500 分間隨解題人數即時動態調整…？！
image

P.S. 先附上其他領域的分數分布做個對照組，理想中我以為分數線會長得像 pwn 那樣，看起來大家真的都不喜歡動腦解 Crypto >:(
或者說動腦解 CTF？

image

其實在這次 Pre Exam 當完 Staff + 周末打完 DEFCON CTF Qual 後深深感覺到 CTF 應該要有所改變了（或者說慢慢在改變？