Chapter 12 - Hacking the Transposition Cipher
12
HACKING THE TRANSPOSITION CIPHER
“Ron Rivest, one of the inventors of RSA, thinks that restricting cryptography would be foolhardy: ‘It is poor policy to clamp down indiscriminately on a technology just because some criminals might be able to use it to their advantage.’”
— Simon Singh, The Code Book
In this chapter, we’ll use a brute-force approach to hack the transposition cipher. Of the thousands of keys that could possibly be associated with the transposition cipher, the correct key should be the only one that results in legible English. Using the detectEnglish.py module we wrote in Chapter 11, our transposition cipher hacker program will help us find the correct key.
Source Code of the Transposition Cipher Hacker Program
Open a new file editor window by selecting File▸New File. Enter the following code into the file editor and save it as transpositionHacker.py. As with previous programs, make sure the pyperclip.py module, the transpositionDecrypt.py module (Chapter 8), and the detectEnglish.py module and dictionary.txt file (Chapter 11) are in the same directory as the transpositionHacker.py file. Then press F5 to run the program.
transposition
Hacker.py
1. # Transposition Cipher Hacker
2. # https://www.nostarch.com/crackingcodes/ (BSD Licensed)
3.
4. import pyperclip, detectEnglish, transpositionDecrypt
5.
6. def main():
7. # You might want to copy & paste this text from the source code at
8. # https://www.nostarch.com/crackingcodes/:
9. myMessage = """AaKoosoeDe5 b5sn ma reno ora'lhlrrceey e enlh
na indeit n uhoretrm au ieu v er Ne2 gmanw,forwnlbsya apor tE.no
euarisfatt e mealefedhsppmgAnlnoe(c -or)alat r lw o eb nglom,Ain
one dtes ilhetcdba. t tg eturmudg,tfl1e1 v nitiaicynhrCsaemie-sp
ncgHt nie cetrgmnoa yc r,ieaa toesa- e a0m82e1w shcnth ekh
gaecnpeutaaieetgn iodhso d ro hAe snrsfcegrt NCsLc b17m8aEheideikfr
aBercaeu thllnrshicwsg etriebruaisss d iorr."""
10.
11. hackedMessage = hackTransposition(myMessage)
12.
13. if hackedMessage == None:
14. print('Failed to hack encryption.')
15. else:
16. print('Copying hacked message to clipboard:')
17. print(hackedMessage)
18. pyperclip.copy(hackedMessage)
19.
20.
21. def hackTransposition(message):
22. print('Hacking...')
23.
24. # Python programs can be stopped at any time
25. # by pressing Ctrl-C:
26. print('(Press Ctrl-C to quit at any time.)')
27.
28. # Brute-force by looping through every possible key:
29. for key in range(1, len(message)):
30. print('Trying key #%s...' % (key))
31.
32. decryptedText = transpositionDecrypt.decryptMessage(key, message)
33.
34. if detectEnglish.isEnglish(decryptedText):
35. # Ask user if this is the correct decryption:
36. print()
37. print('Possible encryption hack:')
38. print('Key %s: %s' % (key, decryptedText[:100]))
39. print()
40. print('Enter D if done, anything else to continue hacking:')
41. response = input('> ')
42.
43. if response.strip().upper().startswith('D'):
44. return decryptedText
45.
46. return None
47.
48. if __name__ == '__main__':
49. main()
Sample Run of the Transposition Cipher Hacker Program
When you run the transpositionHacker.py program, the output should look like this:
Hacking...
(Press Ctrl-C (on Windows) or Ctrl-D (on macOS and Linux) to quit at any time.)
Trying key #1...
Trying key #2...
Trying key #3...
Trying key #4...
Trying key #5...
Trying key #6...
Possible encryption hack:
Key 6: Augusta Ada King-Noel, Countess of Lovelace (10 December 1815 - 27
November 1852) was an English mat
Enter D if done, anything else to continue hacking:
> D
Copying hacked message to clipboard:
Augusta Ada King-Noel, Countess of Lovelace (10 December 1815 - 27 November
1852) was an English mathematician and writer, chiefly known for her work on
Charles Babbage's early mechanical general-purpose computer, the Analytical
Engine. Her notes on the engine include what is recognised as the first
algorithm intended to be carried out by a machine. As a result, she is often
regarded as the first computer programmer.
After trying key #6, the program returns a snippet of the decrypted message for the user to confirm that it has found the right key. In this example, the message looks promising. When the user confirms the decryption is correct by entering D, the program returns the entire hacked message. You can see it’s a biographical note about Ada Lovelace. (Her algorithm for calculating Bernoulli numbers, devised in 1842 and 1843, made her the first computer programmer.) If the decryption is a false positive, the user can press anything else, and the program will continue to try other keys.
Run the program again and skip the correct decryption by pressing anything other than D. The program assumes that it didn’t find the correct decryption and continues its brute-force approach through the other possible keys.
--snip--
Trying key #417...
Trying key #418...
Trying key #419...
Failed to hack encryption.
Eventually, the program runs through all the possible keys and then gives up, informing the user that it was unable to hack the ciphertext.
Let’s take a closer look at the source code to see how the program works.
Importing the Modules
The first few lines of the code tell the user what this program will do. Line 4 imports several modules that we’ve written or seen in previous chapters: pyperclip.py, detectEnglish.py, and transpositionDecrypt.py.
1. # Transposition Cipher Hacker
2. # https://www.nostarch.com/crackingcodes/ (BSD Licensed)
3.
4. import pyperclip, detectEnglish, transpositionDecrypt
The transposition cipher hacker program, containing approximately 50 lines of code, is fairly short because much of it exists in other programs that we’re using as modules.
Multiline Strings with Triple Quotes
The myMessage variable stores the ciphertext we’re trying to hack. Line 9 stores a string value that begins and ends with triple quotes. Notice that it’s a very long string.
6. def main():
7. # You might want to copy & paste this text from the source code at
8. # https://www.nostarch.com/crackingcodes/:
9. myMessage = """AaKoosoeDe5 b5sn ma reno ora'lhlrrceey e enlh
na indeit n uhoretrm au ieu v er Ne2 gmanw,forwnlbsya apor tE.no
euarisfatt e mealefedhsppmgAnlnoe(c -or)alat r lw o eb nglom,Ain
one dtes ilhetcdba. t tg eturmudg,tfl1e1 v nitiaicynhrCsaemie-sp
ncgHt nie cetrgmnoa yc r,ieaa toesa- e a0m82e1w shcnth ekh
gaecnpeutaaieetgn iodhso d ro hAe snrsfcegrt NCsLc b17m8aEheideikfr
aBercaeu thllnrshicwsg etriebruaisss d iorr."""
Triple quote strings are also called multiline strings because they span multiple lines and can contain line breaks within them. Multiline strings are useful for putting large strings into a program’s source code and because single and double quotes don’t need to be escaped within them. To see an example of a multiline string, enter the following into the interactive shell:
>>> spam = """Dear Alice,
Why did you dress up my hamster in doll clothing?
I look at Mr. Fuzz and think, "I know this was Alice's doing."
Sincerely,
Brienne"""
>>> print(spam)
Dear Alice,
Why did you dress up my hamster in doll clothing?
I look at Mr. Fuzz and think, "I know this was Alice's doing."
Sincerely,
Brienne
Notice that this string value, like our ciphertext string, spans multiple lines. Everything after the opening triple quotes will be interpreted as part of the string until the program reaches the triple quotes ending it. You can make multiline strings using either three double-quote characters or three single-quote characters.
Displaying the Results of Hacking the Message
The ciphertext-hacking code exists inside the hackTransposition() function, which is called on line 11 and which we’ll define on line 21. This function takes one string argument: the encrypted ciphertext message we’re trying to hack. If the function can hack the ciphertext, it returns a string of the decrypted text. Otherwise, it returns the None value.
11. hackedMessage = hackTransposition(myMessage)
12.
13. if hackedMessage == None:
14. print('Failed to hack encryption.')
15. else:
16. print('Copying hacked message to clipboard:')
17. print(hackedMessage)
18. pyperclip.copy(hackedMessage)
Line 11 calls the hackTransposition() function to return the hacked message if the attempt is successful or the None value if the attempt is unsuccessful, and it stores the returned value in hackedMessage.
Lines 13 and 14 tell the program what to do if the function is unable to hack the ciphertext. If None was stored in hackedMessage, the program lets the user know by printing that it was unable to break the encryption on the message.
The next four lines show what the program does if the function is able to hack the ciphertext. Line 17 prints the decrypted message, and line 18 copies it to the clipboard. However, for this code to work, we also need to define the hackTransposition() function, which we’ll do next.
Getting the Hacked Message
The hackTransposition() function starts with a couple print() statements.
21. def hackTransposition(message):
22. print('Hacking...')
23.
24. # Python programs can be stopped at any time by pressing
25. # Ctrl-C (on Windows) or Ctrl-D (on macOS and Linux):
26. print('(Press Ctrl-C (on Windows) or Ctrl-D (on macOS and Linux) to
quit at any time.)')
Because the program can try many keys, the program displays a message telling the user that the hacking has started and that it might take a moment to finish the process. The print() call on line 26 tells the user to press ctrl-C (on Windows) or ctrl-D (on macOS and Linux) to exit the program at any point. You can actually press these keys to exit any running Python program.
The next couple lines tell the program which keys to loop through by specifying the range of possible keys for the transposition cipher:
28. # Brute-force by looping through every possible key:
29. for key in range(1, len(message)):
30. print('Trying key #%s...' % (key))
The possible keys for the transposition cipher range between 1 and the length of the message. The for loop on line 29 runs the hacking part of the function with each of these keys. Line 30 uses string interpolation to print the key currently being tested using string interpolation to provide feedback to the user.
Using the decryptMessage() function in the transpositionDecrypt.py program that we’ve already written, line 32 gets the decrypted output from the current key being tested and stores it in the decryptedText variable:
32. decryptedText = transpositionDecrypt.decryptMessage(key, message)
The decrypted output in decryptedText will be English only if the correct key was used. Otherwise, it will appear as garbage text.
Then the program passes the string in decryptedText to the detectEnglish.isEnglish() function we wrote in Chapter 11 and prints part of decryptedText, the key used, and instructions for the user:
34. if detectEnglish.isEnglish(decryptedText):
35. # Ask user if this is the correct decryption:
36. print()
37. print('Possible encryption hack:')
38. print('Key %s: %s' % (key, decryptedText[:100]))
39. print()
40. print('Enter D if done, anything else to continue hacking:')
41. response = input('> ')
But just because detectEnglish.isEnglish() returns True and moves the execution to line 35 doesn’t mean the program has found the correct key. It could be a false positive, meaning the program detected some text as English that is actually garbage text. To make sure, line 38 gives a preview of the text so the user can confirm that the text is indeed English. It uses the slice decryptedText[:100] to print out the first 100 characters of decryptedText.
The program pauses when line 41 executes, waits for the user to enter either D or anything else, and then stores this input as a string in response.
The strip() String Method
When a program gives a user specific instructions but the user doesn’t follow them exactly, an error results. When the transpositionHacker.py program prompts the user to enter D to confirm the hacked message, it means the program won’t accept any input other than D. If a user enters an extra space or character along with D, the program won’t accept it. Let’s look at how to use the strip() string method to make the program accept other inputs as long as they’re similar enough to D.
The strip() string method returns a version of the string with any whitespace characters at the beginning and end of the string stripped out. The whitespace characters are the space character, the tab character, and the newline character. Enter the following into the interactive shell to see how this works:
>>> ' Hello'.strip()
'Hello'
>>> 'Hello '.strip()
'Hello'
>>> ' Hello World '.strip()
'Hello World'
In this example, strip() removes the space characters at the beginning or the end of the first two strings. If a string like ' Hello World ' includes spaces at the beginning and end of the string, the method removes them from both sides but doesn’t remove any spaces between other characters.
The strip() method can also have a string argument passed to it that tells the method to remove characters other than whitespace from the beginning and end of the string. To see an example, enter the following into the interactive shell:
>>> 'aaaaaHELLOaa'.strip('a')
'HELLO'
>>> 'ababaHELLObaba'.strip('ab')
'HELLO'
>>> 'abccabcbacbXYZabcXYZacccab'.strip('abc')
'XYZabcXYZ'
Notice that passing the string arguments 'a' and 'ab' removes these characters when they occur at the beginning or end of the string. However, strip() doesn’t remove characters embedded in the middle of the string. As you can see in the third example, the string 'abc' remains in 'XYZabcXYZ'.
Applying the strip() String Method
Let’s return to the source code in transpositionHacker.py to see how to apply strip() in the program. Line 43 sets a condition using the if statement to give the user some input flexibility:
43. if response.strip().upper().startswith('D'):
44. return decryptedText
If the condition for the statement were simply response == 'D', the user would have to enter D exactly and nothing else to end the program. For example, if the user enters 'd', ' D', or 'Done', the condition would be False and the program would continue checking other keys instead of returning the hacked message.
To avoid this issue, the string in response removes whitespace from the start or end of the string with the call to strip(). Then the string that response.strip() evaluates to has the upper() method called on it. Whether the user enters 'd' or 'D', the string returned from upper() will always be capitalized as 'D'. Adding flexibility in the type of input the program can accept makes it easier to use.
To make the program accept user input that starts with 'D' but is a full word, we use startswith() to check only the first letter. For example, if the user inputs ' done' as response, the whitespace would be stripped and then the string 'done' would be passed to upper(). After upper() capitalizes the whole string to 'DONE', the string is passed to startswith(), which returns True because the string does start with the substring 'D'.
If the user indicates that the decrypted string is correct, the function hackTransposition() on line 44 returns the decrypted text.
Failing to Hack the Message
Line 46 is the first line after the for loop that began on line 29:
46. return None
If the program execution reaches this point, it means the program never reached the return statement on line 44, which would happen if the correctly decrypted text was never found for any of the keys that were tried. In that case, line 46 returns the None value to indicate that the hacking failed.
Calling the main() Function
Lines 48 and 49 call the main() function if this program was run by itself rather than being imported by another program using its hackTransposition() function:
48. if __name__ == '__main__':
49. main()
Remember that the __name__ variable is set by Python. The main() function will not be called if transpositionHacker.py is imported as a module.
Summary
Like Chapter 6, this chapter was short because most of the code was already written in other programs. Our hacking program can use functions from other programs by importing them as modules.
You learned how to use triple quotes to include a string value that spans multiple lines in the source code. You also learned that the strip() string method is useful for removing whitespace or other characters from the beginning or end of a string.
Using the detectEnglish.py program saved us a lot of time we would have had to spend manually inspecting every decrypted output to see if it was English. It allowed us to use the brute-force technique to hack a cipher that has thousands of possible keys.