Skip to content

Instantly share code, notes, and snippets.

@chrisballinger
Created January 20, 2014 05:39
Show Gist options
  • Save chrisballinger/8515411 to your computer and use it in GitHub Desktop.
Save chrisballinger/8515411 to your computer and use it in GitHub Desktop.
#!/usr/bin/python
# Public Domain
def strxor(a, b): # xor two strings of different lengths
if len(a) > len(b):
return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a[:len(b)], b)])
else:
return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b[:len(a)])])
def scan_for_letter(character):
int_char = ord(character)
if int_char >= 65 and int_char <= 91 or int_char >= 97 and int_char <= 123:
return str(character).swapcase()
else:
return None
def set_letter_at_index(letter, letter_index, probability_arrays, ct1_index, ct2_index):
prob_arrays = [probability_arrays[ct1_index], probability_arrays[ct2_index]]
for prob_array in prob_arrays:
prob_dict = prob_array[letter_index]
letter_count = prob_dict.get(letter, 0) + 1
space_count = prob_dict.get(' ', 0) + 1
prob_dict[letter] = letter_count
prob_dict[' '] = space_count
probability_arrays[ct1_index] = prob_arrays[0]
probability_arrays[ct2_index] = prob_arrays[1]
def scan_string(string, probability_arrays, ct1_index, ct2_index):
characters = list(string)
for character_index in range(len(string)):
character = characters[character_index]
letter = scan_for_letter(character)
if letter:
set_letter_at_index(letter, character_index, probability_arrays, ct1_index, ct2_index)
def xor_indices(array, x, y):
ct1 = array[x].decode("hex")
ct2 = array[y].decode("hex")
xor = strxor(ct1, ct2)
return xor
def permute_array(cipher_texts, probability_arrays):
for x in range(len(cipher_texts)):
for y in range(x+1, len(cipher_texts)):
xor = xor_indices(cipher_texts, x, y)
scan_string(xor, probability_arrays, x, y)
def most_probable(prob_dict):
if len(prob_dict) is 0:
return ' '
total_character_count = 0
keys = prob_dict.keys()
for key in keys:
character_count = prob_dict[key]
total_character_count = total_character_count + character_count
for key in keys:
prob_dict[key] = float(prob_dict[key]) / total_character_count
highest_probability_index = 0
for i in range(1, len(keys)):
key = keys[i]
probability = prob_dict[key]
highest_probability = prob_dict[keys[highest_probability_index]]
if probability > highest_probability:
highest_probability_index = i
most_probable_key = keys[highest_probability_index]
return most_probable_key
def guess_string(probability_array):
guessed_characters = []
for prob_dict in probability_array:
if len(prob_dict) is 0:
guessed_characters.append('*')
continue
if len(prob_dict) is 2:
prob_dict.pop(' ', None)
key = prob_dict.keys()[0]
guessed_characters.append(key)
continue
most_probable_key = most_probable(prob_dict)
guessed_characters.append(most_probable_key)
return "".join(guessed_characters)
def generate_guesses(probability_arrays):
guess_texts = []
for probability_array in probability_arrays:
guessed_string = guess_string(probability_array)
guess_texts.append(guessed_string)
return guess_texts
def generate_probability_arrays(cipher_texts):
probability_arrays = []
for i in range(len(cipher_texts)):
ct_length = len(cipher_texts[i].decode("hex"))
probability_array = []
for j in range(ct_length):
probability_array.append({})
probability_arrays.append(probability_array)
return probability_arrays
def length_of_longest_array(arrays):
if len(arrays) is 0:
return 0
max_length = len(arrays[0])
for i in range(1, len(arrays)):
array_length = len(arrays[i])
if array_length > max_length:
max_length = array_length
return max_length
def generate_key_guess_array(key_length):
key_guess_array = []
for i in range(key_length):
key_guess_array.append({})
return key_guess_array
def update_key_probabilities(key_guess_string, key_guess_probabilities):
key_guess_list = list(key_guess_string)
for i in range(len(key_guess_string)):
key_guess = key_guess_list[i]
key_dict = key_guess_probabilities[i]
guess_count = key_dict.get(key_guess, 0) + 1
key_dict[key_guess] = guess_count
key_guess_probabilities[i] = key_dict
def guess_key_from_probabilities(key_guess_probabilities):
key_guess = []
for prob_dict in key_guess_probabilities:
most_probable_key = most_probable(prob_dict)
key_guess.append(most_probable_key)
return "".join(key_guess)
def guess_key(guess_texts, cipher_texts):
key_guess_probabilities = generate_key_guess_array(length_of_longest_array(guess_texts))
for i in range(len(guess_texts)):
guess_text = guess_texts[i]
key_guess = strxor(cipher_texts[i].decode("hex"), guess_text)
update_key_probabilities(key_guess, key_guess_probabilities)
key_guess = guess_key_from_probabilities(key_guess_probabilities)
return key_guess
def main():
cipher_texts = ["feedface"] # redacted
probability_arrays = generate_probability_arrays(cipher_texts)
permute_array(cipher_texts, probability_arrays)
guess_texts = generate_guesses(probability_arrays)
for i in range(len(guess_texts)):
print str(i+1) + ': ' + guess_texts[i]
key_guess = guess_key(guess_texts, cipher_texts)
print 'Key0: ' + key_guess.encode("hex")
for i in range(len(cipher_texts)):
print str(i+1) + ': ' + strxor(key_guess, cipher_texts[i].decode("hex"))
plain_texts = ["redacted"]
original_key = 'feedface'
key_guess = guess_key(plain_texts, cipher_texts)
print 'Key1: ' + key_guess.encode("hex")
for i in range(len(cipher_texts)):
print str(i+1) + ': ' + strxor(key_guess, cipher_texts[i].decode("hex"))
print 'Original Key: ' + original_key
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment