At first, let’s define final_state(), which returns the last state of transduce(B, s) for input B.

def transduce(b, s=0):
if len(b) == 0:
return b
d, t = T[s]
b0, bp = b, b[1:]
return [b0 ^ t] + transduce(bp, s=d[b0])

def final_state(b, s=0):
if len(b) == 0:
return s
d, _ = T[s]
b0, bp = b, b[1:]
return transduce_state(bp, s=d[b0])

The problem of breaking the cipher is that there’s swapping action of left 32bit & right 32bit in each stage.

def swap(b):
l = BLOCK_SIZE // 2
m = (1 << l) - 1 return (b >> l) | ((b & m) << l)

class Transducipher:
def __init__(self, k):
self.k = [k]
for i in range(1, len(T)):
k = swap(transduceblock(k))
self.k.append(k)

def encrypt(self, b):
for i in range(len(T)):
b ^= self.k[i]
b = transduceblock(b)
b = swap(b)
return b

Let’s say self.k[i] as Key_i, and block of the each stage as Data_i. (Data_0 is the input of the encrypt() function. The output of the encrypt() function will be Data_6.)
Next, let’s say the left 32bit of block B_i as B_i,0, and the right 32bit as B_i,1.

From Key_i, we can write Key_i+1,0 and Key_i+1,1 like these:

Key_i+1,1 = transduce(Key_i,0, 0)
Key_i+1,0 = transduce(Key_i,1, final_state(Key_i,0, 0) )

From these, we can write out some relations of the Key_i,j blocks which affected by Key_0,0, with some unknown states.

Key_1,1 = transduce(Key_0,0, 0)
Key_2,0 = transduce(Key_1,1, final_state(Key_1,0, 0) )
Key_3,1 = transduce(Key_2,0, 0)
Key_4,0 = transduce(Key_3,1, final_state(Key_3,0, 0) )
Key_5,1 = transduce(Key_4,0, 0)

Also, we can write out relations from Data_0,0.

Data_1,1 = transduce(Data_0,0 ^ Key_0,0, 0)
Data_2,0 = transduce(Data_1,1 ^ Key_1,1, final_state(Data_1,0 ^ Key_1,0, 0) )
Data_3,1 = transduce(Data_2,0Key_2,0, 0)
Data_4,0 = transduce(Data_3,1 ^ Key_3,1, final_state(Data_3,0 ^ Key_3,0, 0) )
Data_5,1 = transduce(Data_4,0Key_4,0, 0)
Data_6,0 = transduce(Data_5,1 ^ Key_5,1, final_state(Data_5,0 ^ Key_5,0, 0) )

The key idea is that, if we just assume the unknown values from  final_state() in these relations, we can get Data_6,0 from Key_0,0 & Data_0,0 immediately. There are five unknown states, so we can assume those states and get 6**5 settings for them.
From this, we can write a backtracking function for finding Key_0,0, from 0th bit to 31st bit.

def transduce_withstate(b, s=0): # Also returns the final state
if len(b) == 0:
return b, s
d, t = T[s]
b0, bp = b, b[1:]

rb, fs = transduce_withstate(bp, s=d[b0])

return [b0 ^ t] + rb, fs

# Backtracking function for first 32 bit of the first key
def backtrack_first32bit(idx, data_in, data_out, key_cand, states, data_num):
a, b, c, d, e = states

# First 32bits are filled
if idx == 32:
key_copy = [k for k in key_cand]
data_copy = data_in[:32]
next_states = []

istates = [ (0, 0), (a, b), (0, 0), (c, d), (0, 0) ]

# Get states for calculating last 32bits of the key
for i in range(5):
i1, i2 = istates[i]
for j in range(32):
data_copy[j] ^= key_copy[j]
key_copy, kstate = transduce_withstate(key_copy, i1)
data_copy, dstate = transduce_withstate(data_copy, i2)

if i%2 == 0:
next_states.append(kstate)
next_states.append(dstate)

# Backtrack for remaining
backtrack_last32bit(0, data_in, data_out, key_cand, next_states, states, data_num)

return

for b0 in range(2): # Test the idx th bit as b0

key_copy = [k for k in key_cand]
key_copy.append(b0)
data_copy = data_in[:idx+1]

# Run the encryption
istates = [ (0, 0), (a, b), (0, 0), (c, d), (0, 0), (0, e) ]

for i1, i2 in istates:
for j in range(idx+1):
data_copy[j] ^= key_copy[j]
key_copy = transduce(key_copy, i1)
data_copy = transduce(data_copy, i2)

# Compare
if data_copy[idx] != data_out[idx]:
continue # Failed

key_copy = [k for k in key_cand]
key_copy.append(b0)
backtrack_first32bit(idx+1, data_in, data_out, key_copy, states, data_num)

# Data of the problem
data = [[13079742441184578626, 15822063786926281121],
...
[10970386673164693022, 12683515533170128309]]

if __name__ == "__main__":
# Change data to binary vector form
for i in range(len(data)):
data[i], data[i] = block2bin(data[i]), block2bin(data[i])

# Test for each datum (total 16 data)
for data_num in range(len(data)):

# Assume five states
for i in range(6**5):
states = [(i // (6**j)) % 6 for j in range (5)]
backtrack_first32bit(0, data[data_num], data[data_num], [], states, data_num)

if i % 100 == 0:
print(data_num, i)

print(data_num, "end")

if data_num > 0:
pos_key.intersection_update(pos_key[data_num])

print(len(pos_key))
if len(pos_key) < 5:
print(pos_key)

After finding candidates of Key_0,0, we can also get candidates of Key_0,1  from Key_0,0. backtrack_last32bit() will do this.
Furthermore, we can re-calculate the five states, which are assumed at first, from Key_0,1. We can compare the value between the assumed ones and the re-calculated ones, and find out whether the assumed setting is right or not.

The key(Key_0) is 11424187353095200769, and the flag is PCTF{9e8adddea4bfe001}.