## 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}.