How I solved some advanced puzzles (3-4, 4-3, 5-1, 5-2, 5-3, 6-5) using Python
Introduction
This guide shows how I solved some of advance puzzles with the help of Python. Originally I was solving the puzzles with a pencil and printed screenshots (like the image below for 3-3; do not click to zoom if you do not want to be spoiled), but for later problems I got tired of trials and errors. So I got Python to do it.
Note: To post my codes to Steam Community, I had to rename the variables for list indexes from i to x in order to keep them from being parsed as markup tags (in my opinion the markups should be ignored within a code element).
3-4: Frequency Analysis
from collections import Counter
text = """
AJLPNYRJZJFLZYASGSKQGSMME
JKEJPFSVLPJLKKEJELNNSPZKY
NNYGNSGASGYZJGAKEYZYGASVW
NJKSWSKECNLUJZKEJZEYCYZWS
VOEKLGAHYKKJAZEJNYJZLKLGU
ESPPJLAFHSPZJLFSVGJRJPYTL
OYGJALZMJJKJPZUESSGJPLUEY
NATYOEKZLYNEJPKMSEVGAPJAK
SGZGLTJEYZCLGYSNL
""".replace("\n", "")
print(Counter(text))
The result (do not zoom if you don’t want to be spoiled):
To solve a polyalphabetic substitution cipher (Vigenère cipher), the first thing to do is to figure out the length of the key. According to the in-game hint, there are (at least) two repeating 3-letter sequences: DUF and LUE. Counting the spans of appearance for each of them, and then taking their greatest common divisor, we get the most likely length of the key: 3.
Once the length of the key is identified, we can use the frequency analysis technique as in monoalphabetic substitution ciphers. The code below divides the ciphetext into “phases” depending on which letter of the key is applied, and counts the frequency of the letters within the phase.
from collections import Counter
text = """\
LAFLUIWOYWPADUFHSNBVSWVNDZQDUF
RBPLUYQPLWLPHZRLUEDUBSYMIPRDIJ
HTYQUCUZYLKFRSKHZBUHULUEKPQFOY
LYSSAMWOCWHZOLGDTDDPPOFDDTGOPY
UDGWOYOSDRYKVVDVLAULRZYGWPLJZY
QKYPTWVLJIAFHHSWOMUVDDAPLMJLUE
PVLRNPDWFXWMQAFHZSEQCFAGQDFLJF
LHLDSWCLMQLFXUBULBDUBVPVWFQHWY
UHRHJGSOCUZZXAGFVLILQVAFDARKPQ
LZCQAGULJBUCZAMPL\
""".replace("\n", "")
phase1 = "".join(text[x] for x in range(len(text)) if x % 3 == 0)
phase2 = "".join(text[x] for x in range(len(text)) if x % 3 == 1)
phase3 = "".join(text[x] for x in range(len(text)) if x % 3 == 2)
triplets = (text[x - 2] + text[x - 1] + text[x] for x in range(2, len(text), 3))
print(Counter(phase1))
print(Counter(phase2))
print(Counter(phase3))
print(Counter(triplets))
The code also tries to find repeating 3-letter sequences like DUF and LUE. I thought that it was not necessary to find the sequences in the phases other than 1-2-3. Unfortunately that was not enough to find what is “THE” in the plaintext.
4-3: Brute Force Attack
After trying some shifts according to the frequency analysis, I decided to have my computer try.
The code outputs several candidates for the solution, so we have to pick up the correct one manually.
from string import ascii_uppercase as alphabets
from itertools import product
text = """\
LAFLUIWOYWPADUFHSNBVSWVNDZQDUF
RBPLUYQPLWLPHZRLUEDUBSYMIPRDIJ
HTYQUCUZYLKFRSKHZBUHULUEKPQFOY
LYSSAMWOCWHZOLGDTDDPPOFDDTGOPY
UDGWOYOSDRYKVVDVLAULRZYGWPLJZY
QKYPTWVLJIAFHHSWOMUVDDAPLMJLUE
PVLRNPDWFXWMQAFHZSEQCFAGQDFLJF
LHLDSWCLMQLFXUBULBDUBVPVWFQHWY
UHRHJGSOCUZZXAGFVLILQVAFDARKPQ
LZCQAGULJBUCZAMPL\
""".replace("\n", "")
def char_to_num(char):
return alphabets.index(char) + 1
def vigenere_sub(char1, char2):
return alphabets[(char_to_num(char1) - char_to_num(char2) - 1) % 26]
for key_chars in product(alphabets, repeat=3):
decryption = ""
for x in range(len(text)):
decryption += vigenere_sub(text[x], key_chars[x % 3])
if "THE" in decryption and "AND" in decryption:
print(key_chars)
print(decryption)
print()
As the upper-right part of the image may suggest, as a result of the brute force attack, I knew that I had almost solved the puzzle by frequency analysis but given up not being confident enough to proceed. (Do not zoom the image if you don’t want to be spoiled.)
5-1, 5-2, 5-3
For mechanized cryptography puzzles, we can write a code to emulate the functionalities of Enigma. We can use the same code to solve all of them except:
- For the second puzzle, we need some trial and error, or a bit of brute force, to determine the initial rotation of the disk.
- For the last puzzle, we need the function to swap some pairs of letters.
from string import ascii_uppercase as keyboard
scrambler1 = (keyboard, "UWYGADFPVZBECKMTHXSLRINQOJ")
scrambler2 = (keyboard, "AJPCZWRLFBDKOTYUQGENHXMIVS")
scrambler3 = (keyboard, "TAGBPCSDQEUFVNZHYIXJWLRKOM")
reflector = (keyboard, "YRUHQSLDPXNGOKMIEBFZCWVJAT")
def scramble(position, disk, backwards=False):
row1, row2 = disk[::-1] if backwards else disk
char = row1[position]
return row2.index(char)
def rotate(disk, n):
return (disk[0][n:] + disk[0][:n], disk[1][n:] + disk[1][:n])
def decrypt(char, *disks):
x = keyboard.index(char)
for disk in disks:
x = scramble(x, disk)
for disk in disks[-2::-1]:
x = scramble(x, disk, True)
return keyboard[x]
def decrypt_text(text, *disks):
decryption = ""
disk1 = disks[0]
for char in text:
disk1 = rotate(disk1, 1)
decryption += decrypt(char, disk1, *disks[1:])
return decryption
def swap(text, key):
result = ""
for char in text:
result += key.replace(char, "") if char in key else char
return result
def swap_keys(text, keys):
for key in keys:
text = swap(text, key)
return text
def puzzle_5_1():
print(decrypt_text("ZYDNI", scrambler1, reflector))
def puzzle_5_2():
for i in range(26):
scrambler = rotate(scrambler1, i)
text = decrypt_text("QHSGUWIG", scrambler, reflector)
if text[:2] == "XV":
print(text)
def puzzle_5_3():
text = "GYHRVFLRXY"
keys = ("AB", "SZ", "UY", "GH", "LQ", "EN")
text = swap_keys(text, keys)
d1 = rotate(scrambler2, scrambler2[0].index("A"))
d2 = rotate(scrambler1, scrambler1[0].index("E"))
d3 = rotate(scrambler3, scrambler3[0].index("B"))
text = decrypt_text(text, d1, d2, d3, reflector)
text = swap_keys(text, keys)
print(text)
puzzle_5_1()
puzzle_5_2()
puzzle_5_3()
6-5
The puzzle is simple—just executing the algorithm backwards. However solving this by hand, one small mistake could mess up everything. That is why I used (or had to use, I confess) Python to solve this.
Note that I re-interpreted the algorithm: instead of applying the row-swapping to both of the text and the key and then XOR-ing them, I interpreted the instruction as first XOR-ing them and then swapping the rows—the results being the same.
def block(bitstr):
return (bitstr[:4], bitstr[4:8], bitstr[8:12], bitstr[12:])
def swap(rows):
return tuple(row[1] + row[0] + row[3] + row[2] for row in rows)
def xor(rows, key):
keybits = "".join(bin(ord(char))[2:].zfill(8) for char in key)
if len(keybits) != 16: raise AssertionError
textbits = "".join(rows)
val = "".join("0" if keybits[x] == textbits[x] else "1" for x in range(16))
return block(val)
def shift(rows):
result = []
for n in range(len(rows)):
row = rows[n]
result.append(row[n:] + row[:n])
return tuple(result)
def decrypt(cipher, key):
return xor(swap(shift(cipher)), key)
ciphertext = block("1001011110110101")
first = decrypt(ciphertext, "BX")
second = decrypt(first, "YS")
print(chr(int(second[0] + second[1], 2)))
print(chr(int(second[2] + second[3], 2)))
