IceCTF [Cryptography] - Hill Cipher

Crypto crypto Comments

On this challenge we were given the decoding matrix and the cipher text:

1
2
3
4
5
6
7
8
9
10

secret = [[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"

With this we can easily decode the ciphered text we only need to write a python script (to know how it works the decryption for hill cipher read this http://crypto.interactive-maths.com/hill-cipher.html) the one I wrote requires sympy package installed run pip install sympy:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

import math
import sympy
from sympy import init_printing, pprint
from sympy import Matrix
from sympy.vector import matrix_to_vector, CoordSysCartesian
init_printing()

def decrypt(matrix, words):
    cipher = ''
    M = Matrix(matrix)
    M = M.inv_mod(64)
    length = len(M)
    d = {}
    d2 = {}
    # arr = np.array([d[i] = j; j +=1 for i in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_{}"], dtype=int)
    alph = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_{}"

    for x in range(len(alph)):
        d[alph[x]] = x
        d2[x] = alph[x]
    # print d
    count = 0
    l = []

    for ch in words:
        if (count+1) % (8+1) == 0:
            m = Matrix(l)
            dot_pr_m = M*m
            # print mcd(dot_pr_m)
            # pprint(dot_pr_m.rref()[0][0])
            n = []
            for i in dot_pr_m:
                cipher += d2[i % 64]
            count = 0
            l = []
        l.append(d[ch])
        count += 1
    if (count+1) % (8+1) == 0:
        m = Matrix(l)
        dot_pr_m = M*m
        # print mcd(dot_pr_m)
        # pprint(dot_pr_m.rref()[0][0])
        n = []
        for i in dot_pr_m:
            cipher += d2[i % 64]
    return cipher

if __name__ == '__main__':
    #print mcd([])
    # exit(0)
    secret = [[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"
    # secret = [[7,8], [11,11]]
    # ciphertext = 'APADJTFTWLFJ'.lower()
    print(ciphertext)
    
print(decrypt(secret, ciphertext))
1
2
3
4
5

kinyabitch@Debian ~/h/crl> python hill-cipher.py 

7Nv7}dI9hD9qGmP}CR_5wJDdkj4CKxd45rko1cj51DpHPnNDb__EXDotSRCP8ZCQ
IceCTF{linear_algebra_plus_led_zeppelin_are_a_beautiful_m1xture}

TeamRocketISTCTF Team

Portuguese Computer Science Students