## How to solve

Permutations can be handled as matrices.

For given key $k$ and plaintext $(x, y)$, the result of one-round encryption is:

$(x_1, y_1) = (y, xk^{-1}yk)$

Let’s do this for three rounds!

$(x_2, y_2) = (xk^{-1}yk, yk^{-1}xk^{-1}yk^2)$
$(x_3, y_3) = (y_2, xk^{-1}ykk^{-1}y_2k) = (y_2, xk^{-1}yy_2k)$

If we define $t = yy_2$, we can say that

$(yx_3, y_3) = (t, xk^{-1}tk)$

So, the three-round encryption is not different from the one-round one!

From this, just run backtracking for $x^{-1}y_3 = k^{-1}tk$ to get proper $k$ that satisfies the both sets.

```import random
from hashlib import sha1
from horst import Permutation

with open('data.txt', 'r') as f:

(x1, y1), (t1, u1) = data[0]
(x2, y2), (t2, u2) = data[1]

# Left-hand side: l
l1, l2 = x1.inv() * u1, x2.inv() * u2
# Right-hand side: k^{-1} r k
r1, r2 = y1 * t1, y2 * t2

k = [-1 for _ in range(64)]
kinv = [-1 for _ in range(64)]
called = []

def backtrack(idx):
if idx in called:
st = set(range(64)) - set(called)
if len(st) == 0:
k_str = str(Permutation(k)).encode('ascii')
print("PCTF{%s}" % sha1(k_str).hexdigest())
exit(0)
backtrack(min(st))
return

called.append(idx)
p, q = l1[idx], l2[idx]

# Running backtracking for: `l = k^{-1} r k`
# If `l[idx] = p`, then `k[r[kinv[idx]]] = p`
# Let's say `kinv[idx] = a, r[a] = b, k[b] = p`.
# Just do possible all the (a, b) pairs for backtracking.

# Possible `a` values
if kinv[idx] != -1:
arange = [kinv[idx]]
else:
# Values which are not used
arange = list(set(range(64)) - set(kinv))

for a in arange:

# If k[a] is assigned, flag_ka is True.
flag_ka = False
if kinv[idx] == -1:
flag_ka = True
kinv[idx] = a
k[a] = idx

b = r1[a]
c = r2[a]

if ((k[b] != -1 and k[b] != p) or (kinv[p] != -1 and kinv[p] != b)
or (k[c] != -1 and k[c] != q) or (kinv[q] != -1 and kinv[q] != c)):
# Set back
if flag_ka:
kinv[idx] = -1
k[a] = -1
continue

# If k[b] is assigned, flag_kb is True, and so on.
flag_kb, flag_kc = False, False
if k[b] == -1:
flag_kb = True
k[b] = p
kinv[p] = b
if k[c] == -1:
flag_kc = True
k[c] = q
kinv[q] = c

backtrack(p)

# Set back
if flag_kc:
k[c] = -1
kinv[q] = -1
if flag_kb:
k[b] = -1
kinv[p] = -1
if flag_ka:
kinv[idx] = -1
k[a] = -1

called.pop()

backtrack(0)```

The flag is `PCTF{69f4153d282560cdaab05e14c9f1b7e0a5cc74d1}`.