從題目中就可以知道這是一提 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

1def sign(msg: bytes):
2    h = int.from_bytes(hashlib.sha1(msg).digest(), 'big') % order
3    k = lcg.next()
4    R = k * curve.generator
5    r = R.x() % order
6    s = (pow(k, -1, order) * (h + r * sk.privkey.secret_multiplier)) % order
7    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# NIST P-192
2'''
3order = 6277101735386680763835789423207666416102355444465032267104602349
4x = 0x188da80ebb30e5a3191d00c1f7ff60c93db7a6c14f50b75b2decb24e7b7c20e9
5y = 0x0712e4af1c2a8e2a52f72a6f9d9c7b7b7550b46cd0f3c9147e39a818c6f5b6b6
6info from https://neuromancer.sk/std/nist/P-192
7'''
8
9a = 1103515245
10c = 12345
11n = order
12h = int.from_bytes(hashlib.sha1("get_example").digest(), 'big') % n
13
14d = (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

既然私鑰有了我們就可以自由加密訊息了，剩下的部分就是要計算出第三次 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 了

• 題目檔案
• 解題程式碼
• Code:568624320198069:1382946124044753

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

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 開根號就不會是整數也就不會是正確的

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

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

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

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

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

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

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

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

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

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

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

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

最後在

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

就有答案了

• 題目檔案
• 解題程式碼
• Code:7277901827578088:3277133792625161

題目有給 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 了

• 題目檔案
• 解題程式碼
• Code:6178118987585758:8296645964105477

所以我們一開始看題目就可以看到兩個矩陣 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

1rand_iter = (33 + (i * 97) % 90 for i in itertools.count())

接下來我們知道發送出去的數值會依照計算

1c = (A @ blocks[i]) % p
2c = (A @ blocks[i] + B @ blocks[i-1]) % p

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

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

最後就可以得到 flag

• 題目檔案
• 解題程式碼
• Code:6014825458540502:1359881923246279