# 神盾盃 AEGIS 2025 Writeup

## Result
with Bun, GraspingStew631, ash/, lywslc, ffting, SD

我在賽中解了 random multi 和 M-rsa 這兩題
## Crypto
### random multi
flag 的值會乘上 7691640804 次隨機選 pool 裡面的值 mod p 之後輸出
觀察發現 pool 裡面的值都是 11 的次方且只有 11^0 ~ 11^9，然後因為相乘就是次方相加，所以可以用期望值來算出乘 7691640804 次大概會是乘以 11 的幾次方
然後算出是多少次方之後再往兩側延伸一個 window = 200000，畢竟有隨機性不會一定和期望值相同
然後就是取 inverse 那些的了，逆回去算出 flag
（不用每次重算 inverse 的酷酷算法是 ChatGPT 教我的）
要注意的大概就是 window 不能太小，一開始開太小以為寫錯

import math
from Crypto.Util.number import *
from sympy import prime
from tqdm import trange
import random

# Given values
p = 10270690747750681275848519156345460292282442776941950362299330027993038338823977542405725333740052688659124663537769686180834450426957439995949108234020121
c = 6211227177504225821131033803784639291621321097309823976872498717139250997486591939973272963659554090619408357034740836341244321284116105064793564676501364

n = 7691640804
pool = [11, 11, 2357947691, 19487171, 1, 1, 1, 1, 2357947691, 14641, 14641, 14641, 11, 14641, 214358881, 214358881, 14641, 1, 1771561, 14641, 214358881, 19487171, 11, 214358881, 14641, 121, 11, 14641, 161051, 161051, 1331, 161051, 11, 14641, 19487171, 214358881, 19487171, 121, 19487171, 1, 1331, 161051, 19487171, 19487171, 161051, 161051, 2357947691, 2357947691, 11, 1331, 14641, 11, 11, 19487171, 161051]

# 1. Calculate the total exponent of 11
# The pool contains powers of 11. Let's map each number to its exponent.
exponents = [round(math.log(x, 11)) for x in pool]

# print(exponents)

# Calculate the average exponent from the pool
total_sum_of_exponents = sum(exponents)
total_pool_size = len(exponents)
average_exponent = total_sum_of_exponents / total_pool_size

# The total exponent E is the number of iterations (n) times the average exponent
# Using integer rounding is a good guess for a discrete distribution
# average_exponent = 185/41
E = int(round(n * average_exponent))
print(f"Total exponent E: {E}")

window = 2000000
base = 11 % p
a = pow(base, E - window, p)        # 先算起點
inv_base = inverse(base, p)         # 11 的逆元
inv_a = inverse(a, p)               # a 的逆元

for i in range(2*window+1):
    decrypted_long = (c * inv_a) % p
    decrypted_flag = long_to_bytes(decrypted_long)
    if decrypted_flag.startswith(b"AEGIS"):
        print(f"Decrypted Flag: {decrypted_flag}")

    a = (a * base) % p              # 11^(e+1)
    inv_a = (inv_a * inv_base) % p  # 對應的逆元


### M-rsa
總之是矩陣版的 Hastad's Broadcast Attack，可以取得一次 a 和很多次 (n, c)
~~以下是把解法跟 ChatGPT 講請它幫我寫的 code~~

from pwn import remote
from Crypto.Util.number import long_to_bytes
from sympy import Symbol, Matrix, Poly, nroots
import ast
from math import prod
from sympy import Integer
import gmpy2

HOST = "0.cloud.chals.io"
PORT = 15520
ROUNDS = 40    # 可以調整，確保 product(n) 足夠大覆蓋矩陣條目大小
E = 19

def chinese_remainder(pairs):
    N = prod([n for n, _ in pairs])
    total = 0
    for n, c in pairs:
        m = N // n
        inv = int(gmpy2.invert(m, n))
        total += int(c) * inv * m
    return total % N, N

def crt_matrix_entries(pairs_list):
    # pairs_list: list of length 9, 每個元素是 [(n1,c11),(n2,c12),...]
    B = [[0]*3 for _ in range(3)]
    for idx, pairs in enumerate(pairs_list):
        val, N = chinese_remainder(pairs)
        i = idx // 3
        j = idx % 3
        B[i][j] = Integer(val)
    return Matrix(B)

def parse_initial_a(conn):
    # 伺服器在開始會有一行像 [p0, p1, ...] 被 print
    # 我們讀到那行並解析
    line = conn.recvline(timeout=5).decode().strip()
    # line 可能包含其他文字，嘗試從 line 找到 first '['...']'
    if '[' in line and ']' in line:
        arr_s = line[line.find('['):line.rfind(']')+1]
        a_list = ast.literal_eval(arr_s)
        return a_list
    else:
        # 若沒在單行讀到，嘗試再多讀幾行拼湊
        accum = line
        for _ in range(5):
            more = conn.recvline(timeout=1).decode()
            accum += more
            if '[' in accum and ']' in accum:
                arr_s = accum[accum.find('['):accum.rfind(']')+1]
                return ast.literal_eval(arr_s)
    raise RuntimeError("Failed to parse initial a list from server output")

def main():
    conn = remote(HOST, PORT)
    # **先讀並解析伺服器印出的 a 列表（很重要）**
    a_list = parse_initial_a(conn)
    print("[+] parsed a_list:", a_list)

    # 為矩陣 9 個位置準備 CRT pairs storage
    pairs_list = [[] for _ in range(9)]

    for r in range(ROUNDS):
        conn.recvuntil(b"(y):")
        conn.sendline(b"y")
        n_line = conn.recvline().strip()
        c_line = conn.recvline().strip()

        n = int(n_line.decode())
        # c_line 形如 Python 的 matrix literal (伺服器 print 出來)
        c_mat = ast.literal_eval(c_line.decode())

        # 把 3x3 的每個 entry 加到對應的 pairs list
        for i in range(3):
            for j in range(3):
                pairs_list[i*3 + j].append((n, int(c_mat[i][j])))

        print(f"[{r+1}/{ROUNDS}] got n (digits={len(str(n))}) and c matrix")

    print("[+] Running CRT for each entry...")
    B = crt_matrix_entries(pairs_list)
    print("[+] Reconstructed integer matrix B = A^e (entries may be huge).")

    # 構造符號矩陣 A_sym：把 a_list 放入已知位置，中心用符號 m
    m = Symbol('m')
    A_sym = Matrix([
        [Integer(a_list[0]), Integer(a_list[1]), Integer(a_list[2])],
        [Integer(a_list[3]), m,                Integer(a_list[4])],
        [Integer(a_list[5]), Integer(a_list[6]), Integer(a_list[7])]
    ])

    print("[+] Building A_sym**E ... this may take some time but is doable for 3x3")
    A_pow = A_sym**E  # Sympy matrix power -> entries are polynomials in m

    # 選擇某個 entry（通常 [1,1]）建立多項式方程： Poly(A_pow[1,1] - B[1,1], m)
    expr = A_pow[1,1] - B[1,1]
    poly = Poly(expr, m)
    print("[+] Polynomial degree:", poly.degree())

    # 用數值根尋找可能整根（這一步找複數根並嘗試取整數近似）
    from sympy import real_roots
    roots = real_roots(poly)
    for r in roots:
        if r.is_integer:
            m_val = int(r)
            if poly.eval(m_val) == 0:
                print("Found integer root:", m_val)
                flag = long_to_bytes(m_val)
                print(flag)

if __name__ == "__main__":
    main()


## Misc
### cipherRestaurant
:::info
賽後解出
:::
有一個 exe，跑起來會隨機丟出一張 [A-Z].jpg
寫個腳本跑很多次把 A-Z 收集完
（binwalk 也可以拿到但檔名會亂掉就沒有用了；因為是 python 打包成的執行檔所以如果用 [PyInstaller Extractor](https://github.com/extremecoders-re/pyinstxtractor) 復原的話也可以，但沒必要那麼麻煩

# script.ps1
$executionCount = 100

for ($i = 1; $i -le $executionCount; $i++) {
    Write-Host "$i"
    .\\cipherRestaurant.exe
}


可以看到大部分都是食材，V~Y 是人
丟到 https://futureboy.us/stegano/decinput.html 這個網站可以看到 V, W, X 裡面有隱寫提示內容

V: The chef loves prime numbers, and he will use them as ingredient codes.
W: I want to eat the food that the chef made, but he gave me gold coins and asked me to buy the ingredients on the list. The list only says "PRIME". What are these ingredients?
X: I am Legendary Utensil, and I can transform ingredients into dishes.

然後有人通靈出 X.jpg 這張指的是 [OpenPuff](https://embeddedsw.net/OpenPuff_Steganography_Home.html) 這個隱寫工具
但要 unhide 東西需要 password 以及選到正確的 carrier（正確的圖片）

然後也有隊友 strings 出來其他圖片裡面都有寫一個質數

A,2
B,3
C,5
D,7
E,11
F,17
G,17
H,19
I,23
J,29
K,31
L,37
M,41
N,43
O,47
P,53
Q,59
R,61
S,67
T,71
U,73
V,(empty)
W,(empty)
X,(empty)
Y,96
Z,101

然後就是通靈時間，要通靈出 password 和 carrier 是誰
:::info
接下來就是賽後的部分
:::
總之最後密碼是 PRIME 5 個英文單字對應的質數相乘（53\*61\*23\*41\*11 = 33535909），然後 carrier 是 Y.jpg 那張廚師的照片
然後這樣就成功解出來了。

（賽中有試到把質數乘起來，但 carrier 只試了 V, W, X, A，隊友有試 Z，可惡！！！）