[Original Writeup](https://dope-beats.com/markdown/transposed)

# Transposed [100]

In this challenge we are given a few lines of python and an output file.

```python
import random

W = 7
perm = range(W)
random.shuffle(perm)

msg = open("flag.txt").read().strip()
while len(msg) % (2*W):
msg += "."

for i in xrange(100):
msg = msg[1:] + msg[:1]
msg = msg[0::2] + msg[1::2]
msg = msg[1:] + msg[:1]
res = ""
for j in xrange(0, len(msg), W):
for k in xrange(W):
res += msg[j:j+W][perm[k]]
msg = res
print msg
```

Output file:
```
L{NTP#AGLCSF.#OAR4A#STOL11__}PYCCTO1N#RS.S
```

The python script reads in the flag, pads it with `.` so that the length is a
multiple of 14, and then shuffles the characters around. To get a feel for how
the algorithm works, we can first run the script with our own input, and print
out the intermediate values.

```python
# --snip--
msg = "ABCDEFGHIJKLMN"
while len(msg) % (2*W):
msg += "."

for i in xrange(100):
print(msg)
# --snip--
```

After running the script a few times to get different permutations, we notice
that sometimes the output repeats very quickly, and we see that the shuffling
tends to undo itself.

```
ABCDEFGHIJKLMN
DNHFCLJEAIGBMK
FKELHBICDAJNMG
LGCBENAHFDIKMJ
BJHNCKDELFAGMI
NIEKHGFCBLDJMA
KACGEJLHNBFIMD
GDHJCIBEKNLAMF
JFEIHANCGKBDML
ILCAEDKHJGNFMB
--snip--
ABCDEFGHIJKLMN <- Original input
```

We can check with grep to see if this always happens, and indeed it looks like
the pattern always undoes itself, even though sometimes it takes many
iterations.

```
python encrypt.py | grep ABCDEFG
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
```

So now all we have to do is figure out what the original `perm` array was set
to. If we can get the right values for this array, we can simply run the
`encrypt.py` script with the output data and print out intermediate values which
look like possible flags. Luckily there are only `7! == 5040` possible
permutations of `perm` so we can easily brute force this.

```python
import random
import itertools
import re

W = 7
original_msg = open("output").read().strip()
while len(original_msg) % (2*W):
original_msg += "."

for perm in itertools.permutations(range(W)):
msg = original_msg
for i in xrange(100):
if re.match(r"^FLAG{.*}\.\.$", msg):
print(msg)
# --snip--
```

The script takes a few seconds to check all possible permutations, and sure
enough at some point the encryption algorithm undoes itself and we get the flag.

```
python decrypt.py
FLAG{##CL4SS1CAL_CRYPTO_TRANSPOS1T1ON##}..
FLAG{##CL4SS1CAL_CRYPTO_TRANSPOS1T1ON##}..
FLAG{##CL4SS1CAL_CRYPTO_TRANSPOS1T1ON##}..
```