Hacking Secret Ciphers with Python (2013)

Chapter 16: HACKING THE AFFINE CIPHER

Topics Covered In This Chapter:

· The ** Exponent Operator

· The continue Statement

We know that the affine cipher is limited to only a few thousand keys. This means it is trivial to perform a brute-force attack against it. Open a new File Editor and type in the following code. Save the file as affineHacker.py.

Source Code of the Affine 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 affineHacker.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 affineHacker.py file. You can download this file from http://invpy.com/pyperclip.py.

Typing the string for the myMessage variable might be tricky, but you can copy and paste it from http://invpy.com/affineHacker.py to save time.

Source Code for affineHacker.py

1. # Affine Cipher Hacker

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

4. import pyperclip, affineCipher, detectEnglish, cryptomath

6. SILENT_MODE = False

8. def main():

9. # You might want to copy & paste this text from the source code at

10. # http://invpy.com/affineHacker.py

11. myMessage = """U&'<3dJ^Gjx'-3^MS'Sj0jxuj'G3'%j'<mMMjS'g{GjMMg9j{G'g"'gG '<3^MS'Sj<jguj'm'P^dm{'g{G3'%jMgjug{9'GPmG'gG'-m0'P^dm{LU'5&Mm{'_^xg{9"""

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 Mac 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

When you press F5 from the file editor to run this program, the output will 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)

...skipped for brevity...

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

How the Program Works

affineHacker.py

1. # Affine Cipher Hacker

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

4. import pyperclip, affineCipher, detectEnglish, cryptomath

6. SILENT_MODE = False

Our affine cipher hacking program fits in 60 lines of code because we’ve already written much of the code it uses.

When you run the hacker program, you can see that this program produces a lot of output as it works its way through all the possible decryptions. However, printing out this input does slow down the program. If you change line 6 to set the SILENT_MODE variable to True, the program will be silenced and not print out all these messages. This will speed up the program immensely.

But showing all that text while your hacking program runs makes it look cool. (And if you want your programs to look cool by printing out text slowly one character at a time for a “typewriter” effect, check out the typewriter.py module at http://invpy.com/typewriter.py.)

affineHacker.py

8. def main():

9. # You might want to copy & paste this text from the source code at

10. # http://invpy.com/affineHacker.py

11. myMessage = """U&'<3dJ^Gjx'-3^MS'Sj0jxuj'G3'%j'<mMMjS'g{GjMMg9j{G'g"'gG '<3^MS'Sj<jguj'm'P^dm{'g{G3'%jMgjug{9'GPmG'gG'-m0'P^dm{LU'5&Mm{'_^xg{9"""

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.')

The ciphertext to be hacked is stored as a string in myMessage, and this string is passed to the hackAffine() function (described next). 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 hacking failed).

The code on lines 15 to 22 will check if hackedMessage was set to None or not. If hackedMessage is not equal to None, then the message will be printed to the screen on line 19 and copied to the clipboard on line 20. Otherwise, the program will simply print that it was unable to hack the message.

The Affine Cipher Hacking Function

affineHacker.py

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 Mac and Linux)

30. print('(Press Ctrl-C or Ctrl-D to quit at any time.)')

The hackAffine() function has the code that does the decryption. This can take a while, so if the user wants to exit the program early, she can press Ctrl-C (on Windows) or Ctrl-D (on OS X and Linux).

The ** Exponent Operator

There is another math operator besides the basic +, -, *, /, and // operators. The ** operator is Python’s exponent operator. This does “to the power of” math on two numbers. For example, “two to the power of five” would be 2 ** 5 in Python code. This is equivalent to two multiplied by itself five times: 2 * 2 * 2 * 2 * 2. Both the expressions 2 ** 5 and 2 * 2 * 2 * 2 * 2 evaluate to the integer 32.

Try typing the following into the interactive shell:

>>> 2 ** 6

>>> 4**2

>>> 2**4

>>> 123**10

792594609605189126649

>>>

affineHacker.py

32. # brute-force by looping through every possible key

33. for key in range(len(affineCipher.SYMBOLS) ** 2):

34. keyA = affineCipher.getKeyParts(key)[0]

The range of integers for the keys used to brute-force the ciphertext will range from 0 to the size of the symbol set to the second power. The expression:

len(affineCipher.SYMBOLS) ** 2

...is the same as:

len(affineCipher.SYMBOLS) * len(affineCipher.SYMBOLS)

We multiply this because 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.

Line 34 calls the getKeyParts() function that we made in affineCipher.py to get the Key A part of the key we are testing. Remember that the return value of this function call is a tuple of two integers (one for Key A and one for Key B). Since hackAffine() only needs Key A, the [0] after the function call works on the return value to evaluate to just the first integer in the returned tuple.

That is, affineCipher.getKeyParts(key)[0] will evaluate to (for example), the tuple (42, 22)[0], which will then evaluate to 42. This is how we can get just the Key A part of the return value. The Key B part (that is, the second value in the returned tuple) is just ignored because we don’t need Key B to calculate if Key A is valid.

The continue Statement

The continue statement is simply the continue keyword by itself. A continue statement is found inside the block of a while or for loop. When a continue statement is executed, the program execution immediately jumps to the start of the loop for the next iteration.

This is exactly the same thing that 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 early.

Try typing the following into the interactive shell:

>>> for i in range(3):

... print(i)

... print('Hello!')

...

Hello!

>>>

This is pretty obvious. The for loop will loop through the range object, and the value in i becomes each integer between 0 and 4. Also on each iteration, the print('Hello!') function call will display “Hello!” on the screen.

Try typing in this code, which adds a continue statement before the print('Hello!') line:

>>> for i in range(3):

... print(i)

... continue

... print('Hello!')

...

>>>

Notice that “Hello!” never appears, because the continue statement causes the program execution to jump back to the start of the for loop for the next iteration. So the execution never reaches the print('Hello!') line.

A continue statement is often put inside an if statement’s block so that execution will continue at the beginning of the loop based on some condition.

affineHacker.py

35. if cryptomath.gcd(keyA, len(affineCipher.SYMBOLS)) != 1:

36. continue

With the Key A integer stored in the variable keyA, line 35 uses the gcd() function in our cryptomath module to determine if Key A is not relatively prime with the symbol set size. Remember, two numbers are relatively prime if their GCD (greatest common divisor) is one.

If Key A and the symbol set size are not relatively prime, then the condition on line 35 is True and the continue statement on line 36 is executed. This will cause the program execution to jump back to the start of the loop for the next iteration. This way, the program will skip line 38’s call todecryptMessage() if the key is invalid, and continue to the next key.

affineHacker.py

38. decryptedText = affineCipher.decryptMessage(key, message)

39. if not SILENT_MODE:

40. print('Tried Key %s... (%s)' % (key, decryptedText[:40]))

The message is then decrypted with the key by calling decryptMessage(). If SILENT_MODE is False the “Tried Key” message will be printed on the screen. If SILENT_MODE was set to True, the print() call on line 40 will be skipped.

affineHacker.py

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()

Next, we use the isEnglish() function from our detectEnglish module to check if the decrypted message is recognized as English. If the wrong decryption key was used, then the decrypted message will look like random characters and isEnglish() will return False.

But if the decrypted message is recognized as readable English (by the isEnglish() function anyway), then we will display this to the user.

affineHacker.py

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

The program might not have found the correct key, but rather a key that produces gibberish that the isEnglish() function mistakenly thinks is English. To prevent false positives, the decrypted text is printed on the screen for the user to read. If the user decides that this is the correct decryption, she can type in D and press Enter. Otherwise, she can just press Enter (which returns a blank string from the input() call) and the hackAffine() function will continue trying more keys.

affineHacker.py

54. return None

From the indentation of line 54, you can see that this is line is executed after the for loop on line 33 has completed. If this loop has finished, then it has gone through every possible decryption key without finding the correct key. (If the program had found the correct key, then the execution would have previously returned from the function on line 53.)

But at this point, the hackAffine() function returns the None value to signal that it was unsuccessful at hacking the ciphertext.

affineHacker.py

57. # If affineHacker.py is run (instead of imported as a module) call

58. # the main() function.

59. if __name__ == '__main__':

60. main()

Just like the other programs, we want the affineHacker.py file to be run on its own or be imported as a module. If affineHacker.py is run as a program, then the special __name__ variable will be set to the string '__main__' (instead of 'affineHacker'). In this case, we want to call the main()function.

Practice Exercises, Chapter 16, Set A

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

Summary

This chapter was fairly short because it hasn’t introduced any new hacking techniques. As long as the number of possible keys is less than a million or so, it won’t take long for our computers to brute-force through every possible key and use isEnglish() to check if it has found the right key.

And a lot of the code we use for the affine cipher hacker has already been written in affineCipher.py, detectEnglish.py, cryptomath.py, and pyperclip.py. The main() function trick is really helpful in making the code in our programs reusable.

The ** exponent operator can be used to raise a number to the power of another number. The continue statement sends the program execution back to the beginning of the loop (instead of waiting until the execution reaches the end of the block).

In the next chapter, we will learn a new cipher that cannot be brute-forced by our computers. The number of possible keys is more than a trillion trillion! A single laptop couldn’t possible go through a fraction of those keys in our life time. This makes it immune to brute-forcing. Let’s learn about the simple substitution cipher.