Stage 2 - Over the Hill

[koddsson]

Description

Over the hills and far away... many times I've gazed, many times been bitten. Many dreams come true and some have silver linings, I live for my dream of a decrypted flag. crypted

Solution

Flag is: IceCTF{linear_algebra_plus_led_zeppelin_are_a_beautiful_m1xture}

[koddsson]

Probably a Hill cypher.

[koddsson]

This was indeed a Hill cipher but what confused us a lot of the time was how you calculated the inverse matrix. The wikipedia article doesn't go into great detail about this which ended with us asking the author of the puzzle for help:

This led us to this caluclator that calculated the inverse matrix which can then be used as a decryption key to get the key.

import sys
import numpy as np

# The following three variables where given
alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_{}"
ciphertext = "7Nv7}dI9hD9qGmP}CR_5wJDdkj4CKxd45rko1cj51DpHPnNDb__EXDotSRCP8ZCQ"
matrix = [[54, 53, 28, 20, 54, 15, 12, 7],
          [32, 14, 24, 5, 63, 12, 50, 52],
          [63, 59, 40, 18, 55, 33, 17, 3],
          [63, 34, 5, 4, 56, 10, 53, 16],
          [35, 43, 45, 53, 12, 42, 35, 37],
          [20, 59, 42, 10, 46, 56, 12, 61],
          [26, 39, 27, 59, 44, 54, 23, 56],
          [32, 31, 56, 47, 31, 2, 29, 41]]

# We got the inverted matrix from a online caluclator by plugging the original
# matrix variable into it. http://planetcalc.com/3324/
inverted_matrix = [
        [31, 44, 13, 33, 47, 24, 12, 21],
        [37, 22, 19, 37, 40,  1, 59, 55],
        [45, 59, 63,  4, 27, 63, 20, 50],
        [44, 10,  0,  9, 11,  1, 14, 16],
        [54, 47, 14,  7, 31, 25, 48, 48],
        [39,  2, 56, 48, 38, 27, 48, 34],
        [38,  1, 12, 40, 40, 13, 34,  5],
        [27, 22,  5, 21, 22, 20,  7, 59]
]

a = np.matrix(inverted_matrix)

# Convert the ciphertext to their position in our alphabet
numbers = map(lambda x: alphabet.index(x), ciphertext)

# Split the numbers into arrays of 8 in lenght so we can dot multiply it to the
# inverted matrix
decrypt = [numbers[i:i + 8] for i in xrange(0, len(numbers), 8)]

# Loop through all the ciphertext numbers, decrypt them to the correct position
# in our alphabet and write out the correct character
for x in decrypt:
    numbers = (np.dot(a, x) % 64).tolist()[0]
    for y in numbers:
        sys.stdout.write(alphabet[int(y)])