Rating:

# IceCTF 2016 – Over the Hill

## Problem

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

## Solution

As hinted at by the name, this challenge uses the [Hill Cipher](https://en.wikipedia.org/wiki/Hill_cipher).

Enter the alphabet, matrix and ciphertext values provided with the problem.

```mathematica

alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_{}";

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}};

ciphertext = "7Nv7}dI9hD9qGmP}CR_5wJDdkj4CKxd45rko1cj51DpHPnNDb__EXDotSRCP8ZCQ";

```

Get the index of each ciphertext character using the alphabet. We assume 0 based indexes (Mathematica uses 1 based indexes normally. Wikipedia used 0 based indexes and the highest index in the key was 63, so this challenge probably uses 0 based indexes.

`Characters[]` will split a string into a list of single character strings, whose index can be looked up in alphabet using `StringPosition[]`.

```mathematica

ciphertextIndexes = StringPosition[alphabet, #][[1, 1]] - 1 & /@ Characters@ciphertext

```

```

{58, 39, 21, 58, 63, 3, 34, 60, 7, 29, 60, 16, 32, 12, 41, 63, 28,

43, 61, 56, 22, 35, 29, 3, 10, 9, 55, 28, 36, 23, 3, 55, 56, 17, 10,

14, 52, 2, 9, 56, 52, 29, 15, 33, 41, 13, 39, 29, 1, 61, 61, 30, 49,

29, 14, 19, 44, 43, 28, 41, 59, 51, 28, 42}

```

Split the ciphertext into vertical matrices the size of the key matrix.

```mathematica

ciphertextParts = Partition[List /@ ciphertextIndexes, Length@matrix]

```

```

{{{58}, {39}, {21}, {58}, {63}, {3}, {34}, {60}}, {{7}, {29}, {60},

{16}, {32}, {12}, {41}, {63}}, {{28}, {43}, {61}, {56}, {22}, {35},

{29}, {3}}, {{10}, {9}, {55}, {28}, {36}, {23}, {3}, {55}}, {{56},

{17}, {10}, {14}, {52}, {2}, {9}, {56}}, {{52}, {29}, {15}, {33},

{41}, {13}, {39}, {29}}, {{1}, {61}, {61}, {30}, {49}, {29}, {14},

{19}}, {{44}, {43}, {28}, {41}, {59}, {51}, {28}, {42}}}

```

Just do a dot product of the message parts with the inverse of the matrix. Everything is done with a modulus of the length of the alphabet.

```mathematica

messageParts = Mod[

Inverse[matrix, Modulus -> StringLength@alphabet].#,

StringLength@alphabet] & /@ ciphertextParts

```

```

{{{34}, {2}, {4}, {28}, {45}, {31}, {62}, {11}}, {{8}, {13}, {4},

{0}, {17}, {61}, {0}, {11}}, {{6}, {4}, {1}, {17}, {0}, {61}, {15},

{11}}, {{20}, {18}, {61}, {11}, {4}, {3}, {61}, {25}}, {{4}, {15},

{15}, {4}, {11}, {8}, {13}, {61}}, {{0}, {17}, {4}, {61}, {0}, {61},

{1}, {4}}, {{0}, {20}, {19}, {8}, {5}, {20}, {11}, {61}}, {{12},

{52}, {23}, {19}, {20}, {17}, {4}, {63}}}

```

`Flatten[]` the nested list of indexes into a one dimensional list, then convert the indexes back into characters, and join the single character strings back together.

```mathematica

StringJoin[StringPart[alphabet, # + 1] & /@ Flatten@messageParts]

```

```

IceCTF{linear_algebra_plus_led_zeppelin_are_a_beautiful_m1xture}

```

Original writeup (https://github.com/bburky/mathematica-ctf-writeups/tree/master/Hill%20cipher).