看似古典Enigma Machine,实则大一线性代数(x). 有幸全场唯一解(★,°:.☆( ̄▽ ̄)/$:.°★

题目整体难度其实不大,就是需要一些现代和群论(特别GL群)的前置知识,还有要做一些猜测(secret里面放的东西太多了- -

题目源码:https://paste.ubuntu.com/p/v2ZGYZTnjn/

思路

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

  • 代码的36行可以看出flag可以由数组t得来,所以最终目标是恢复t
  • 26-29行矩阵CC的构造可以看出,CC里面包含了t,所以也可以看作是求矩阵CC。再观察一下,其实CC是某个(monic的)多项式的伴随矩阵,而t是这个多项式对应的系数的模NN取负,所以问题也可以转化为求这个多项式。令这个多项式为ff,根据伴随矩阵的特性,ffmm个解和CCmm个特征值对应相等,所以问题又可以转化为求CC的特征值;
  • 然后先逆一下Reflector(x, inv=False)函数,逻辑很简单,就是根据输入的inv返回FxFxF1xF^{-1}xFF是个随机可逆矩阵;

  • Rotor(x)的逻辑会更复杂一些,从结果来说里面的for循环是在做CmxC^mx,其实就是上面wiki截图在做的事(PS:题目代码里跟wiki的CC构造刚好互为转置,所以这里和上图有点区别),所以最终返回的是GN(N1)3CmxG^{\frac{N*(N-1)}{3}}C^mx

  • 综合上面两点可得出加密其实是在做:ci=(F1GN(N1)3CmF)vic_i = (F^{-1}G^{\frac{N*(N-1)}{3}}C^mF)*v_i

  • 再来看一下矩阵GG的特性,代码的31-33行说了GG的特征值是在GF(N)GF(N)中的,根据之前一些对GL(m, N)的研究GG的群阶就是N(N1)N*(N-1),甚至如果GG的特征值各不相等的话还会是N1N-1(盲猜出题人没造出特征值各不相等且在GF(N)GF(N)中的GG,逃。所以34行的G_ = G ** (N * (N-1)//3)就暗示了后面应该会有某一步需要做G_3{G\_}^3然后消去G_

  • 最后就是30行的GGCC乘法运算可交换,原以为这里可以暴露GG的一些属性,后来才发现是跟上一点有关的,举个栗子即,(GC)2=GCGC=GGCC=G2C2(GC)^2=GC*GC=GG*CC=G^2C^2,这种幂次的运算需要有交换律才能完成。

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

  • 首先根据RotorReflector这个函数名,加上题目说的“古典密码”,加上搜索一下,可以盲猜这是在做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,所以盲猜CC的阶是3m3m,但后来发现这是错的(其实是没构造出来阶是3m3m的Jordan Form,挖个坑看看以后能不能继续构造或者证伪,逃);

  • 再次观察上面的循环圈,发现前一个向量的每一个值乘上3636N=43N=43刚好就是后一个向量对应的值(可以实验一下这里的“每一个”肯定不是巧合),前面说过加密其实是一次矩阵乘向量,那这个循环圈中的矩阵乘就可以转化成数乘了?根据线性代数教的知识,如果这个向量是特征向量,这个3636是对应的特征值的话,刚好可以这样做(指变数乘)。另外说一下,这里的循环圈循环次数为33是因为,3636GF(43)GF(43)中的阶为33,即3631(mod43)36^3 \equiv 1 \pmod {43}

  • 要验证上一点的猜想其实不难,在上上点中已经找到多组明密文对应的向量,只要验证每组是不是都可以转化成数乘就好了,结果是。都可以转化为数乘,而且这个“数”去重后刚好是99个(且不同的)。再检验一下还可以发现这多组的明密文对应的向量中,去重后向量的个数刚好是2727,即刚好是出题人构造好的vectors的数量;

  • 到这,如果猜想没错的话(最后证明其实是没错的),已经可以算出99个特征值了(不妨先记为λi\lambda'_i),但要注意算出来的特征值是(GN(N1)3Cm)(G^{\frac{N*(N-1)}{3}}C^m)的特征值(因为上面说了加密是ci=(F1GN(N1)3CmF)vic_i = (F^{-1}G^{\frac{N*(N-1)}{3}}C^mF)*v_i,相似矩阵特征值一样),而要算t的话需要的是CC的特征值,所以还需要转一下;

  • 首先做个三次方的话可以轻易消去GG那部分,因为GG的阶是N(N1)N(N-1)

    (F1GN(N1)3CmF)3F1C3mF(modN)(F^{-1}G^{\frac{N*(N-1)}{3}}C^mF)^3 \equiv F^{-1}C^{3m}F \pmod N

    (λi)3(modN)(\lambda'_i)^3 \pmod NC3mC^{3m}的特征值。那么CC的特征值就是λi=(λi)33m(λi)1m(modN)\lambda_i=(\lambda'_i)^{\frac{3}{3m}} \equiv (\lambda'_i)^{\frac{1}{m}} \pmod N,现在m=9m=9N=43N=43φ(N)=42=314\varphi(N)=42=3*14,即gcd(m,φ(N))=3gcd(m, \varphi(N))=3不能直接对mm求逆,可以AMM爆,但是N=43N=43太小了,直接枚举也可以(题目给了hash,应该也暗示了要枚举);

  • 最后根据特征值构造多项式ff(上面说了,CC的特征值是ff的根),然后用ff的系数恢复t,最后得到flag。

题解

按照上面的思路,解的步骤就是:

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

参考Exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# 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