Chapter 15 - Hacking the Affine Cipher
15
HACKING THE AFFINE CIPHER
“Cryptanalysis could not be invented until a civilization had reached a sufficiently sophisticated level of scholarship in several disciplines, including mathematics, statistics, and linguistics.”
—Simon Singh, The Code Book
In Chapter 14, you learned that the affine cipher is limited to only a few thousand keys, which means we can easily perform a brute-force attack against it. In this chapter, you’ll learn how to write a program that can break affine cipher–encrypted messages.
Source Code for the Affine Cipher Hacker Program
Open a new file editor window by selecting File▸New File. Enter the following code into the file editor and then save it as affineHacker.py. Entering the string for the myMessage variable by hand might be tricky, so you can copy and paste it from the affineHacker.py file available at https://www.nostarch.com/crackingcodes/ to save time. Make sure dictionary.txt as well as pyperclip.py, affineCipher.py, detectEnglish.py, and cryptomath.py are in the same directory as affineHacker.py.
affineHacker.py
1. # Affine Cipher Hacker
2. # https://www.nostarch.com/crackingcodes/ (BSD Licensed)
3.
4. import pyperclip, affineCipher, detectEnglish, cryptomath
5.
6. SILENT_MODE = False
7.
8. def main():
9. # You might want to copy & paste this text from the source code at
10. # https://www.nostarch.com/crackingcodes/.
11. myMessage = """5QG9ol3La6QI93!xQxaia6faQL9QdaQG1!!axQARLa!!A
uaRLQADQALQG93!xQxaGaAfaQ1QX3o1RQARL9Qda!AafARuQLX1LQALQI1
iQX3o1RN"Q-5!1RQP36ARu"""
12.
13. hackedMessage = hackAffine(myMessage)
14.
15. if hackedMessage != None:
16. # The plaintext is displayed on the screen. For the convenience of
17. # the user, we copy the text of the code to the clipboard:
18. print('Copying hacked message to clipboard:')
19. print(hackedMessage)
20. pyperclip.copy(hackedMessage)
21. else:
22. print('Failed to hack encryption.')
23.
24.
25. def hackAffine(message):
26. print('Hacking...')
27.
28. # Python programs can be stopped at any time by pressing Ctrl-C (on
29. # Windows) or Ctrl-D (on macOS and Linux):
30. print('(Press Ctrl-C or Ctrl-D to quit at any time.)')
31.
32. # Brute-force by looping through every possible key:
33. for key in range(len(affineCipher.SYMBOLS) ** 2):
34. keyA = affineCipher.getKeyParts(key)[0]
35. if cryptomath.gcd(keyA, len(affineCipher.SYMBOLS)) != 1:
36. continue
37.
38. decryptedText = affineCipher.decryptMessage(key, message)
39. if not SILENT_MODE:
40. print('Tried Key %s... (%s)' % (key, decryptedText[:40]))
41.
42. if detectEnglish.isEnglish(decryptedText):
43. # Check with the user if the decrypted key has been found:
44. print()
45. print('Possible encryption hack:')
46. print('Key: %s' % (key))
47. print('Decrypted message: ' + decryptedText[:200])
48. print()
49. print('Enter D for done, or just press Enter to continue
hacking:')
50. response = input('> ')
51.
52. if response.strip().upper().startswith('D'):
53. return decryptedText
54. return None
55.
56.
57. # If affineHacker.py is run (instead of imported as a module), call
58. # the main() function:
59. if __name__ == '__main__':
60. main()
Sample Run of the Affine Cipher Hacker Program
Press F5 from the file editor to run the affineHacker.py program; the output should look like this:
Hacking...
(Press Ctrl-C or Ctrl-D to quit at any time.)
Tried Key 95... (U&'<3dJ^Gjx'-3^MS'Sj0jxuj'G3'%j'<mMMjS'g)
Tried Key 96... (T%&;2cI]Fiw&,2]LR&Ri/iwti&F2&$i&;lLLiR&f)
Tried Key 97... (S$%:1bH\Ehv%+1\KQ%Qh.hvsh%E1%#h%:kKKhQ%e)
--snip--
Tried Key 2190... (?^=!-+.32#0=5-3*"="#1#04#=2-= #=!~**#"=')
Tried Key 2191... (' ^BNLOTSDQ^VNTKC^CDRDQUD^SN^AD^B@KKDC^H)
Tried Key 2192... ("A computer would deserve to be called i)
Possible encryption hack:
Key: 2192
Decrypted message: "A computer would deserve to be called intelligent if it
could deceive a human into believing that it was human." -Alan Turing
Enter D for done, or just press Enter to continue hacking:
> d
Copying hacked message to clipboard:
"A computer would deserve to be called intelligent if it could deceive a human
into believing that it was human." –Alan Turing
Let’s take a closer look at how the affine cipher hacker program works.
Setting Up Modules, Constants, and the main() Function
The affine cipher hacker program is 60 lines long because we’ve already written much of the code it uses. Line 4 imports the modules we created in previous chapters:
1. # Affine Cipher Hacker
2. # https://www.nostarch.com/crackingcodes/ (BSD Licensed)
3.
4. import pyperclip, affineCipher, detectEnglish, cryptomath
5.
6. SILENT_MODE = False
When you run the affine cipher hacker program, you’ll see that it produces lots of output as it works its way through all the possible decryptions. However, printing all this output slows down the program. If you want to speed up the program, set the SILENT_MODE variable on line 6 to True to stop it from printing all these messages.
Next, we set up the main() function:
8. def main():
9. # You might want to copy & paste this text from the source code at
10. # https://www.nostarch.com/crackingcodes/.
11. myMessage = """5QG9ol3La6QI93!xQxaia6faQL9QdaQG1!!axQARLa!!A
uaRLQADQALQG93!xQxaGaAfaQ1QX3o1RQARL9Qda!AafARuQLX1LQALQI1
iQX3o1RN"Q-5!1RQP36ARu"""
12.
13. hackedMessage = hackAffine(myMessage)
The ciphertext to be hacked is stored as a string in myMessage on line 11, and this string is passed to the hackAffine() function, which we’ll look at in the next section. The return value from this call is either a string of the original message if the ciphertext was hacked or the None value if the hack failed.
The code on lines 15 to 22 checks whether hackedMessage was set to None:
15. if hackedMessage != None:
16. # The plaintext is displayed on the screen. For the convenience of
17. # the user, we copy the text of the code to the clipboard:
18. print('Copying hacked message to clipboard:')
19. print(hackedMessage)
20. pyperclip.copy(hackedMessage)
21. else:
22. print('Failed to hack encryption.')
If hackedMessage is not equal to None, the message is printed to the screen on line 19 and copied to the clipboard on line 20. Otherwise, the program simply prints feedback to the user that it was unable to hack the ciphertext. Let’s take a closer look at how the hackAffine() function works.
The Affine Cipher Hacking Function
The hackAffine() function begins on line 25 and contains the code for decryption. It starts by printing some instructions for the user:
25. def hackAffine(message):
26. print('Hacking...')
27.
28. # Python programs can be stopped at any time by pressing Ctrl-C (on
29. # Windows) or Ctrl-D (on macOS and Linux):
30. print('(Press Ctrl-C or Ctrl-D to quit at any time.)')
The decryption process can take a while, so if the user wants to exit the program early, they can press ctrl-C (on Windows) or ctrl-D (on macOS and Linux).
Before we continue with the rest of the code, you need to learn about the exponent operator.
The Exponent Operator
A useful math operator you need to know to understand the affine cipher hacker program (besides the basic +, -, *, /, and // operators) is the exponent operator (**). The exponent operator raises a number to the power of another number. For example, two to the power of five would be 2 ** 5 in Python. This is equivalent to two multiplied by itself five times: 2 * 2 * 2 * 2 * 2. Both expressions, 2 ** 5 and 2 * 2 * 2 * 2 * 2, evaluate to the integer 32.
Enter the following into the interactive shell to see how the ** operator works:
>>> 5 ** 2
25
>>> 2 ** 5
32
>>> 123 ** 10
792594609605189126649
The expression 5 ** 2 evaluates to 25 because 5 multiplied by itself is equivalent to 25. Likewise, 2 ** 5 returns 32 because 2 multiplied by itself five times evaluates to 32.
Let’s return to the source code to see what the ** operator does in the program.
Calculating the Total Number of Possible Keys
Line 33 uses the ** operator to calculate the total number of possible keys:
32. # Brute-force by looping through every possible key:
33. for key in range(len(affineCipher.SYMBOLS) ** 2):
34. keyA = affineCipher.getKeyParts(key)[0]
We know there are at most len(affineCipher.SYMBOLS) possible integers for Key A and len(affineCipher.SYMBOLS) possible integers for Key B. To get the entire range of possible keys, we multiply these values together. Because we’re multiplying the same value by itself, we can use the ** operator in the expression len(affineCipher.SYMBOLS) ** 2.
Line 34 calls the getKeyParts() function that we used in affineCipher.py to split a single integer key into two integers. In this example, we’re using the function to get the Key A part of the key we’re testing. Recall that the return value of this function call is a tuple of two integers: one for Key A and one for Key B. Line 34 stores the tuple’s first integer in keyA by placing the [0] after the getKeyParts() function call.
For example, affineCipher.getKeyParts(key)[0] evaluates to the tuple and the index (42, 22)[0], which then evaluates to 42, the value at index 0 of the tuple. This gets just the Key A part of the return value and stores it in the variable keyA. The Key B part (the second value in the returned tuple) is ignored because we don’t need Key B to calculate whether Key A is valid. Lines 35 and 36 check whether keyA is a valid Key A for the affine cipher, and if not, the program continues to the next key to try. To understand how the execution moves back to the start of the loop, you need to learn about the continue statement.
The continue Statement
The continue statement uses the continue keyword by itself and takes no parameters. We use a continue statement inside a while or for loop. When a continue statement executes, the program execution immediately jumps to the start of the loop for the next iteration. This also happens when the program execution reaches the end of the loop’s block. But a continue statement makes the program execution jump back to the start of the loop before it reaches the end of the loop.
Enter the following into the interactive shell:
>>> for i in range(3):
... print(i)
... print('Hello!')
...
0
Hello!
1
Hello!
2
Hello!
The for loop loops through the range object, and the value in i becomes each integer from 0 up to, but not including, 3. On each iteration, the print('Hello!') function call displays Hello! on the screen.
Now contrast that for loop with the next example, which is the same as the previous example except it has a continue statement before the print('Hello!') line.
>>> for i in range(3):
... print(i)
... continue
... print('Hello!')
...
0
1
2
Notice that Hello! never gets printed, because the continue statement causes the program execution to jump back to the start of the for loop for the next iteration and the execution never reaches the print('Hello!') line.
A continue statement is often placed inside an if statement’s block so that execution continues at the beginning of the loop under certain conditions. Let’s return to our code to see how it uses the continue statement to skip execution depending on the key used.
Using continue to Skip Code
In the source code, line 35 uses the gcd() function in the cryptomath module to determine whether Key A is relatively prime to the symbol set size:
35. if cryptomath.gcd(keyA, len(affineCipher.SYMBOLS)) != 1:
36. continue
Recall that two numbers are relatively prime if their greatest common divisor (GCD) is 1. If Key A and the symbol set size are not relatively prime, the condition on line 35 is True and the continue statement on line 36 executes. This causes the program execution to jump back to the start of the loop for the next iteration. As a result, the program skips the call to decryptMessage() on line 38 if the key is invalid and continues to try other keys until it finds the right one.
When the program finds the right key, the message is decrypted by calling decryptMessage() with the key on line 38:
38. decryptedText = affineCipher.decryptMessage(key, message)
39. if not SILENT_MODE:
40. print('Tried Key %s... (%s)' % (key, decryptedText[:40]))
If SILENT_MODE was set to False, the Tried Key message is printed on the screen, but if it was set to True, the print() call on line 40 is skipped.
Next, line 42 uses the isEnglish() function from the detectEnglish module to check whether the decrypted message is recognized as English:
42. if detectEnglish.isEnglish(decryptedText):
43. # Check with the user if the decrypted key has been found:
44. print()
45. print('Possible encryption hack:')
46. print('Key: %s' % (key))
47. print('Decrypted message: ' + decryptedText[:200])
48. print()
If the wrong decryption key was used, the decrypted message would look like random characters and isEnglish() would return False. But if the decrypted message is recognized as readable English (by the isEnglish() function’s standards), the program displays it to the user.
We display a snippet of the decrypted message that is recognized as English, because the isEnglish() function might mistakenly identify text as English even though it hasn’t found the correct key. If the user decides that this is indeed the correct decryption, they can type D and then press enter.
49. print('Enter D for done, or just press Enter to continue
hacking:')
50. response = input('> ')
51.
52. if response.strip().upper().startswith('D'):
53. return decryptedText
Otherwise, the user can just press enter to return a blank string from the input() call, and the hackAffine() function would continue trying more keys.
From the indentation at the beginning of line 54, you can see that this line executes after the for loop on line 33 has completed:
54. return None
If the for loop finishes and reaches line 54, then it has gone through every possible decryption key without finding the correct one. At this point, the hackAffine() function returns the None value to signal that it was unsuccessful at hacking the ciphertext.
If the program had found the correct key, the execution would have previously returned from the function on line 53 and never reached line 54.
Calling the main() Function
If we run affineHacker.py as a program, the special __name__ variable will be set to the string '__main__' instead of 'affineHacker'. In this case, we call the main() function.
57. # If affineHacker.py is run (instead of imported as a module), call
58. # the main() function:
59. if __name__ == '__main__':
60. main()
That concludes the affine cipher hacking program.
Summary
This chapter is fairly short because it doesn’t introduce any new hacking techniques. As you’ve seen, as long as the number of possible keys is only a few thousand, it won’t take long for computers to brute-force through every possible key and use the isEnglish() function to search for the right key.
You learned about the exponent operator (**), which raises a number to the power of another number. You also learned how to use the continue statement to send the program execution back to the beginning of the loop instead of waiting until the execution reaches the end of the block.
Conveniently, we already wrote much of the code used for the affine cipher hacker in affineCipher.py, detectEnglish.py, and cryptomath.py. The main() function trick helps us reuse the code in our programs.
In Chapter 16, you’ll learn about the simple substitution cipher, which computers can’t brute-force. The number of possible keys for this cipher is more than trillions of trillions! A single laptop couldn’t possibly go through a fraction of those keys in our lifetime, which makes the cipher immune to a brute-force attack.