break_repeating_key_xor.py (1974B)
1 frequent_letters = "etaoi ETAOI" 2 3 def distance(str1, str2): 4 return ''.join([bin(ord(a) ^ ord(b)) for a, b in zip(str1, str2)]).count('1') 5 6 def get_candidate_key_length(file, accuracy): 7 candidate_distance = 9999999 8 candidate_length = 0 9 10 for key_length in range(2, 40): 11 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)]) 12 average_distance = this_distance / float(key_length * (accuracy)) 13 14 if average_distance < candidate_distance: 15 candidate_distance = average_distance 16 candidate_length = key_length 17 18 return candidate_length 19 20 def get_candidate_key_byte(transposed_block): 21 candidate = '' 22 candidate_frequency = 0 23 24 for c in range(256): 25 plaintext = ''.join([chr(c ^ ord(a)) for a in transposed_block]) 26 frequency = sum([plaintext.count(frequent_letters[n]) for n in range(len(frequent_letters))]) 27 28 if frequency > candidate_frequency: 29 candidate = chr(c) 30 candidate_frequency = frequency 31 32 return candidate 33 34 def decrypt(key, msg): 35 return ''.join([chr(ord(key[i % len(key)]) ^ ord(char)) for i, char in enumerate(msg)]) 36 37 def get_key(file): 38 key_length = get_candidate_key_length(file, 10) 39 split_file = [file[i:i + key_length] for i in range(0, len(file), key_length)] 40 transposed_blocks = [''.join([block[x] for block in split_file[:len(split_file) - 1]]) for x in range(key_length)] 41 return ''.join([get_candidate_key_byte(block) for block in transposed_blocks]) 42 43 file = open('files/6.txt').read().decode("base64") 44 project_euler_59 = ''.join([chr(int(c)) for c in open('files/p059_cipher.txt').read().split(',')]) 45 46 key1 = get_key(file) 47 key2 = get_key(project_euler_59) 48 49 print "key: "" + key1 + ""n" + decrypt(key1, file) 50 print "key: "" + key2 + ""n" + decrypt(key2, project_euler_59)