Lab 6 : Keyword ciphers

0 Preliminaries

Important Read about keyword ciphers in your book: pages 33–34.

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

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

1 From the alphabet to \(\mathbb{Z}_{26}\)

We already saw how to do this last week. Feel free to copy your code.

Exercise 1 Write functions that can convert between letters and numbers, strings and lists of numbers.

def letter_to_num(c):
    """
    >>> letter_to_num('A')
    0
    >>> letter_to_num('Z')
    25

    """

def num_to_letter(n):
    """
    >>> num_to_letter(0)
    'A'
    >>> num_to_letter(25)
    'Z'

    """

def text_to_nums(m):
    """
    >>> 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]

    """

def nums_to_text(l):
    """
    >>> nums_to_text([12, 4, 4, 19, 12, 4, 0, 19, 19, 7, 4, 20, 18, 20, 0, 11, 15, 11, 0, 2, 4])
    'MEETMEATTHEUSUALPLACE'

    """

2 Remove duplicates

Recall we first remove duplicate letters from the keyword. Since we first convert the keyword to numbers, we will remove duplicates from a list of numbers.

We have to first be able to remove duplications in a list. The strategy is to start with a empty list L. Then we append each element in the input to L if it is not in L yet. This strategy guarantees that each element will only be appended once.

Exercise 2 Write a function which takes a list l and a number n and appends n to l only if n is not already in l.

def append_new(l,n):
      """
      >>> append_new([1,2,3], 3)
      [1, 2, 3]

      >>> append_new([1,2,3], 4)
      [1, 2, 3, 4]

      """

Exercise 3 Write a function which takes in a list and removes all the duplicates. Do not change the order of elements in the list. Start with an empty list and append elements to it from the given list using append_new.

def remove_dup(l):
      """
      >>> remove_dup([1,1,2,2])
      [1, 2]

      """

3 Extending the list

Now we have successfully converted the keyword into a list free of duplicates. We now need to extend this list so that it contains 0–25. The goal is to append each number in 0–25 (in ascending order) to this list unless the number already appears in the list.

Exercise 4 Write a function which takes in a list l and appends all the numbers in 0–25 which are not already in l in ascending order. Use append_new

def extend(l):
      """
      >>> extend([1,2,3,4,7])
      [1, 2, 3, 4, 7, 0, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

      """

4 Cycling the list

Now we make use of the second part of the key, the letter. The list we just obtained needs to be cycled according to the key letter. The corresponding number of the key letter implies how many positions we need to cycle the list. Each time we pop off the last element in the list and insert it at the beginning.

Exercise 5 Write a function which takes a list and moves its last element to the front of the list.

def cycle1(l):
      """
      >>> cycle1([1, 2, 3, 4, 0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25])
      [25, 1, 2, 3, 4, 0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]

      """

Exercise 6 Write a function which takes in a list l and a number n and cycles l n times. Use cycle1.

def cycle(l, n):
      """
      >>> cycle([1, 2, 3, 4, 0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25], 3)
      [23, 24, 25, 1, 2, 3, 4, 0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]

      """

5 Mapping from plaintext to ciphertext

Now we combine the previous steps together to prepare the key for use by the encryption and decryption functions. It should take in a keyword and a letter and outputs the list which stores the mapping from plaintext to ciphertext numbers.

>>> text_to_nums("MATHEMATICS")
[12, 0, 19, 7, 4, 12, 0, 19, 8, 2, 18]
>>> remove_dup([12, 0, 19, 7, 4, 12, 0, 19, 8, 2, 18])
[12, 0, 19, 7, 4, 8, 2, 18]
>>> extend([12, 0, 19, 7, 4, 8, 2, 18])
[12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25]
>>> letter_to_num("F")
5
>>> cycle([12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25], 5)
[21, 22, 23, 24, 25, 12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20]

Exercise 7 Combine previous into a function which outputs the list which stores the mapping from plaintext to ciphertext numbers. Use text_to_nums, letter_to_num, remove_dup, extend and cycle.

def mapping(keyword, letter):
      """
      >>> mapping("MATHEMATICS","F")
      [21, 22, 23, 24, 25, 12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20]

      """

6 Encryption and decryption of a number

Now we use the mapping to do encryption and decryption. We encrypt a number n between 0 and 25 by getting the \(n^{th}\) item in the mapping. We decrypt a number n between 0 and 25 by getting the index of n in the mapping.

Exercise 8 Write a function to find the \(n^{th}\) item in the given mapping.

def find_item(l,n):
      """
      >>> find_item([21, 22, 23, 24, 25, 12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20], 2)
      23

      """

Exercise 9 Write a function to find the index of an item in the given mapping.

def find_index(l,n):
      """
      >>> find_index([21, 22, 23, 24, 25, 12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20], 23)
      2

      """

7 Encryption and decryption of a message

Let’s play with an example. We should be capable of encrypting and decrypting a list of numbers now.

Exercise 10 Write a function that can encrypt a list of numbers with a given mapping. Use find_item.

def enc_list(key, l):
      """
      >>> enc_list([21, 22, 23, 24, 25, 12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20],[10, 13, 14, 22, 11, 4, 3, 6, 4, 8, 18, 15, 14, 22, 4, 17])
      [8, 1, 3, 15, 2, 25, 24, 0, 25, 7, 10, 5, 3, 15, 25, 9]

      """

Exercise 11 Write a function that can decrypt a list of numbers with a given mapping. Use find_index.

def dec_list(key, l):
      """
      >>> dec_list([21, 22, 23, 24, 25, 12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20],[8, 1, 3, 15, 2, 25, 24, 0, 25, 7, 10, 5, 3, 15, 25, 9])
      [10, 13, 14, 22, 11, 4, 3, 6, 4, 8, 18, 15, 14, 22, 4, 17]

      """

8 Put everything together

We are almost done. Let’s put all the components together. The encryption function should first generate the mapping with the input keyword and letter. Then it should convert the plaintext into a number list. After that, it encrypts the list with the mapping. Finally, it converts the ciphertext list into a string. The decryption function shares the same workflow but it will decrypt, instead of encrypt, the number list in the third step.

>>> mapping('MATHEMATICS','F')
[21, 22, 23, 24, 25, 12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20]
>>> text_to_nums('KNOWLEDGEISPOWER')
[10, 13, 14, 22, 11, 4, 3, 6, 4, 8, 18, 15, 14, 22, 4, 17]
>>> enc_list([21, 22, 23, 24, 25, 12, 0, 19, 7, 4, 8, 2, 18, 1, 3, 5, 6, 9, 10, 11, 13, 14, 15, 16, 17, 20], [10, 13, 14, 22, 11, 4, 3, 6, 4, 8, 18, 15, 14, 22, 4, 17])
[8, 1, 3, 15, 2, 25, 24, 0, 25, 7, 10, 5, 3, 15, 25, 9]
>>> nums_to_text([8, 1, 3, 15, 2, 25, 24, 0, 25, 7, 10, 5, 3, 15, 25, 9])
'IBDPCZYAZHKFDPZJ'

Exercise 12 Write a function that encrypts the input plaintext with the given keyword and letter. Use mapping and enc_list.

def encrypt(key, letter, message):
      """
      >>> encrypt('MATHEMATICS','F','KNOWLEDGEISPOWER')
      'IBDPCZYAZHKFDPZJ'

      """

Exercise 13 Write a function that decrypts the input ciphertext with the given keyword and letter. Use mapping and dec_list.

def decrypt(key, letter, ciphertext):
      """
      >>> decrypt('MATHEMATICS', 'F', 'IBDPCZYAZHKFDPZJ')
      'KNOWLEDGEISPOWER'

      """