We are given two files: the main script horst.py, used for encryption and decryption; data.txt, which includes two plaintext-ciphertext pairs. The encryption function is defined as follows:

M = 3

1
2
3
4
5

def encrypt(m, k):
    x, y = m
    for i in range(M):
        x, y = (y, x * k.inv() * y * k)
    return x, y

where x, y are both permutations of the set {1, 2, …, 64}. Our goal is to recover the key k. After some calculations (of 3 round encryption), we know that if the plaintext is (x, y), then the ciphertext would be (yk’xk’ykk, xk’yyk’xk’ykkk), where k’ is k.inv(), as defined in the main script, the inverse of k.
Let (x1, y1), (c1, d1) be the plaintext and ciphertext of the first pair, respectively. (x2, y2) and (c2, d2) follow the similar definitions. Notice that d1d2’ = x1k’y1c1c2’y2’kx2’ holds. Let t = x1’d1d2’x2 and b = y1c1c2’y2’, we have t = k’bk, that is, t is a conjugate of b with respect to k’. According to Theorem 2, if we know the cycle notations of b and t, then we can construct u such that t = ubu’, and u will be a candidate of k’. Here is the exploit:

cycles of b

v1 = map(int, ‘0 53 9 62 2 36 59 25 39 58 34 41 63 30 21 49 16 3 52 37 57 10 40 8 5 55 24 4 17 29 32 31 27 19 6 7 47 51’.split())
v2 = map(int, ‘1 15 26 18 61 56 38 42 11 35 43 44 22 54 60 46 20 14 28 23 33 13 48 12 45 50’.split())

cycles of t = k^-1 * b * k

w1 = map(int, ‘1 11 46 43 30 17 34 59 23 6 38 50 39 45 47 36 20 52 63 21 4 10 54 24 29 18 9 42 57 37 27 15 62 41 55 40 58 56’.split())
w2 = map(int, ‘0 61 16 48 31 25 49 3 51 12 28 26 8 7 13 44 2 35 60 53 5 32 33 14 22 19’.split())

1
2
3
4
5
6
7
8
9
10
11
12

for _ in range(len(v1)):
    for _ in range(len(v2)):
        k = [None] * N
        for i in range(len(v2)):
            k[v2[i]] = w2[i]
        for i in range(len(v1)):
            k[v1[i]] = w1[i]
        m = Permutation(k)
        if (x1, y1) == decrypt((c1, d1), m) and (x2, y2) == decrypt((c2, d2), m):
            print "The flag is: PCTF{%s}" % sha1(str(m)).hexdigest()
        v2 = [v2[-1]] + v2[:-1]
    v1 = [v1[-1]] + v1[:-1]

Flag: PCTF{69f4153d282560cdaab05e14c9f1b7e0a5cc74d1}