# Google CTF 2025 writeup
這次和星爆牛炒竹狐一起打，只寫出一題密碼學
## FILTERMAZE
這提示一個 LWE 問題，具體來說描述是這樣：
$A$ 是一個 $n\times m$ 的矩陣，$b$ 和 $e$ 是長度為 $n$ 的向量，$s$ 是長度為 $m$ 的向量，滿足 $b=(As+e)\mod{q}$

首先，他有給的資訊是 $A$、$b$、$q$，想要獲得的是 $s$，並且我們可以用一些方式得到一些有關 $e$ 的資訊。

class PathChecker:
  def __init__(
    self,
    secret_path,
    graph_data,
    lwe_error_mags,
  ):
    self.secret_path = secret_path
    self.graph = graph_data
    self.lwe_error_mags = lwe_error_mags
    self.path_len = len(self.secret_path)

  def check(self, candidate_segment):
    seg_len = len(candidate_segment)
    if seg_len > self.path_len:
      return False
    for i, node in enumerate(candidate_segment):
      if node != self.secret_path[i]:  # Node mismatch
        return False

      if i > 0:
        prev_node = candidate_segment[i - 1]
        neighbors = self.graph.get(prev_node)
        if neighbors is None or node not in neighbors:
          return False

    if seg_len == self.path_len:
      error_magnitudes = [int(abs(err_val)) for err_val in self.lwe_error_mags]
      return error_magnitudes
    else:
      return True

這個類別的 `check` 函式會檢查我們輸入的路徑前綴是否符合答案，並且會告訴我們答案，當我們完全的把路徑猜出來後就會給我們 $e$ 的絕對值（向量中所有數字都取絕對值）。而因為他是檢查前綴，所以可以直接枚舉，於是我們獲得 $e$ 的絕對值了。

但是有 $e$ 的絕對值有什麼用呢？觀察一下以下這件事：
$$
\left[
\begin{array}{ccc}
e_1 \\
e_2 \\
... \\
e_n
\end{array}
\right] \\
= \left[
\begin{array}{ccc}
|e_1| & 0 & ... & 0\\
0 & |e_2| & ... & 0\\
... & ...& ... & ...\\
0 & 0 & ... & |e_n|\\
\end{array}
\right]
\left[
\begin{array}{ccc}
(-1)^{x_1} \\
(-1)^{x_2} \\
... \\
(-1)^{x_n}
\end{array}
\right]
$$
照上面這個關係，我方便起見寫成下面這種形式：$e=E_{abs}X$
於是我們可以把 LWE 問題通過同乘 $E_{abs}^{-1}$ 變成以下形式：
$$E_{abs}^{-1}b=(E_{abs}^{-1}As+X)\mod{q}$$
注意到 $X$ 的係數都是 $1$ 或 $-1$，這就是一個經典的 LWE 問題了，直接當腳本小子去解它，然後就解出 $s$ 了：

# https://github.com/maple3142/lll_cvp
import json
from sage.all import *
from lll_cvp import *
e_abs = [265, 622, 38, 716, 722, 308, 996, 799, 742, 337, 927, 698, 626, 969, 330, 126, 321, 20, 271, 839, 175, 399, 752, 989, 666, 629, 271, 400, 311, 840, 821, 821, 17, 978, 488, 781, 74, 818, 849, 903, 776, 142, 505, 951, 582, 638, 222, 872, 427, 165, 307, 209, 475, 970, 748, 814, 69, 213, 27, 742, 744, 566, 262, 852, 740, 309, 997, 502, 995, 434, 405, 193, 257, 953, 924, 678, 232, 226, 560, 414, 584, 579, 767, 810, 51, 894, 446, 281, 761, 908, 715, 787, 722, 270, 94, 169, 474, 431, 292, 346]

with open("lwe_pub_params.json", "r") as f:
    data = json.loads(f.read())

# print(data)

n = 50
m = 100
q = 1009
A = data["A"]
b = data["b"]

b = [b[i] * pow(e_abs[i], -1, q) % q for i in range(m)]
A = [[A[i][j] * pow(e_abs[i], -1, q) % q for j in range(n)] for i in range(m)]

A = matrix(GF(q), A)
b = vector(GF(q), b)
ATR = reduce_mod_p(A.T, q, reduction=lambda x: x)
s_rec = A.solve_right(kannan_cvp(ATR, b))
print(s_rec)