思路·

先讲一下当时做题的思路，首先是对题目的解析：

代码的36行可以看出flag可以由数组t得来，所以最终目标是恢复t；
由26-29行矩阵 $C$ 的构造可以看出， $C$ 里面包含了t，所以也可以看作是求矩阵 $C$ 。再观察一下，其实 $C$ 是某个（monic的）多项式的伴随矩阵，而t是这个多项式对应的系数的模 $N$ 取负，所以问题也可以转化为求这个多项式。令这个多项式为 $f$ ，根据伴随矩阵的特性， $f$ 的 $m$ 个解和 $C$ 的 $m$ 个特征值对应相等，所以问题又可以转化为求 $C$ 的特征值；

然后先逆一下Reflector(x, inv=False)函数，逻辑很简单，就是根据输入的inv返回 $Fx$ 或 $F^{-1}x$ ， $F$ 是个随机可逆矩阵；
Rotor(x)的逻辑会更复杂一些，从结果来说里面的for循环是在做 $C^mx$ ，其实就是上面wiki截图在做的事（PS：题目代码里跟wiki的 $C$ 构造刚好互为转置，所以这里和上图有点区别），所以最终返回的是 $G^{\frac{N*(N-1)}{3}}C^mx$ ；
综合上面两点可得出加密其实是在做： $c_i = (F^{-1}G^{\frac{N*(N-1)}{3}}C^mF)*v_i$ ；
再来看一下矩阵 $G$ 的特性，代码的31-33行说了 $G$ 的特征值是在 $GF(N)$ 中的，根据之前一些对GL(m, N)的研究， $G$ 的群阶就是 $N*(N-1)$ ，甚至如果 $G$ 的特征值各不相等的话还会是 $N-1$ （盲猜出题人没造出特征值各不相等且在 $GF(N)$ 中的 $G$ ，逃。所以34行的G_ = G ** (N * (N-1)//3)就暗示了后面应该会有某一步需要做 ${G\_}^3$ 然后消去G_；
最后就是30行的 $G$ 和 $C$ 乘法运算可交换，原以为这里可以暴露 $G$ 的一些属性，后来才发现是跟上一点有关的，举个栗子即， $(GC)^2=GC*GC=GG*CC=G^2C^2$ ，这种幂次的运算需要有交换律才能完成。

上面这些是从代码上可以看出来的，下面还有一些摁猜+多次尝试得出的：

首先根据Rotor和Reflector这个函数名，加上题目说的“古典密码”，加上搜索一下，可以盲猜这是在做Enigma类似的东西（后来给的hint 1也暗示了）。又大概搜了一下Enigma的分析和破解方法，发现有雷耶夫斯基（Marian Adam Rejewski）的一种找循环圈的方法，盲猜这题也可以用类似的方法破（hint 2也说了要分析密文），所以遍历了一下明文和密文，看看会不会有密文存在明文中；
从上一点的操作上还真可以找到多对明密文对应的向量，还有一个循环圈：
1
[7, 39, 34, 39] -> [37, 28, 20, 28] -> [42, 19, 32, 19] -> [7, 39, 34, 39]
因为循环的次数刚好是3，所以盲猜 $C$ 的阶是 $3m$ ，但后来发现这是错的（其实是没构造出来阶是 $3m$ 的Jordan Form，挖个坑看看以后能不能继续构造或者证伪，逃）；
再次观察上面的循环圈，发现前一个向量的每一个值乘上 $36$ 模 $N=43$ 刚好就是后一个向量对应的值（可以实验一下这里的“每一个”肯定不是巧合），前面说过加密其实是一次矩阵乘向量，那这个循环圈中的矩阵乘就可以转化成数乘了？根据线性代数教的知识，如果这个向量是特征向量，这个 $36$ 是对应的特征值的话，刚好可以这样做（指变数乘）。另外说一下，这里的循环圈循环次数为 $3$ 是因为， $36$ 在 $GF(43)$ 中的阶为 $3$ ，即 $36^3 \equiv 1 \pmod {43}$ ；

要验证上一点的猜想其实不难，在上上点中已经找到多组明密文对应的向量，只要验证每组是不是都可以转化成数乘就好了，结果是。都可以转化为数乘，而且这个“数”去重后刚好是 $9$ 个（且不同的）。再检验一下还可以发现这多组的明密文对应的向量中，去重后向量的个数刚好是 $27$ ，即刚好是出题人构造好的vectors的数量；
到这，如果猜想没错的话（最后证明其实是没错的），已经可以算出 $9$ 个特征值了（不妨先记为 $\lambda'_i$ ），但要注意算出来的特征值是 $(G^{\frac{N*(N-1)}{3}}C^m)$ 的特征值（因为上面说了加密是 $c_i = (F^{-1}G^{\frac{N*(N-1)}{3}}C^mF)*v_i$ ，相似矩阵特征值一样），而要算t的话需要的是 $C$ 的特征值，所以还需要转一下；
首先做个三次方的话可以轻易消去 $G$ 那部分，因为 $G$ 的阶是 $N(N-1)$ ：

$(F^{-1}G^{\frac{N*(N-1)}{3}}C^mF)^3 \equiv F^{-1}C^{3m}F \pmod N$

即 $(\lambda'_i)^3 \pmod N$ 是 $C^{3m}$ 的特征值。那么 $C$ 的特征值就是 $\lambda_i=(\lambda'_i)^{\frac{3}{3m}} \equiv (\lambda'_i)^{\frac{1}{m}} \pmod N$ ，现在 $m=9$ 、 $N=43$ 、 $\varphi(N)=42=3*14$ ，即 $gcd(m, \varphi(N))=3$ 不能直接对 $m$ 求逆，可以AMM爆，但是 $N=43$ 太小了，直接枚举也可以（题目给了hash，应该也暗示了要枚举）；
最后根据特征值构造多项式 $f$ （上面说了， $C$ 的特征值是 $f$ 的根），然后用 $f$ 的系数恢复t，最后得到flag。

题解·

按照上面的思路，解的步骤就是：

找到明密文对中，可以把矩阵乘向量转化成数乘向量的对，把这些数解出来即大概率是 $(G^{\frac{N*(N-1)}{3}}C^m)$ 的特征值（实际exp中用的是找循环圈的向量，上面也说了数量刚好是 $27$ ，疑似是出题人给的vectors，而且刚好解出来 $9$ 个特征值）；
根据 $(G^{\frac{N*(N-1)}{3}}C^m)$ 的特征值接触 $C$ 特征值的可能值，实际每个特征值会有 $3$ 种可能性，一共有 $9$ 个特征值，即一共 $3^9=19683$ 种可能，可以爆破；
爆破的时候,先构造 $f=\prod_{i=0}^8 (x-\lambda_i)$ ，记 $f=c_0 + c_1x+...+c_8x^8+x^9$ ，则 $t_i \equiv -c_i \pmod N$ ，这里的 $t_i$ 即t[i]，然后构造flag，对比sha1值是否相等。

参考Exp：

# sage

# input
N = 43
m = 9
plain = [[30, 0, 41, 24], [37, 6, 8, 20], [12, 19, 24, 31], [33, 10, 42, 19], [22, 26, 40, 38], [32, 20, 35, 20], [31, 3, 39, 20], [26, 6, 0, 26], [25, 21, 32, 28], [9, 33, 37, 26], [13, 19, 20, 28], [34, 5, 12, 37], [11, 22, 18, 35], [37, 1, 2, 15], [33, 14, 15, 28], [7, 39, 34, 39], [8, 12, 1, 29], [18, 27, 9, 30], [7, 5, 1, 41], [31, 7, 28, 20], [33, 36, 8, 16], [23, 15, 15, 2], [41, 2, 29, 17], [1, 9, 22, 19], [14, 8, 15, 13], [37, 23, 34, 34], [16, 29, 37, 25], [39, 9, 24, 27], [20, 41, 18, 14], [6, 8, 30, 6], [16, 36, 38, 1], [40, 24, 40, 9], [13, 23, 41, 11], [5, 8, 19, 17], [30, 31, 4, 6], [4, 11, 23, 40], [37, 27, 18, 20], [41, 18, 7, 25], [17, 18, 25, 11], [25, 28, 41, 37], [33, 23, 0, 23], [20, 26, 10, 35], [20, 20, 28, 22], [31, 23, 32, 20], [2, 37, 13, 40], [26, 1, 37, 27], [7, 35, 9, 38], [30, 15, 41, 18], [25, 11, 31, 19], [35, 35, 33, 29], [33, 34, 35, 41], [3, 14, 16, 38], [42, 19, 32, 19], [6, 8, 42, 20], [8, 8, 10, 3], [33, 10, 22, 34], [10, 4, 1, 21], [39, 15, 24, 27], [38, 24, 22, 20], [2, 21, 32, 39], [14, 14, 11, 24], [18, 16, 29, 41], [28, 6, 19, 37], [3, 12, 6, 35], [25, 40, 6, 39], [5, 22, 40, 42], [39, 24, 5, 31], [14, 37, 5, 7], [36, 9, 31, 5], [28, 9, 8, 6], [36, 12, 32, 36], [28, 37, 16, 29], [20, 39, 42, 3], [15, 36, 38, 20], [12, 31, 27, 3], [27, 14, 33, 28], [26, 19, 8, 23], [6, 17, 17, 17], [2, 42, 0, 3], [0, 4, 8, 23], [12, 5, 33, 38], [23, 38, 30, 24], [1, 42, 15, 23], [17, 37, 27, 25], [24, 12, 18, 33], [20, 20, 26, 41], [36, 13, 23, 42], [39, 18, 25, 41], [11, 29, 17, 14], [3, 4, 25, 12], [0, 12, 4, 0], [27, 40, 37, 10], [30, 7, 13, 29], [16, 26, 36, 23], [31, 19, 10, 12], [4, 13, 10, 38], [14, 11, 19, 7], [37, 40, 9, 5], [1, 7, 30, 17], [37, 28, 20, 28], [35, 28, 34, 23], [7, 18, 33, 24], [21, 17, 15, 14], [29, 35, 15, 41], [30, 16, 13, 26], [39, 22, 34, 30], [5, 31, 22, 2], [41, 38, 37, 12], [40, 23, 19, 39], [28, 5, 27, 5], [20, 34, 22, 31], [3, 34, 6, 31], [42, 20, 13, 19], [24, 18, 23, 1], [27, 10, 20, 38], [22, 40, 37, 23], [17, 31, 5, 14], [7, 8, 16, 4], [14, 38, 5, 14], [41, 1, 13, 8], [6, 16, 35, 9], [26, 27, 13, 29], [30, 8, 14, 8], [36, 4, 35, 0], [41, 35, 19, 24], [31, 39, 20, 15], [27, 40, 21, 22], [22, 11, 10, 39], [14, 25, 24, 33], [0, 4, 7, 6], [35, 41, 41, 28], [27, 27, 12, 34], [10, 17, 11, 40], [38, 1, 36, 38], [25, 37, 14, 41]]
cipher = [[11, 26, 12, 12], [33, 10, 42, 19], [9, 40, 31, 36], [12, 31, 27, 3], [36, 2, 19, 11], [27, 10, 30, 26], [25, 12, 9, 42], [6, 40, 18, 8], [14, 13, 26, 7], [36, 3, 19, 18], [9, 33, 37, 26], [10, 4, 1, 21], [18, 26, 6, 24], [7, 14, 36, 38], [16, 10, 28, 17], [37, 28, 20, 28], [39, 15, 8, 35], [6, 0, 42, 28], [26, 39, 12, 7], [41, 21, 6, 31], [28, 34, 25, 21], [35, 33, 34, 39], [24, 6, 26, 7], [24, 14, 33, 16], [4, 41, 7, 3], [31, 41, 5, 32], [34, 33, 32, 17], [6, 8, 7, 24], [38, 8, 2, 15], [14, 25, 37, 22], [18, 18, 27, 15], [19, 8, 4, 7], [16, 3, 0, 22], [27, 6, 24, 3], [31, 40, 15, 23], [6, 22, 23, 41], [12, 40, 40, 40], [11, 7, 6, 42], [24, 29, 16, 26], [35, 4, 32, 20], [8, 31, 32, 26], [5, 0, 19, 29], [4, 4, 40, 13], [4, 24, 28, 41], [31, 20, 1, 1], [36, 1, 1, 29], [9, 36, 29, 7], [22, 11, 10, 39], [13, 20, 35, 37], [35, 37, 39, 17], [40, 11, 38, 6], [15, 13, 32, 41], [7, 39, 34, 39], [30, 0, 3, 16], [11, 18, 40, 30], [23, 29, 38, 2], [8, 29, 18, 34], [39, 5, 37, 39], [26, 11, 38, 26], [9, 3, 6, 33], [20, 20, 28, 22], [35, 14, 6, 40], [42, 24, 27, 24], [29, 7, 42, 10], [20, 30, 26, 42], [9, 31, 38, 38], [42, 6, 12, 40], [13, 19, 20, 28], [14, 25, 24, 33], [13, 19, 42, 18], [42, 30, 17, 3], [16, 0, 20, 1], [37, 42, 22, 26], [13, 14, 10, 3], [20, 23, 2, 5], [28, 34, 29, 28], [36, 8, 0, 7], [17, 30, 4, 13], [24, 6, 21, 23], [13, 24, 42, 33], [40, 5, 39, 26], [18, 29, 4, 33], [34, 8, 30, 30], [39, 9, 24, 27], [3, 35, 25, 40], [12, 18, 24, 26], [40, 38, 29, 33], [1, 28, 34, 7], [16, 21, 22, 34], [17, 37, 27, 25], [21, 35, 11, 25], [19, 29, 27, 18], [7, 24, 34, 7], [6, 5, 22, 33], [19, 24, 30, 20], [39, 23, 38, 27], [31, 39, 35, 17], [30, 15, 41, 18], [27, 8, 42, 22], [42, 19, 32, 19], [32, 0, 7, 4], [22, 37, 42, 41], [34, 5, 12, 37], [16, 11, 37, 11], [24, 21, 15, 15], [10, 37, 22, 33], [4, 11, 30, 13], [19, 19, 1, 27], [13, 12, 21, 11], [11, 24, 31, 21], [12, 4, 35, 23], [26, 41, 10, 25], [38, 32, 5, 4], [42, 28, 23, 23], [39, 24, 5, 31], [27, 10, 20, 38], [14, 15, 12, 28], [18, 17, 9, 18], [6, 41, 42, 13], [29, 10, 38, 13], [0, 11, 29, 35], [42, 12, 38, 18], [14, 0, 17, 24], [29, 27, 41, 2], [40, 15, 15, 18], [0, 5, 12, 0], [16, 37, 10, 20], [19, 31, 36, 20], [15, 36, 38, 20], [10, 35, 30, 40], [20, 18, 33, 1], [14, 14, 11, 24], [9, 37, 6, 25], [33, 37, 17, 34], [2, 11, 16, 6]]
hash = 'fd1f241a4d3ff9fc25d1e2480baa8b0c3b5a4559'

# find circles (in fact eigenvectors ...)
tmp = []
pc = list(zip(plain, cipher))
for pci in pc:
  for pcj in pc:
    if pci[1] == pcj[0]:
      tmp.append(pci)
#print(tmp)
#for t in sorted(tmp):
#  print(t)

circles = []
for tt in tmp:
  circle = [tt]
  for _ in range(len(tmp)):
    c = circle[-1]
    for t in tmp:
      if c[1] == t[0]:
        if t in circle:
          break
        circle.append(t)
  circles.append(circle)
# maybe these are vectors ...
assert len(list(set([str(x) for x in flatten(circles, max_level=2)]))) == 27

def to_str(vz):
  res = ''
  for vi in vz[:-1]:
    res += str(vi[0])
    res += '  ->  '
  res += str(vz[-1][0])
  res += '  ->  '
  res += str(vz[-1][1])
  return res

for c in circles:
  print(to_str(c))
print()

# get lambdas of G_*C^m
def getLambda(a, b):
  return Integer(a).inverse_mod(43) * b % 43

lambdas = []
for c in circles:
  for i in range(4):
    lambdas.append(getLambda(c[0][0][i], c[0][1][i]))
lambdas = sorted(list(set(lambdas)))
assert len(lambdas) == 9
print(lambdas)

# get possible lambdas of C
lambdas2 = []
for l in lambdas:
  tmp = []
  for i in range(1, 43):
    if pow(i, 3*m, 43) == pow(l, 3, 43):
      tmp.append(i)
  lambdas2.append(tmp)
  print(tmp)
print()

# enumerate for real lambdas
from hashlib import sha1
import itertools

F.<a> = GF(43)
R.<x> = PolynomialRing(F)
flags = 'MRCTF{%s}'

for lams in itertools.product(*lambdas2):
  f = R(1)
  for l in lams:
    f *= R(x-l)
  #print(f)
  t = list(f)
  t = [-ti % 43 for ti in t[:-1]]
  #print(t)

  flag = flags % sha1(str(t).encode()).hexdigest()
  #print(hash)
  #print(sha1(flag.encode()).hexdigest())
  if sha1(flag.encode()).hexdigest() == hash:
    print(flag)  
    break