Cypher: Python Codes to Solve Advanced Puzzles (3-4, 4-3, 5-*, 6-5)

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

The code below counts the frequency of each letter. Once it’s done, assign each letter according to the output and ETAOIN SHRDLU, and you will identify the THE’s. Then the problem is easily solved with a pencil and paper.
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):

4-3: Frequency Analysis

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)))

By unvollstaendigkeitssatz

Leave a Comment

ArabicEnglishFrenchGermanItalianJapaneseKoreanPortugueseSpanish