Hacking Secret Ciphers with Python (2013)

Chapter 9: DECRYPTING WITH THE TRANSPOSITION CIPHER

Topics Covered In This Chapter:

· Decrypting with the transposition cipher

· The math.ceil(), math.floor() and round() functions

· The and and or boolean operators

· Truth tables

“When stopping a terrorist attack or seeking to recover a kidnapped child, encountering encryption may mean the difference between success and catastrophic failures.”

Attorney General Janet Reno, September 1999

“Even the Four Horsemen of Kid Porn, Dope Dealers, Mafia and Terrorists don’t worry me as much as totalitarian governments. It’s been a long century, and we've had enough of them.”

Bruce Sterling, 1994 Computers, Freedom, and Privacy conference

Unlike the Caesar cipher, the decryption process for the transposition cipher is very different from the encryption process. In this chapter we will create a separate program, transpositionDecrypt.py, to handle decryption.

Decrypting with the Transposition Cipher on Paper

Let’s pretend we send the ciphertext “Cenoonommstmme oo snnio. s s c” to a friend (and she already knows that the secret key is 8). The first step for her to decrypt the ciphertext is to calculate how many boxes she needs to draw. To find this amount, divide the length of the ciphertext message by the key and round up. The length of our ciphertext is 30 characters (exactly the same as the plaintext) and the key is 8. So calculate 30 divided by 8 to get 3.75.

3.75 rounds up to 4. This means we want to draw a grid of boxes with 4 columns (the number we just calculated) and 8 rows (the key). It will look like this:

(Note that if the length divided by the key was a whole number, like in 30 / 5 = 6.0, then 6.0 would not “round up” to 7.)

The second thing we need to calculate is how many boxes on the rightmost column to shade in. Take the total number of boxes (32) and subtract the length of the ciphertext (30). 32 – 30 = 2, so shade in the bottom 2 boxes on the rightmost column:

Then start filling in the boxes with one character of the ciphertext per box. Start at the top left and go right, just like we did when we were encrypting. The ciphertext is “Cenoonommstmme oo snnio. s s c”, and so “Ceno” goes in the first row, then “onom” in the second row, and so on. After we are done, the boxes will look like this (where the (s) represents a space):

Our friend who received the ciphertext will see that if she reads the text going down the columns, the original plaintext has been restored: “Common sense is not so common.”

The steps for decrypting are:

1. Calculate the number of columns you will have by taking the length of the message and dividing by the key, then rounding up.

2. Draw out a number of boxes. The number of columns was calculated in step 1. The number of rows is the same as the key.

3. Calculate the number of boxes to shade in by taking the number of boxes (this is the number of rows and columns multiplied) and subtracting the length of the ciphertext message.

4. Shade in the number of boxes you calculated in step 3 at the bottom of the rightmost column.

5. Fill in the characters of the ciphertext starting at the top row and going from left to right. Skip any of the shaded boxes.

6. Get the plaintext by reading from the leftmost column going from top to bottom, and moving over to the top of the next column.

Note that if you use a different key, you will be drawing out the wrong number of rows. Even if you follow the other steps in the decryption process correctly, the plaintext will come out looking like random garbage (just like when you use the wrong key with the Caesar cipher).

Practice Exercises, Chapter 9, Set A

Practice exercises can be found at http://invpy.com/hackingpractice9A.

A Transposition Cipher Decryption Program

Open a new file editor window and type out the following code in it. Save this program as transpositionDecrypt.py.

Source Code of the Transposition Cipher Decryption Program

Open a new file editor window by clicking on File ► New Window. Type in the following code into the file editor, and then save it as transpositionDecrypt.py. Press F5 to run the program. Note that first you will need to download the pyperclip.py module and place this file in the same directory as the transpositionDecrypt.py file. You can download this file from http://invpy.com/pyperclip.py.

Source code for transpositionDecrypt.py

1. # Transposition Cipher Decryption

2. # http://inventwithpython.com/hacking (BSD Licensed)

3.

4. import math, pyperclip

5.

6. def main():

7. myMessage = 'Cenoonommstmme oo snnio. s s c'

8. myKey = 8

9.

10. plaintext = decryptMessage(myKey, myMessage)

11.

12. # Print with a | (called "pipe" character) after it in case

13. # there are spaces at the end of the decrypted message.

14. print(plaintext + '|')

15.

16. pyperclip.copy(plaintext)

17.

18.

19. def decryptMessage(key, message):

20. # The transposition decrypt function will simulate the "columns" and

21. # "rows" of the grid that the plaintext is written on by using a list

22. # of strings. First, we need to calculate a few values.

23.

24. # The number of "columns" in our transposition grid:

25. numOfColumns = math.ceil(len(message) / key)

26. # The number of "rows" in our grid will need:

27. numOfRows = key

28. # The number of "shaded boxes" in the last "column" of the grid:

29. numOfShadedBoxes = (numOfColumns * numOfRows) - len(message)

30.

31. # Each string in plaintext represents a column in the grid.

32. plaintext = [''] * numOfColumns

33.

34. # The col and row variables point to where in the grid the next

35. # character in the encrypted message will go.

36. col = 0

37. row = 0

38.

39. for symbol in message:

40. plaintext[col] += symbol

41. col += 1 # point to next column

42.

43. # If there are no more columns OR we're at a shaded box, go back to

44. # the first column and the next row.

45. if (col == numOfColumns) or (col == numOfColumns - 1 and row >= numOfRows - numOfShadedBoxes):

46. col = 0

47. row += 1

48.

49. return ''.join(plaintext)

50.

51.

52. # If transpositionDecrypt.py is run (instead of imported as a module) call

53. # the main() function.

54. if __name__ == '__main__':

55. main()

When you run the above program, it produces this output:

Common sense is not so common.|

If you want to decrypt a different message, or use a different key, change the value assigned to the myMessage and myKey variables on lines 5 and 6.

How the Program Works

transpositionDecrypt.py

1. # Transposition Cipher Decryption

2. # http://inventwithpython.com/hacking (BSD Licensed)

3.

4. import math, pyperclip

5.

6. def main():

7. myMessage = 'Cenoonommstmme oo snnio. s s c'

8. myKey = 8

9.

10. plaintext = decryptMessage(myKey, myMessage)

11.

12. # Print with a | (called "pipe" character) after it in case

13. # there are spaces at the end of the decrypted message.

14. print(plaintext + '|')

15.

16. pyperclip.copy(plaintext)

The first part of the program is very similar to the first part of transpositionEncrypt.py. The pyperclip module is imported along with a different module named math. If you separate the module names with commas, you can import multiple modules with one import statement.

The main() function creates variables named myMessage and myKey, and then calls the decryption function decryptMessage(). The return value of this function is the decrypted plaintext of the ciphertext and key that we passed it. This is stored in a variable named plaintext, which is then printed to the screen (with a pipe character at the end in case there are spaces at the end of the message) and copied to the clipboard.

transpositionDecrypt.py

19. def decryptMessage(key, message):

Look at the six steps to decrypting from earlier in this chapter. For example, if we are decrypting “Cenoonommstmme oo snnio. s s c” (which has 30 characters) with the key 8, then the final set of boxes will look like this:

The decryptMessage() function implements each of the decryption steps as Python code.

The math.ceil(), math.floor() and round() Functions

When you divide numbers using the / operator, the expression returns a floating point number (that is, a number with a decimal point). This happens even if the number divides evenly. For example, 21 / 7 will evaluate to 3.0, not 3.

>>> 21 / 7

3.0

>>>

This is useful because if a number does not divide evenly, the numbers after the decimal point will be needed. For example, 22 / 5 evaluates to 4.4:

>>> 22 / 5

4.4

>>>

(If the expression 22 / 5 evaluates to 4 instead of 4.4, then you are using version 2 of Python instead of version 3. Please go to the http://python.org website and download and install Python 3.)

If you want to round this number to the nearest integer, you can use the round() function. Type the following into the interactive shell:

>>> round(4.2)

4

>>> round(4.5)

4

>>> round(4.9)

5

>>> round(5.0)

5

>>> round(22 / 5)

4

>>>

If you only want to round up then use the math.ceil() function, which stands for “ceiling”. If you only want to round down then use the math.floor() function. These functions exist in the math module, so you will need to import the math module before calling them. Type the following into the interactive shell:

>>> import math

>>> math.floor(4.0)

4

>>> math.floor(4.2)

4

>>> math.floor(4.9)

4

>>> math.ceil(4.0)

4

>>> math.ceil(4.2)

5

>>> math.ceil(4.9)

5

>>>

The math.ceil() function will implement step 1 of the transposition decryption.

transpositionDecrypt.py

19. def decryptMessage(key, message):

20. # The transposition decrypt function will simulate the "columns" and

21. # "rows" of the grid that the plaintext is written on by using a list

22. # of strings. First, we need to calculate a few values.

23.

24. # The number of "columns" in our transposition grid:

25. numOfColumns = math.ceil(len(message) / key)

26. # The number of "rows" in our grid will need:

27. numOfRows = key

28. # The number of "shaded boxes" in the last "column" of the grid:

29. numOfShadedBoxes = (numOfColumns * numOfRows) - len(message)

Line 25 calculates the number of columns (step 1 of decrypting) by dividing len(message) by the integer in key. This value is passed to the math.ceil() function, and that return value is stored in numOfColumns.

Line 27 calculates the number of rows (step 2 of decrypting), which is the integer stored in key. This value gets stored in the variable numOfRows.

Line 29 calculates the number of shaded boxes in the grid (step 3 of decrypting), which will be the number of columns times rows, minus the length of the message.

If we are decrypting “Cenoonommstmme oo snnio. s s c” with key 8, numOfColumns will be set to 4, numOfRows will be set to 8, and numOfShadedBoxes will be set to 2.

transpositionDecrypt.py

31. # Each string in plaintext represents a column in the grid.

32. plaintext = [''] * numOfColumns

Just like the encryption program had a variable named ciphertext that was a list of strings to represent the grid of ciphertext, the decryptMessage() function will have a variable named plaintext that is a list of strings. These strings start off as blank strings, and we will need one string for each column of the grid. Using list replication, we can multiply a list of one blank string by numOfColumns to make a list of several blank strings.

(Remember that each function call has its own local scope. The plaintext in decryptMessage() exists in a different local scope than the plaintext variable in main(), so they are two different variables that just happen to have the same name.)

Remember that the grid for our 'Cenoonommstmme oo snnio. s s c' example looks like this:

The plaintext variable will have a list of strings. Each string in the list is a single column of this grid. For this decryption, we want plaintext to end up with this value:

>>> plaintext = ['Common s', 'ense is ', 'not so c', 'ommon.']

>>> plaintext[0]

'Common s'

That way, we can join all the list’s strings together to get the 'Common sense is not so common.' string value to return.

transpositionDecrypt.py

34. # The col and row variables point to where in the grid the next

35. # character in the encrypted message will go.

36. col = 0

37. row = 0

38.

39. for symbol in message:

The col and row variables will track the column and row where the next character in message should go. We will start these variables at 0. Line 39 will start a for loop that iterates over the characters in the message string. Inside this loop the code will adjust the col and row variables so that we concatenate symbol to the correct string in the plaintext list.

transpositionDecrypt.py

40. plaintext[col] += symbol

41. col += 1 # point to next column

As the first step in this loop we concatenate symbol to the string at index col in the plaintext list. Then we add 1 to col (that is, we increment col) on line 41 so that on the next iteration of the loop, symbol will be concatenated to the next string.

The and and or Boolean Operators

The Boolean operators and and or can help us form more complicated conditions for if and while statements. The and operator connects two expressions and evaluates to True if both expressions evaluate to True. The or operator connects two expressions and evaluates to True if one or both expressions evaluate to True. Otherwise these expressions evaluate to False. Type the following into the interactive shell:

>>> 10 > 5 and 2 < 4

True

>>> 10 > 5 and 4 != 4

False

>>>

The first expression above evaluates to True because the two expressions on the sides of the and operator both evaluate to True. This means that the expression 10 > 5 and 2 < 4 evaluates to True and True, which in turn evaluates to True.

However, for the second above expression, although 10 > 5 evaluates to True the expression 4 != 4 evaluates to False. This means the whole expression evaluates to True and False. Since both expressions have to be True for the and operator to evaluate to True, instead they evaluate to False.

Type the following into the interactive shell:

>>> 10 > 5 or 4 != 4

True

>>> 10 < 5 or 4 != 4

False

>>>

For the or operator, only one of the sides must be True for the or operator to evaluate them both to True. This is why 10 > 5 or 4 != 4 evaluates to True. However, because both the expression 10 < 5 and the expression 4 != 4 are both False, this makes the second above expression evaluate to False or False, which in turn evaluates to False.

The third Boolean operator is not. The not operator evaluates to the opposite Boolean value of the value it operates on. So not True is False and not False is True. Type the following into the interactive shell:

>>> not 10 > 5

False

>>> not 10 < 5

True

>>> not False

True

>>> not not False

False

>>> not not not not not False

True

>>>

Practice Exercises, Chapter 9, Set B

Practice exercises can be found at http://invpy.com/hackingpractice9B.

Truth Tables

If you ever forget how the Boolean operators work, you can look at these charts, which are called truth tables:

Table 6-1: The and operator's truth table.

Table 6-2: The or operator's truth table.

Table 6-3: The not operator's truth table.

The and and or Operators are Shortcuts

Just like for loops let us do the same thing as while loops but with less code, the and and or operators let us shorten our code also. Type in the following into the interactive shell. Both of these bits of code do the same thing:

>>> if 10 > 5:

... if 2 < 4:

... print('Hello!')

...

Hello!

>>>

>>> if 10 > 5 and 2 < 4:

... print('Hello!')

...

Hello!

>>>

So you can see that the and operator basically takes the place of two if statements (where the second if statement is inside the first if statement’s block.)

You can also replace the or operator with an if and elif statement, though you will have to copy the code twice. Type the following into the interactive shell:

>>> if 4 != 4:

... print('Hello!')

... elif 10 > 5:

... print('Hello!')

...

Hello!

>>>

>>> if 4 != 4 or 10 > 5:

... print('Hello!')

...

Hello!

>>>

Order of Operations for Boolean Operators

Just like the math operators have an order of operations, the and, or, and not operators also have an order of operations: first not, then and, and then or. Try typing the following into the interactive shell:

>>> not False and False # not False evaluates first

True

>>> not (False and False) # (False and False) evaluates first

False

Back to the Code

transpositionDecrypt.py

43. # If there are no more columns OR we're at a shaded box, go back to

44. # the first column and the next row.

45. if (col == numOfColumns) or (col == numOfColumns - 1 and row >= numOfRows - numOfShadedBoxes):

46. col = 0

47. row += 1

There are two cases where we want to reset col back to 0 (so that on the next iteration of the loop, symbol is added to the first string in the list in plaintext). The first is if we have incremented col past the last index in plaintext. In this case, the value in col will be equal to numOfColumns. (Remember that the last index in plaintext will be numOfColumns minus one. So when col is equal to numOfColumns, it is already past the last index.)

The second case is if both col is at the last index and the row variable is pointing to a row that has a shaded box in the last column. Here’s the complete decryption grid with the column indexes along the top and the row indexes down the side:

You can see that the shaded boxes are in the last column (whose index will be numOfColumns - 1) and rows 6 and 7. To have our program calculate which row indexes are shaded, we use the expression row >= numOfRows - numOfShadedBoxes. If this expression is True, and col is equal tonumOfColumns - 1, then we know that we want to reset col to 0 for the next iteration.

These two cases are why the condition on line 45 is (col == numOfColumns) or (col == numOfColumns - 1 and row >= numOfRows - numOfShadedBoxes). That looks like a big, complicated expression but remember that you can break it down into smaller parts. The block of code that executes will change col back to the first column by setting it to 0. We will also increment the row variable.

transpositionDecrypt.py

49. return ''.join(plaintext)

By the time the for loop on line 39 has finished looping over every character in message, the plaintext list’s strings have been modified so that they are now in the decrypted order (if the correct key was used, that is). The strings in the plaintext list are joined together (with a blank string in between each string) by the join() string method. The string that this call to join() returns will be the value that our decryptMessage() function returns.

For our example decryption, plaintext will be ['Common s', 'ense is ', 'not so c', 'ommon.'], so ''.join(plaintext) will evaluate to 'Common sense is not so common.'.

transpositionDecrypt.py

52. # If transpositionDecrypt.py is run (instead of imported as a module) call

53. # the main() function.

54. if __name__ == '__main__':

55. main()

The first line that our program runs after importing modules and executing the def statements is the if statement on line 54. Just like in the transposition encryption program, we check if this program has been run (instead of imported by a different program) by checking if the special__name__ variable is set to the string value '__main__'. If so, we execute the main() function.

Practice Exercises, Chapter 9, Set C

Practice exercises can be found at http://invpy.com/hackingpractice9C.

Summary

That’s it for the decryption program. Most of the program is in the decryptMessage() function. We can see that our programs can encrypt and decrypt the message “Common sense is not so common.” with the key 8. But we should try several other messages and keys to see that a message that is encrypted and then decrypted will result in the same thing as the original message. Otherwise, we know that either the encryption code or the decryption code doesn’t work.

We could start changing the key and message variables in our transpositionEncrypt.py and transpositionDecrypt.py and then running them to see if it works. But instead, let’s automate this by writing a program to test our program.