XOR gate

XOR gate

Very interesting problem from Project Euler (59), made easier by the fact that the key is lowercase and 3 letters long. The encrypted message by cyclically repeating the 3 letter key through the message. Assuming spaces have not been removed in the plaintext message, a simple frequency analysis of the 3 batches of letters XOR’d with different letters in the key decrypts the cipher text quite quickly. Implementation in Python:

cipher = urllib2.urlopen("https://projecteuler.net/project/cipher1.txt")
cipher_text = cipher.read()
cipher_text = cipher_text.split(",")
cipher_text[-1] = cipher_text[-1][0:2]

""" Frequency Analysis """

key_base = string.lowercase
start_time = time.time()
letter_1 = []
letter_2 = []
letter_3 = []
space_ascii = ord(' ')
for letter in key_base:
	space_counter = 0
	for i in xrange(0, len(cipher_text), 3):
		if int(cipher_text[i]) ^ ord(letter) == space_ascii:
			space_counter += 1
	letter_1.append(space_counter)
	space_counter = 0
	for j in xrange(1, len(cipher_text), 3):
		if int(cipher_text[j]) ^ ord(letter) == space_ascii:
			space_counter += 1
	letter_2.append(space_counter)
	space_counter = 0
	for k in xrange(2, len(cipher_text), 3):
		if int(cipher_text[k]) ^ ord(letter) == space_ascii:
			space_counter += 1
	letter_3.append(space_counter)

key = [ord(key_base[letter_1.index(max(letter_1))]), ord(key_base[letter_2.index(max(letter_2))]), ord(key_base[letter_3.index(max(letter_3))])]

""" Decryption """

decrypted_message = []
for i in xrange(len(cipher_text)):
	decrypted_message.append(int(cipher_text[i]) ^ key[i % 3])

ascii_sum = sum(decrypted_message)
finish_time = time.time() - start_time
Advertisements