Problem #59 concerns a type of cipher in cryptography known as XOR encryption. The question reads:
Project Euler Problem 59: XOR decryption Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107. A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65. For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message. Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable. Your task has been made easy, as the encryption key consists of three lower case characters. Using p059_cipher.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.
As it turns out, XOR Decryption is exactly the same as XOR encryption. Setting c = a XOR b, we can find that c XOR b = a for all a and b. This fact will be used to greatly simplify our brute force.
Solution #1: Brute Force Approach
It suffices to check all 26*26*26 = 17,576 possible 3-letter keys and store the ones that decrypt the cipher text into a reasonable deciphered text. It takes a bit of guessing and checking to determine what characters are acceptable in a reasonable deciphered text, but after going through the most common characters in typical English text, we can find that only one key provides a reasonable answer. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Basic Cryptography Approach to Project Euler Problem #59
'''
import time
f = open("PE59CipherText.txt", "r")
if(f.mode == "r"):
contents = f.readlines()
realContents = []
for x in contents:
realContents.append(x.split(","))
else:
raise ValueError("Cannot read from file")
finalContents = []
for x in realContents[0]:
finalContents.append(int(x))
def isAcceptable(myChar):
return 'a'<=myChar<='z' or 'A'<=myChar<='Z' or myChar == ' ' or myChar == '\'' or myChar == ',' or myChar == '"' or myChar == '[' or myChar == ']' or myChar == ':' or '0'<=myChar<='9' or myChar == '/' or myChar == '.' or myChar == '(' or myChar == ')' or myChar == ';' or myChar=='+'
def projectEulerProblemFiftyNine(cipherText):
tl = len(cipherText)
alphabet = "abcdefghijklmnopqrstuvwxyz"
possible = []
for a in alphabet:
for b in alphabet:
for c in alphabet:
myGuess = a+b+c
asciiIndices = [ord(a),ord(b),ord(c)]
s = ""
bad = False
for x in range(tl):
myChar = chr(cipherText[x] ^ asciiIndices[x%3])
if not isAcceptable(myChar):
bad = True
break
s+=myChar
if not bad:
possible.append(s)
total = -1
for x in possible:
subTotal = 0
for y in x:
subTotal+=ord(y)
if(total==-1):
total = subTotal
return total
start = time.time()
print projectEulerProblemFiftyNine(finalContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
129448
--- 0.169327974319 seconds ---
for input of given cipher text.
'''
And with that, we’re done. In case you’re wondering, the key was “exp” and the decrypted text was “An extract taken from the introduction of one of Euler’s most celebrated papers, “De summis serierum reciprocarum” [On the sums of series of reciprocals]: I have recently found, quite unexpectedly, an elegant expression for the entire sum of this series 1 + 1/4 + 1/9 + 1/16 + etc., which depends on the quadrature of the circle, so that if the true sum of this series is obtained, from it at once the quadrature of the circle follows. Namely, I have found that the sum of this series is a sixth part of the square of the perimeter of the circle whose diameter is 1; or by putting the sum of this series equal to s, it has the ratio sqrt(6) multiplied by s to 1 of the perimeter to the diameter. I will soon show that the sum of this series to be approximately 1.644934066842264364; and from multiplying this number by six, and then taking the square root, the number 3.141592653589793238 is indeed produced, which expresses the perimeter of a circle whose diameter is 1. Following again the same steps by which I had arrived at this sum, I have discovered that the sum of the series 1 + 1/16 + 1/81 + 1/256 + 1/625 + etc. also depends on the quadrature of the circle. Namely, the sum of this multiplied by 90 gives the biquadrate (fourth power) of the circumference of the perimeter of a circle whose diameter is 1. And by similar reasoning I have likewise been able to determine the sums of the subsequent series in which the exponents are even numbers.”
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 
I am not geting the following:
total = -1
for x in possible:
subTotal = 0
for y in x:
subTotal+=ord(y)
if(total==-1):
total = subTotal
return total
Wouldn’t this code return only the first total sum of the ASCII values of the first decyption or am I misreading something? I’ve just tested it with something easy as possible = [‘cat’,’kangaroo’] at it returned me the total for ‘cat’ only.
LikeLiked by 1 person
Oops, you are right. This code would only print the total of the ASCII values of one of the strings in ‘possible’. Based on the way I indented it, it should return the total of the last element.
I think the reason I did it this way was because I I had determined with brute force that there was only one possible comprehensible plain-text for a given arrangement of “isAcceptable.” At that point, I got lazy and wrote code to just get the sum of the characters in one element. I wrote this code over a year ago so I forgot my exact thought process, but I think it was something like that.
Thanks for the comment! 🙂
LikeLike