Lab 5 : Additive Ciphers

0 Preliminaries

If you are using Python 2, add the following statement to the top of your file (if you don’t know which version you are using, there’s no harm in adding it anyway):

from __future__ import print_function

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}\)

A basic step in many cipher systems is the conversion back and forth of a text to a numerical representation. For the additive cipher, we will convert individual letters to numbers as follows:

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12

N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

The goal of this section is to write Python functions which convert letters to numbers and numbers to letters. There are several reasonable approaches to this problem. One is to define a list of the symbols in your collection and to use list indexing and the index method to decode and encode:

>>> symbols = ['A', 'B', 'C']
>>> symbols.index('C')
2
>>> symbols[2]
'C'

You might also take advantage of the fact that ASCII codes preserve the order of upper-case letters and are in the range 65 – 90:

>>> ord('A')
65
>>> ord('Z')
90
>>> chr(65)
'A'
>>> chr(90)
'Z'

Exercise 1 Write a function that converts upper case letters A–Z to numbers 0–25 as in the table above.

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

Exercise 2 Write a function that converts numbers 0–25 to upper case letters A–Z as in the table above.

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

Exercise 3 Write a function that converts a message written in symbols in the range A–Z to a list of numbers 0–25. Use letter_to_num.

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]
    """

Exercise 4 Write a function that converts a list of numbers in the range 0–25 to a string of symbols in the range A–Z. Use num_to_letter.

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'

Challenge 1 You might notice that all the letters are capital and punctuation and spaces are missing. This is just for convenience. Extend the collection of symbols you would allow in your plaintext message: the only constraint is that each symbol must correspond to only one number in \(\{0,\dotsc,n-1\}\) where \(n\) is at least the number of symbols in your collection.

2 Encrypting a message

Exercise 5 Write a function which takes two integers and adds them modulo 26. The output must be in the range 0–25.

def add_26(a,b):
    """
    >>> add_26(25, 4)
    3
    >>> add_26(23, 3)
    0
    """

Exercise 6 Write a function which takes an integer k and a list of integers l and adds k to every element in l modulo 26. Use add_26.

def map_add_26(k,l):
    """
    >>> map_add_26(3, [12, 4, 4, 19, 12, 4, 0, 19, 19, 7, 4, 20, 18, 20, 0, 11, 15, 11, 0, 2, 4])
    [15, 7, 7, 22, 15, 7, 3, 22, 22, 10, 7, 23, 21, 23, 3, 14, 18, 14, 3, 5, 7]
    """

Exercise 7 Encryption using an additive cipher proceeds as follows. First, the sender picks a key, typically from 0–25. She then converts her plaintext message to numbers. She then encrypts her message by adding her key modulo 26 to every number in her message, which has been converted to numbers. She then converts the result back to letters.

We have all the functions we need at this point. Suppose that you want to encrypt the message “Meet me at five” using the key 4:

>>> text_to_nums('MEETMEATFIVE')
[12, 4, 4, 19, 12, 4, 0, 19, 5, 8, 21, 4]
>>> map_add_26(4, [12, 4, 4, 19, 12, 4, 0, 19, 5, 8, 21, 4])
[16, 8, 8, 23, 16, 8, 4, 23, 9, 12, 25, 8]
>>> nums_to_text([16, 8, 8, 23, 16, 8, 4, 23, 9, 12, 25, 8])
'QIIXQIEXJMZI'

The ciphertext is QIIXQIEXJMZI.

Exercise 8 Write a function which takes a key k and a plaintext message and returns a ciphertext. Use text_to_nums, map_add_26 and nums_to_text.

def encrypt(k,m):
    """
    >>> encrypt(6, 'MEETMEATTHEUSUALPLACE')
    'SKKZSKGZZNKAYAGRVRGIK'
    """

Challenge 2 Write encrypt so that it supports the extended collection of symbols you defined in Challenge 1.

3 Decrypting a message

Exercise 9 Write a function which computes the additive inverse of an integer modulo 26.

def add_inv_26(a):
"""
>>> add_inv_26(0)
0
>>> add_inv_26(25)
1
>>> add_inv_26(13)
13
"""

Exercise 10 Decryption proceeds as follows. First, the receiver converts the ciphertext to numbers. Second, she computes the additive inverse modulo 26 of the key. Call it k_inv. Then she adds k_inv modulo 26 to every number in her ciphertext, which has been converted to numbers. Then she converts the resulting numbers back to letters.

>>> text_to_nums('SKKZSKGZLOBK')
[18, 10, 10, 25, 18, 10, 6, 25, 11, 14, 1, 10]
>>> add_inv_26(6)
20
>>> map_add_26(20,[18, 10, 10, 25, 18, 10, 6, 25, 11, 14, 1, 10])
[12, 4, 4, 19, 12, 4, 0, 19, 5, 8, 21, 4]
>>> nums_to_text([12, 4, 4, 19, 12, 4, 0, 19, 5, 8, 21, 4])
'MEETMEATFIVE'

Exercise 11 Write a function which takes a key k and a ciphertext and returns a plaintext message. Use text_to_nums, map_add_26, nums_to_text and add_inv_26.

def decrypt(k,m):
    """
    >>> decrypt(6, 'SKKZSKGZZNKAYAGRVRGIK')
    'MEETMEATTHEUSUALPLACE'
    """

Challenge 3 Write decrypt so that it supports the extended collection of symbols you defined in Challenge 1.