cryptopals

commit e071794ffd90ed473d9daeca62388f3d17b45800
parent a8b7ca46b35cc82afa2b64fc2300047e5879836f
Author: mpizzzle <michael.770211@gmail.com>
Date:   Sat,  7 Oct 2017 15:36:52 +0100

set 1 challenge 6 complete

Diffstat:
M
set1/break_repeating_key_xor.py
 | 
50
+++++++++++++++++++++++++++++++++++++++++++++++---

1 file changed, 47 insertions(+), 3 deletions(-)
diff --git a/set1/break_repeating_key_xor.py b/set1/break_repeating_key_xor.py
@@ -1,6 +1,50 @@
 import sys
 
-def hamming_distance(str1, str2):
+frequent_letters = "etaoi ETAOI"
+
+def distance(str1, str2):
 	return ''.join([bin(ord(a) ^ ord(b)) for a, b in zip(str1, str2)]).count('1')
+	
+def get_candidate_key_length(file, accuracy):
+	candidate_distance = sys.float_info.max
+	candidate_length = 0
+
+	for key_length in range(2, 40):
+		this_distance = sum([distance(file[key_length * x:key_length * (x + 1)], file[key_length * (x + 1):key_length * (x + 2)]) for x in range(accuracy)])
+		average_distance = this_distance / float(key_length * (accuracy))
+		if average_distance < candidate_distance:
+			candidate_distance = average_distance
+			candidate_length = key_length
+
+	return candidate_length
+
+def get_candidate_xor_byte(transposed_block):
+	candidate = ''
+	candidate_frequency = 0
+
+	for x in range(128):
+		frequency = 0
+		plaintext = ''.join([chr(x ^ ord(a)) for a in transposed_block])
+
+		for char in plaintext:
+			if char in frequent_letters:
+				frequency += 1
+
+		if frequency > candidate_frequency:
+			candidate = chr(x)
+			candidate_frequency = frequency
+	return candidate
+
+def decrypt(key, msg):
+	return ''.join([chr(ord(key[i % len(key)]) ^ ord(char)) for i, char in enumerate(msg)])
+
+with open('files/6.txt') as f:
+    file = f.read().decode("base64")	
+	
+key_length = get_candidate_key_length(file, 10)
+split_file = [file[i:i + key_length] for i in range(0, len(file), key_length)]
+transposed_blocks = [''.join([block[x] for block in split_file[:len(split_file)- 1]]) for x in range(key_length)]
 
-print hamming_distance("this is a test", "wokka wokka!!!")-
\ No newline at end of file
+key = ''.join([get_candidate_xor_byte(transposed_block) for transposed_block in transposed_blocks])
+print key
+print decrypt(key, file)+
\ No newline at end of file