Lab 12 : Hill’s System

In this lab, we will implement the encryption and decryption function for Hill’s System. We assume the key matrix size is 2x2.

0 Preliminaries

To run doctests, add the following to the bottom of your file:

if (__name__ == '__main__'):
  import doctest
  doctest.testmod(optionflags= doctest.NORMALIZE_WHITESPACE)

We will reuse the following code from previous labs.

A_Z = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def text_to_nums(s):
    """
    Assumes s is string over {A,...,Z}

    >>> text_to_nums('EFFERVESCENCE')
    [4, 5, 5, 4, 17, 21, 4, 18, 2, 4, 13, 2, 4]

    """
    return [A_Z.index(c) for c in s]

def nums_to_text(l):
    """
    Assumes l encodes string over {A,...,Z} with numbers in Z_26

    >>> nums_to_text([4, 5, 5, 4, 17, 21, 4, 18, 2, 4, 13, 2, 4])
    'EFFERVESCENCE'

    """
    return "".join([A_Z[i] for i in l])

1 Matrix times a vector

Exercise 1 Write a function which multiplies a 2x2 matrix and a vector (represented as a list) with entries in the integers modulo n.

def mul_mat_vec_mod(m, v, n):
    """
    >>> mul_mat_vec_mod([[9, 4], [5, 7]], [5, 20], 26)
    [21, 9]

    """

2 Encryption in Hill’s system

To implement the encryption system, we first split up the message (a list of numbers) into blocks of two numbers and then multiply each block by the key matrix. In the case where there is an odd number of numbers in the input list, we pad the list with an extra ‘0’.

Exercise 2 Write a function which splits a list of numbers into a list of lists of numbers. Each list of numbers in the output list contains 2 numbers. If the size of the input list is odd, append an extra ‘0’ at the end.

def split_list(l):
    """
    >>> split_list([1, 2, 3, 4, 5, 6, 7, 8])
    [[1, 2], [3, 4], [5, 6], [7, 8]]

    >>> split_list([1, 2, 3, 4, 5, 6, 7, 8, 9])
    [[1, 2], [3, 4], [5, 6], [7, 8], [9, 0]]

    >>> split_list([12, 4, 4, 19, 12, 4, 0, 19, 19, 7, 4, 20, 18, 20, 0, 11, 15, 11, 0, 2, 4])
    [[12, 4], [4, 19], [12, 4], [0, 19], [19, 7], [4, 20], [18, 20], [0, 11], [15, 11], [0, 2], [4, 0]]

    """

Exercise 3 Write a function which takes a 2x2 matrix and a list of length-two lists of numbers, multiplies each list of numbers with the input matrix on the left modulo n and flattens the resulting list of list of numbers into a list of numbers. Use mul_mat_vec_mod.

def mul_mat_lov_mod(m, lov, n):
    """
    >>> mul_matrix_lov_mod([[9, 4], [5, 7]], [[12, 4], [4, 19], [12, 4], [0, 19], [19, 7], [4, 20], [18, 20], [0, 11], [15, 11], [0, 2], [4, 0]], 26)
      [20, 10, 8, 23, 20, 10, 24, 3, 17, 14, 12, 4, 8, 22, 18, 25, 23, 22, 8, 14, 10, 20]

    """

We are now ready to compose all these operations into an encryption function:

>>> text_to_nums('MEETMEATTHEUSUALPLACE')
[12, 4, 4, 19, 12, 4, 0, 19, 19, 7, 4, 20, 18, 20, 0, 11, 15, 11, 0, 2, 4]
>>> split_list([12, 4, 4, 19, 12, 4, 0, 19, 19, 7, 4, 20, 18, 20, 0, 11, 15, 11, 0, 2, 4])
[[12, 4], [4, 19], [12, 4], [0, 19], [19, 7], [4, 20], [18, 20], [0, 11], [15, 11], [0, 2], [4, 0]]
>>> mul_mat_lov_mod([[9, 4], [5, 7]], [[12, 4], [4, 19], [12, 4], [0, 19], [19, 7], [4, 20], [18, 20], [0, 11], [15, 11], [0, 2], [4, 0]], 26)
[20, 10, 8, 23, 20, 10, 24, 3, 17, 14, 12, 4, 8, 22, 18, 25, 23, 22, 8, 14, 10, 20]
>>> nums_to_text([20, 10, 8, 23, 20, 10, 24, 3, 17, 14, 12, 4, 8, 22, 18, 25, 23, 22, 8, 14, 10, 20])
'UKIXUKYDROMEIWSZXWIOKU'

Exercise 4 Write a function which encrypts the text with a key matrix using Hill’s system. Use text_to_nums, split_list, mul_mat_lov_mod and nums_to_text.

def hill_enc(k, m):
    """
    >>> hill_enc([[9, 4], [5, 7]],'EVERYDOGHASHISDAY')
    'QLAJULUILJIJOKBPIQ'
    """

3 Decryption in Hill’s system

Decryption is encryption with the inverse of the original key matrix.

Exercise 5 Write a function which computes the inverse of a 2x2 matrix modulo n. (You may use your code from last lab.)

def invert_2x2_mod(matrix, n):
    """
    Assumes that (a*d - b*c) is invertible mod n.

    >>> invert_2x2_mod([[1, 2], [3, 4]], 7)
    [[5, 1], [5, 3]]

    """

>>> invert_2x2_mod([[9, 4], [5, 7]], 26)
[[5, 12], [15, 25]]
>>> hill_dec([[9, 4], [5, 7]], 'UKIXUKYDROMEIWSZXWIOKU')
'MEETMEATTHEUSUALPLACEA'

Exercise 6 Write a function which decrypts the ciphertext with the original key matrix. Use invert_2x2_mod and hill_enc.

def hill_dec(k, m):
    """
    >>> hill_dec([[9, 4], [5, 7]], 'QLAJULUILJIJOKBPIQ')
    'EVERYDOGHASHISDAYA'
    """