Hacking Secret Ciphers with Python (2013)
Chapter 13: HACKING THE TRANSPOSITION CIPHER
Topics Covered In This Chapter:
· Multi-line Strings with Triple Quotes
· The strip() String Method
To hack the transposition cipher, we will use a brute-force approach. Of the thousands of keys, the correct key is most likely that only one that will result in readable English. We developed English-detection code in the last chapter so the program can realize when it has found the correct key.
Source Code of the Transposition Cipher Hacker 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 transpositionHacker.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 transpositionHacker.py file. You can download this file from http://invpy.com/pyperclip.py.
Source code for transpositionHacker.py
1. # Transposition Cipher Hacker
2. # http://inventwithpython.com/hacking (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. # http://invpy.com/transpositionHacker.py
9. myMessage = """Cb b rssti aieih rooaopbrtnsceee er es no npfgcwu plri
ch nitaalr eiuengiteehb(e1 hilincegeoamn fubehgtarndcstudmd nM eu eacBoltaetee
oinebcdkyremdteghn.aa2r81a condari fmps" tad l t oisn sit u1rnd stara nvhn fs
edbh ee,n e necrg6 8nmisv l nc muiftegiitm tutmg cm shSs9fcie ebintcaets h a
ihda cctrhe ele 1O7 aaoem waoaatdahretnhechaopnooeapece9etfncdbgsoeb uuteitgna.
rteoh add e,D7c1Etnpneehtn beete" evecoal lsfmcrl iu1cifgo ai. sl1rchdnheev sh
meBd ies e9t)nh,htcnoecplrrh ,ide hmtlme. pheaLem,toeinfgn t e9yce da' eN eMp a
ffn Fc1o ge eohg dere.eec s nfap yox hla yon. lnrnsreaBoa t,e eitsw il ulpbdofg
BRe bwlmprraio po droB wtinue r Pieno nc ayieeto'lulcih sfnc ownaSserbereiaSm
-eaiah, nnrttgcC maciiritvledastinideI nn rms iehn tsigaBmuoetcetias rn"""
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 by pressing Ctrl-C (on
25. # Windows) or Ctrl-D (on Mac and Linux)
26. print('(Press Ctrl-C or Ctrl-D 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. # Check with user to see if the decrypted key has been found.
36. print()
37. print('Possible encryption hack:')
38. print('Key %s: %s' % (key, decryptedText[:100]))
39. print()
40. print('Enter D for done, or just press Enter 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 Breaker Program
When you run this program, the output will look this:
Hacking...
(Press Ctrl-C or Ctrl-D to quit at any time.)
Trying key #1...
Trying key #2...
Trying key #3...
Trying key #4...
Trying key #5...
Trying key #6...
Trying key #7...
Trying key #8...
Trying key #9...
Trying key #10...
Possible encryption hack:
Key 10: Charles Babbage, FRS (26 December 1791 - 18 October 1871) was an English mathematician, philosopher,
Enter D for done, or just press Enter to continue hacking:
> D
Copying hacked message to clipboard:
Charles Babbage, FRS (26 December 1791 - 18 October 1871) was an English mathematician, philosopher, inventor and mechanical engineer who originated the concept of a programmable computer. Considered a "father of the computer", Babbage is credited with inventing the first mechanical computer that eventually led to more complex designs. Parts of his uncompleted mechanisms are on display in the London Science Museum. In 1991, a perfectly functioning difference engine was constructed from Babbage's original plans. Built to tolerances achievable in the 19th century, the success of the finished engine indicated that Babbage's machine would have worked. Nine years later, the Science Museum completed the printer Babbage had designed for the difference engine.
When the hacker program has found a likely correct decryption, it will pause and wait for the user to press “D” and then Enter. If the decryption is a false positive, the user can just press Enter and the program will continue to try other keys.
Run the program again and skip the correct decryption by just pressing Enter. The program assumes that it was not a correct decryption and continues brute-forcing through the other possible keys. Eventually the program runs through all the possible keys and then gives up, telling the user that it was unable to hack the ciphertext:
Trying key #757...
Trying key #758...
Trying key #759...
Trying key #760...
Trying key #761...
Failed to hack encryption.
How the Program Works
transpositionHacker.py
1. # Transposition Cipher Hacker
2. # http://inventwithpython.com/hacking (BSD Licensed)
3.
4. import pyperclip, detectEnglish, transpositionDecrypt
The transposition hacker program is under 50 lines of code because much of it exists in other programs. Several modules are imported on line 4.
Multi-line Strings with Triple Quotes
transpositionHacker.py
6. def main():
7. # You might want to copy & paste this text from the source code at
8. # http://invpy.com/transpositionHacker.py
9. myMessage = """Cb b rssti aieih rooaopbrtnsceee er es no npfgcwu plri ch nitaalr eiuengiteehb(e1 hilincegeoamn fubehgtarndcstudmd nM eu eacBoltaetee
oinebcdkyremdteghn.aa2r81a condari fmps" tad l t oisn sit u1rnd stara nvhn fs
edbh ee,n e necrg6 8nmisv l nc muiftegiitm tutmg cm shSs9fcie ebintcaets h a
ihda cctrhe ele 1O7 aaoem waoaatdahretnhechaopnooeapece9etfncdbgsoeb uuteitgna.
rteoh add e,D7c1Etnpneehtn beete" evecoal lsfmcrl iu1cifgo ai. sl1rchdnheev sh
meBd ies e9t)nh,htcnoecplrrh ,ide hmtlme. pheaLem,toeinfgn t e9yce da' eN eMp a
ffn Fc1o ge eohg dere.eec s nfap yox hla yon. lnrnsreaBoa t,e eitsw il ulpbdofg
BRe bwlmprraio po droB wtinue r Pieno nc ayieeto'lulcih sfnc ownaSserbereiaSm
-eaiah, nnrttgcC maciiritvledastinideI nn rms iehn tsigaBmuoetcetias rn"""
The ciphertext to be hacked is stored in the myMessage variable. Line 9 has a string value that begins and ends with triple quotes. These strings do not have to have literal single and double quotes escaped inside of them. Triple quote strings are also called multi-line strings, because they can also contain actual newlines within them. Try typing 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,
Bob"""
>>> 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,
Bob
>>>
Notice that this string value can span over multiple lines. Everything after the opening triple quotes will be interpreted as part of the string until it reaches triple quotes ending it. Multi-line strings can either use three double quote characters or three single quote characters.
Multi-line strings are useful for putting very large strings into the source code for a program, which is why it is used on line 9 to store the ciphertext to be broken.
Back to the Code
transpositionHacker.py
11. hackedMessage = hackTransposition(myMessage)
The ciphertext hacking code exists inside the hackTransposition() function. This function takes one string argument: the encrypted ciphertext message to be broken. If the function can hack the ciphertext, it returns a string of the decrypted text. Otherwise, it returns the None value. This value is stored in the hackedMessage variable.
transpositionHacker.py
13. if hackedMessage == None:
14. print('Failed to hack encryption.')
If None was stored in hackedMessage, the program prints that it was unable to break the encryption on the message.
transpositionHacker.py
15. else:
16. print('Copying hacked message to clipboard:')
17. print(hackedMessage)
18. pyperclip.copy(hackedMessage)
Otherwise, the text of the decrypted message is printed to the screen on line 17 and also copied to the clipboard on line 18.
transpositionHacker.py
21. def hackTransposition(message):
22. print('Hacking...')
23.
24. # Python programs can be stopped at any time by pressing Ctrl-C (on
25. # Windows) or Ctrl-D (on Mac and Linux)
26. print('(Press Ctrl-C or Ctrl-D to quit at any time.)')
Because there are many keys the program can go through, the program displays a message to the user telling her that the hacking has started. The print() call on line 26 also tells her that she can press Ctrl-C (on Windows) or Ctrl-D (on OS X and Linux) to exit the program at any point. (Pressing these keys will always exit a running Python program.)
transpositionHacker.py
28. # brute-force by looping through every possible key
29. for key in range(1, len(message)):
30. print('Trying key #%s...' % (key))
The range of possible keys for the transposition cipher is the integers between 1 and the length of the message. The for loop on line 29 will run the hacking part of the function with each of these keys.
To provide feedback to the user, the key that is being tested is printed to the string on line 30, using string interpolation to place the integer in key inside the 'Trying key #%s...' % (key) string.
transpositionHacker.py
32. decryptedText = transpositionDecrypt.decryptMessage(key, message)
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.
transpositionHacker.py
34. if detectEnglish.isEnglish(decryptedText):
35. # Check with user to see if the decrypted key has been found.
36. print()
37. print('Possible encryption hack:')
38. print('Key %s: %s' % (key, decryptedText[:100]))
39. print()
40. print('Enter D for done, or just press Enter to continue hacking:')
41. response = input('> ')
The decrypted output in decryptedText will most likely only be English if the correct key was used (otherwise, it will appear to be random garbage). The string in decryptedText is passed to the detectEnglish.isEnglish() function we wrote in the last chapter.
But just because detectEnglish.isEnglish() returns True (making the program execution enter the block following the if statement on line 34) doesn’t mean the program has found the correct key. It could be a “false positive”. To be sure, line 38 prints out the first 100 characters of thedecryptedText string (by using the slice decryptedText[:100]) on the screen for the user to look at.
The program pauses when line 41 executes, waiting for the user to type something in either D on nothing before pressing Enter. This input is stored as a string in response.
The strip() String Method
The strip() string method returns a version of the string that has any whitespace at the beginning and end of the string stripped out. Try typing in the following into the interactive shell:
>>> ' Hello'.strip()
'Hello'
>>> 'Hello '.strip()
'Hello'
>>> ' Hello World '.strip()
'Hello World'
>>> 'Hello x'.strip()
'Hello x'
>>>
The strip() method can also have a string argument passed to it that tells the method which characters should be removed from the start and end of the string instead of removing whitespace. The whitespace characters are the space character, the tab character, and the newline character. Try typing the following into the interactive shell:
>>> 'Helloxxxxxx'.strip('x')
'Hello'
>>> 'aaaaaHELLOaa'.strip('a')
'HELLO'
>>> 'ababaHELLOab'.strip('ab')
'HELLO'
>>> 'abccabcbacbXYZabcXYZacccab'.strip('abc')
'XYZabcXYZ'
>>>
transpositionHacker.py
43. if response.strip().upper().startswith('D'):
44. return decryptedText
The expression on line 43 used for the if statement’s condition lets the user have some flexibility with what has to be typed in. If the condition were response == 'D', then the user would have to type in exactly “D” and nothing else in order to end the program.
If the user typed in 'd' or ' D' or 'Done' then the condition would be False and the program would continue. To avoid this, the string in response has any whitespace removed from the start or end with the call to strip(). Then the string that response.strip() evaluates to has the upper()method called on it. If the user typed in either “d” or “D”, the string returned from upper() will be 'D'. Little things like this make our programs easier for the user to use.
If the user has indicated that the decrypted string is correct, the decrypted text is returned from hackTransposition() on line 44.
transpositionHacker.py
46. return None
Line 46 is the first line after the for loop that began on line 29. If the program execution reaches this point, it’s because the return statement on line 44 was never reached. That would only 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 has failed.
transpositionHacker.py
48. if __name__ == '__main__':
49. main()
Lines 48 and 49 call the main() function if this program was run by itself, rather than imported by another program that wants to use its hackTransposition() function.
Practice Exercises, Chapter 13, Set A
Practice exercises can be found at http://invpy.com/hackingpractice13A.
Summary
This chapter was short like the “Breaking the Caesar Cipher with the Brute-Force Technique” chapter because (also like that chapter) most of the code was already written in other programs. Our hacking program can import functions from these other programs by importing them as modules.
The strip() string method is useful for removing whitespace (or other) characters from the beginning or end of a string. If we use triple quotes, then a string value can span across multiple lines in our source code.
The detectEnglish.py program removes a lot of the work of inspecting the decrypted output to see if it’s English. This allows the brute-force technique to be applied to a cipher that can have thousands of keys.
Our programs are becoming more sophisticated. Before we learn the next cipher, we should learn how to use Python’s debugger tool to help us find bugs in our programs.