Section3.3Project: Implementing cryptography in Python
Objectives
It is time to develop Python tools for some of our cryptographic methods.
Practice some cryptography by hand.
Implement DIANA, a Vigenère-style encryption formerly used by the NSA.
Extend the AlgoPerm class to be a more full-feature class of permutations.
Subsection3.3.1Demonstrating understanding
It takes a higher level of understanding to implement a simple algorithm as a code than it does to be able to perform the algorithm. To that end, it is important to practice ideas by hand on paper.
Activity3.1.Practice makes perfect.
Now that we have discussed some cryptographic techniques, it is time to show that you have mastered them. Work out this activity on paper.
(a)
The message CQNAN JWM KJLT JPJRW is encrypted with a shift cipher. Explain how you could find the amount of shift without using a computer.
(b)
Find the decrypted phrase corresponding to CQNAN JWM KJLT JPJRW, on paper. Henceforth we’ll refer to that key phrase as \(key\text{.}\)
(c)
The permutation with one-line notation \(a_0~a_1~a_2~\cdots~a_{n-1}\) can be rotated by \(k\) steps to obtain a new permutation with one-line notation \(a_k~a_{k+1}~a_{k+2}~\cdots~a_{n-1}~a_0~\cdots~a_{k-1}\text{.}\) All shift ciphers on an alphabet can be considered as rotations of one another; what is the simplest permutation of which a shift cipher can be considered a rotation? Explain why.
(d)
Suppose you want to use \(key\) as the key phrase for Playfair’s cipher. On paper, write the Playfair grid corresponding to \(key\text{.}\)
(e)
Remembering that the shift directions to decrypt using Playfair’s cipher are up and left instead of down and right, use \(key\) and Playfair’s cipher to decrypt the following message.
GDTESG HFGNER LTPODB HERARF GWHBTE QNDFEV
The spaces in that message do not correspond to actual spaces. They merely provide spacing to make the encrypted message easier to process by hand.
Performing Playfair’s cipher by hand is easy enough that a common use was in encrypting time-sensitive information: for instance, mortar fire on a location would commence in 15 minutes and so friendly personnel should vacate the area! By the time the enemy could decipher it, the information was no longer relevant.
Subsection3.3.2Implementing cryptography
Activity3.2.DIANA: Vigenère-style encryption.
Implementation of the Vigenère cipher is suprisingly easy; we’ll implement a slightly modified version called the DIANA cipher, used by the National Security Agency. The difference between the two is that the tabular rasa of the Vigenère cipher includes the identity permutation as the first column of the table, where in the DIANA system no letter of the key is represented by an identity permutation. The matrix of the DIANA cipher is as follows, in both alphabetix and arithmetic forms:
\begin{align*}
\small
\begin{array}{c|cccccccc}
\amp A \amp B \amp C \amp D \amp \cdots \amp Y \amp Z \\ \hline
A \amp Z \amp Y \amp X \amp W \amp \cdots \amp B \amp A \\
B \amp Y \amp X \amp W \amp V \amp \cdots \amp A \amp Z \\
C \amp X \amp W \amp V \amp U \amp \cdots \amp Z \amp Y \\
D \amp W \amp V \amp U \amp T \amp \cdots \amp Y \amp X \\
\vdots \amp \vdots \amp \vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\
Y \amp B \amp A \amp Z \amp Y \amp \cdots \amp D \amp C \\
Z \amp A \amp Z \amp Y \amp X \amp \cdots \amp C \amp B
\end{array} \amp\qquad
\small
\begin{array}{c|cccccccc}
~ \amp 0 \amp 1 \amp 2 \amp 3 \amp \cdots \amp 24 \amp 25 \\ \hline
0 \amp 25 \amp 24 \amp 23 \amp 22 \amp \cdots \amp 1 \amp 0 \\
1 \amp 24 \amp 23 \amp 22 \amp 21 \amp \cdots \amp 0 \amp 25 \\
2 \amp 23 \amp 22 \amp 21 \amp 20 \amp \cdots \amp 25 \amp 24 \\
3 \amp 22 \amp 21 \amp 20 \amp 19 \amp \cdots \amp 24 \amp 23 \\
\vdots \amp \vdots \amp \vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\
24 \amp 1 \amp 0 \amp 25 \amp 24 \amp \cdots \amp 3 \amp 2 \\
25 \amp 0 \amp 25 \amp 24 \amp 23 \amp \cdots \amp 2 \amp 1
\end{array}
\end{align*}
(a)
Use a nested for loop to create a list-of-lists containing the DIANA cipher. You’ll need to create a mathematical formula (involving remainders!) for the element of the \(m\)th row and \(k\)th column of the DIANA matrix, where \(k,m\in\set{0,\dotsc,25}\text{.}\)
diana = [ ]
for m in range( 26 ):
new_row = [ ]
for k in range( 26 ):
# CHANGE THIS to the correct value involving k and m
new_row.append( 0 )
diana.append( new_row )
print( diana )
(b)
Remember that ord('A') is 65, so to find the alphabet index of a capital letter stored as a string x would require using ord(x)-65. If we write \([D]_{i,j}\) to mean the entry in the \(i\)th row and \(j\)th column of the numerical DIANA matrix given above, then we now have from task (a) a mathematical formula for the value of \([D]_{i,j}\text{.}\) Since that value is the encrypted value of a message character with index i using key character j, we can build a DIANA cipher!
The first step to applying the DIANA cipher given a cryptographic key key and a message msg is to ensure that both message and key consist only of capital letters, and that the cryptographic key is either already as long as the message or has been extended by repetition to be at least as long as the message. Then the key and message can be converted to lists of integers, which then can be processed through the DIANA cipher. In order to decrypt a message, we must acknowledge that the DIANA cipher is that it is an involution: \(k=[D]_{i,j}\) if and only if \(i=[D]_{k,j}\text{.}\)
(i)
Write a detailed step-by-step algorithm on paper to explain the DIANA cipher.
(ii)
Create a function diana(key, msg) which performs the DIANA cipher using an input string key to encrypt and decrypt a message string msg, which works correctly whether msg is plaintext or ciphertext.
Now we should fill out the rest of our AlgoPerm class so we would have the tools to make a rotating-permutation cipher like Enigma; while fully implementing Enigma is beyond the scope of this project, it will be nice to have the tools to do so if you choose later to continue experimenting.
Activity3.3.Extending the AlgoPerm class.
(a)
Begin by copying AlgoPerm.py into a new file, called ExtendedAlgoPerm.py. All your changes to the AlgoPerm class will be performed in the ExtendedAlgoPerm.py file.
(b)
The __init__ method of your AlgoPerm class must first be extended to allow for the mapping to represent the disjoint cycle decomposition of the permutation of \(\set{0,1,2,\dotsc,k-1}\text{.}\) Here is a function which takes a tuple of tuples and converts it into an appropriate mapping dictionary.
def mapping_from_tuples(tuple_of_tuples):
bad_cycles = ValueError("Badly formatted tuple for cycle notation.")
map_dict = { }
for cyc in tuple_of_tuples:
if type(cyc) != tuple:
# It might still be bad input.
raise bad_cycles
else:
# So now we know it's a tuple of tuples.
for i,x in enumerate(cyc):
# i is the index and x is the element of the cycle
if x in map_dict.keys():
# This is a bad disjoint cycle notation! Not a bijection!
raise bad_cycles
try:
y = cyc[i+1]
# This will work unless we're at the end of the cycle already
except IndexError:
y = cyc[0]
# Now y = f(x), if f is this permutation.
map_dict[x] = y
# Once that's done we've walked through the whole support
# of the permutation, and now we have to make sure the
# fixed set is in the domain as well.
max_value = max(map_dict.keys())
for x in range(1 + max_value):
if x in map_dict.keys():
# We've already seen this x, move along.
continue
else:
map_dict[x] = x
# Now map_dict is the right dictionary to use to build an
# AlgoPerm, so rewrite this code into your own words!
return map_dict
In order to fix your __init__ file, this function must be rewritten! Do so.
(c)
Add a support method to the class, as follows:
def support(self):
supp = [ ]
for x in self.domain():
if x==self(x):
continue
else:
supp.append( x )
return set(supp)
(d)
Now that AlgoPerm.__init__ has been rewritten to allow input such as AlgoPerm( ((0,),(1,2,3),(4,),(5,6,7)) ), we must include code to display our permutations in disjoint cycle notation as well as returning them as tuples of tuples. We will introduce two new methods: cycle_tuples and cycle_string. Since the code for cycle_tuples involves some looping, we are going to add a neat feature to our class. Specifically, we will make use of a try:... except:... block so that no matter how many times we call the cycle_tuples method, the computation is only performed once.
(i)
Start the method as below. The lines beginning with #### will be changed.
def cycle_tuples(self):
'''Return self in disjoint cycle notation as a tuple of tuples. Single-element tuples
will be left off unless self is the identity, in which case this will return
((x,),), which is the tuple-of-tuples notation for the identity permutation when
x is the minimum element of self.domain()'''
try:
# If self has an attribute _cycle_tuples, this will work.
return self._cycle_tuples
# if not, it will raise an AttributeError, which is handled by...
except AttributeError:
# Since tuples are immutable, everything must be created as a list.
list_of_cycles = [ ]
# In order to create the cycle decomposition, we need an ordered list
# of all the domain elements which are not fixed by self, but in
# a mutable way. The following should work!
symbol_list = sorted(self.support())
#### This is the part you will work out in successive steps.
#### It will involve some looping so these three comments will
#### end up being removed and replaced by a nested while loop.
if list_of_cycles == [ ]:
# Inside this block, we see that self is the identity.
self._cycle_tuples = ( ( min(self.domain()), ), )
# To be nice for our next method, let's define the string version as well.
self._cycle_tuples = f"({min(self.domain())})"
else:
# Otherwise we've create a list containing tuples of each interesting
# cycle in the decomposition of self.
self._cycle_tuples = tuple(list_of_cycles)
# And we have to be a little more careful with the string version here
self._cycle_string = ''
for cyc in list_of_cycles:
self._cycle_string += str(cyc)
# Now we've defined the interesting attribute of self, so return it.
return self._cycle_tuples
(ii)
The algorithm for producing the disjoint cycle notation appeared in the first section of this chapter, in Example 2.1.30. It consists of a loop which puts elements of the domain into cycles, starting with the minimum element of the support, and proceeding until all of the support elements have either been placed into cycles or discarded; only the elements of the support need to be considered because disjoint cycle notation does not include single-element cycles unless the permutation is the identity!
The while loop must repeat as long as symbol_list is non-empty. The first task inside the while loop will be to remove the 0th-indexed element from symbol_list. This is exactly what the list.pop(index) method does: it returns the element in the specified index from the list, and simultaneously removes it from the list. Thus x = symbol_list.pop(0) will always assign the 0th-indexed element of symbol_list to x and shorten symbol_list by removing its 0th-indexed element.
Next a new list must be created representing the cycle which is about to be created: new_cycle = [ x ].
In order to create the cycle, we must iterate until the image of the last element appended to new_cycle is equal to the initial element of new_cycle. Since we have defined the __call__ method, we can check this as the condition of a while loop by testing to see if self( new_cycle[-1] ) differs from new_cycle[0]. So long as these two are unequal, we must assign a new variable y = self( new_cycle[-1] ), then remove y from symbol_list using the list.remove(...) method, and finally append y to the end of new_cycle.
Once that loop has completed, we simply check if new_cycle is a single-element list: if so, we skip to the next iteration of the outer while loop using continue. Otherwise, we append tuple( new_cycle ) to our list_of_cycles. This completes the nested while loop!
Convert that explanation into code and replace the #### lines.
(iii)
Having written the cycle_tuples method in such a way that its execution saves the _cycle_string attribute, we now have an easy way to write the cycle_string method, again using the try:... except AttributeError:... block.
def cycle_string(self):
try:
return self._cycle_string
except AttributeError:
# If the attribute wasn't defined, we need to run the cycle_tuples method,
# but we don't need its output so we'll just let it run without saving
# the returned value.
self.cycle_tuples()
return self._cycle_string
An alternative way to perform that same function safely is to use the builtin hasattr(value, attr_name) function; this function takes any object as value and any string as attr_name and returns True if value has an attribute with the same name as the contents of theattr_name string.
Implement cycle_string as a method using an if:... else:... block instead of try:... except:...
(e)Permutation rotations.
The key component of the Enigma machine is in its physical rotation of the permutations. The physical mechanism made this extremely straightforward, and we can use careful slicing to cause the same change. Suppose we defined sigma = AlgoPerm([5,4,3,0,1,2]), which is \(\sigma=(0,5,2,3)(1,4)\text{.}\) We want to define a method rotate(self, steps) which has the following outputs:
Table3.3.1.Rotations of the permutation \(\sigma=(0,5,2,3)(1,4)\)
