X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=cipherbreak.py;h=c239400d7f0fb917dd319db3fbf0e704204399ee;hb=a28096fcfca066aea1cddc4ff29c2f09f0528852;hp=56143891e3290c3e0c481238cc2c41bee4bfa82f;hpb=76e40a7da75f35016c6528557908d421eea9e380;p=cipher-training.git diff --git a/cipherbreak.py b/cipherbreak.py index 5614389..c239400 100644 --- a/cipherbreak.py +++ b/cipherbreak.py @@ -29,9 +29,6 @@ from language_models import * # timeit.timeit('keyword_break(c5a)', setup='gc.enable() ; from __main__ import c5a ; from cipher import keyword_break', number=1) # timeit.repeat('keyword_break_mp(c5a, chunksize=500)', setup='gc.enable() ; from __main__ import c5a ; from cipher import keyword_break_mp', repeat=5, number=1) -transpositions = collections.defaultdict(list) -for word in keywords: - transpositions[transpositions_of(word)] += [word] def frequencies(text): """Count the number of occurrences of each character in text @@ -131,185 +128,6 @@ def affine_break(message, fitness=Pletters): best_adder, best_one_based)[:50])) return (best_multiplier, best_adder, best_one_based), best_fit -def keyword_break(message, wordlist=keywords, fitness=Pletters): - """Breaks a keyword substitution cipher using a dictionary and - frequency analysis. - - >>> keyword_break(keyword_encipher('this is a test message for the ' \ - 'keyword decipherment', 'elephant', KeywordWrapAlphabet.from_last), \ - wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS - (('elephant', ), -52.834575011...) - """ - best_keyword = '' - best_wrap_alphabet = True - best_fit = float("-inf") - for wrap_alphabet in KeywordWrapAlphabet: - for keyword in wordlist: - plaintext = keyword_decipher(message, keyword, wrap_alphabet) - fit = fitness(plaintext) - logger.debug('Keyword break attempt using key {0} (wrap={1}) ' - 'gives fit of {2} and decrypt starting: {3}'.format( - keyword, wrap_alphabet, fit, - sanitise(plaintext)[:50])) - if fit > best_fit: - best_fit = fit - best_keyword = keyword - best_wrap_alphabet = wrap_alphabet - logger.info('Keyword break best fit with key {0} (wrap={1}) gives fit of ' - '{2} and decrypt starting: {3}'.format(best_keyword, - best_wrap_alphabet, best_fit, sanitise( - keyword_decipher(message, best_keyword, - best_wrap_alphabet))[:50])) - return (best_keyword, best_wrap_alphabet), best_fit - -def keyword_break_mp(message, wordlist=keywords, fitness=Pletters, - chunksize=500): - """Breaks a keyword substitution cipher using a dictionary and - frequency analysis - - >>> keyword_break_mp(keyword_encipher('this is a test message for the ' \ - 'keyword decipherment', 'elephant', KeywordWrapAlphabet.from_last), \ - wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS - (('elephant', ), -52.834575011...) - """ - with Pool() as pool: - helper_args = [(message, word, wrap, fitness) - for word in wordlist - for wrap in KeywordWrapAlphabet] - # Gotcha: the helper function here needs to be defined at the top level - # (limitation of Pool.starmap) - breaks = pool.starmap(keyword_break_worker, helper_args, chunksize) - return max(breaks, key=lambda k: k[1]) - -def keyword_break_worker(message, keyword, wrap_alphabet, fitness): - plaintext = keyword_decipher(message, keyword, wrap_alphabet) - fit = fitness(plaintext) - logger.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of ' - '{2} and decrypt starting: {3}'.format(keyword, - wrap_alphabet, fit, sanitise(plaintext)[:50])) - return (keyword, wrap_alphabet), fit - -def monoalphabetic_break_hillclimbing(message, max_iterations=10000000, - fitness=Pletters): - ciphertext = unaccent(message).lower() - alphabet = list(string.ascii_lowercase) - random.shuffle(alphabet) - alphabet = ''.join(alphabet) - return monoalphabetic_break_hillclimbing_worker(ciphertext, alphabet, - max_iterations, fitness) - -def monoalphabetic_break_hillclimbing_mp(message, workers=10, - max_iterations = 10000000, fitness=Pletters, chunksize=1): - worker_args = [] - ciphertext = unaccent(message).lower() - for i in range(workers): - alphabet = list(string.ascii_lowercase) - random.shuffle(alphabet) - alphabet = ''.join(alphabet) - worker_args.append((ciphertext, alphabet, max_iterations, fitness)) - with Pool() as pool: - breaks = pool.starmap(monoalphabetic_break_hillclimbing_worker, - worker_args, chunksize) - return max(breaks, key=lambda k: k[1]) - -def monoalphabetic_break_hillclimbing_worker(message, alphabet, - max_iterations, fitness): - def swap(letters, i, j): - if i > j: - i, j = j, i - if i == j: - return letters - else: - return (letters[:i] + letters[j] + letters[i+1:j] + letters[i] + - letters[j+1:]) - best_alphabet = alphabet - best_fitness = float('-inf') - for i in range(max_iterations): - alphabet = swap(alphabet, random.randrange(26), random.randrange(26)) - cipher_translation = ''.maketrans(string.ascii_lowercase, alphabet) - plaintext = message.translate(cipher_translation) - if fitness(plaintext) > best_fitness: - best_fitness = fitness(plaintext) - best_alphabet = alphabet - print(i, best_alphabet, best_fitness, plaintext) - return best_alphabet, best_fitness - - -def vigenere_keyword_break_mp(message, wordlist=keywords, fitness=Pletters, - chunksize=500): - """Breaks a vigenere cipher using a dictionary and frequency analysis. - - >>> vigenere_keyword_break_mp(vigenere_encipher(sanitise('this is a test ' \ - 'message for the vigenere decipherment'), 'cat'), \ - wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS - ('cat', -52.947271216...) - """ - with Pool() as pool: - helper_args = [(message, word, fitness) - for word in wordlist] - # Gotcha: the helper function here needs to be defined at the top level - # (limitation of Pool.starmap) - breaks = pool.starmap(vigenere_keyword_break_worker, helper_args, - chunksize) - return max(breaks, key=lambda k: k[1]) -vigenere_keyword_break = vigenere_keyword_break_mp - -def vigenere_keyword_break_worker(message, keyword, fitness): - plaintext = vigenere_decipher(message, keyword) - fit = fitness(plaintext) - logger.debug('Vigenere keyword break attempt using key {0} gives fit of ' - '{1} and decrypt starting: {2}'.format(keyword, - fit, sanitise(plaintext)[:50])) - return keyword, fit - - -def vigenere_frequency_break(message, max_key_length=20, fitness=Pletters): - """Breaks a Vigenere cipher with frequency analysis - - >>> vigenere_frequency_break(vigenere_encipher(sanitise("It is time to " \ - "run. She is ready and so am I. I stole Daniel's pocketbook this " \ - "afternoon when he left his jacket hanging on the easel in the " \ - "attic. I jump every time I hear a footstep on the stairs, " \ - "certain that the theft has been discovered and that I will " \ - "be caught. The SS officer visits less often now that he is " \ - "sure"), 'florence')) # doctest: +ELLIPSIS - ('florence', -307.5473096791...) - """ - def worker(message, key_length, fitness): - splits = every_nth(sanitised_message, key_length) - key = ''.join([chr(caesar_break(s)[0] + ord('a')) for s in splits]) - plaintext = vigenere_decipher(message, key) - fit = fitness(plaintext) - return key, fit - sanitised_message = sanitise(message) - results = starmap(worker, [(sanitised_message, i, fitness) - for i in range(1, max_key_length+1)]) - return max(results, key=lambda k: k[1]) - - -def beaufort_frequency_break(message, max_key_length=20, fitness=Pletters): - """Breaks a Beaufort cipher with frequency analysis - - >>> beaufort_frequency_break(beaufort_encipher(sanitise("It is time to " \ - "run. She is ready and so am I. I stole Daniel's pocketbook this " \ - "afternoon when he left his jacket hanging on the easel in the " \ - "attic. I jump every time I hear a footstep on the stairs, " \ - "certain that the theft has been discovered and that I will " \ - "be caught. The SS officer visits less often now " \ - "that he is sure"), 'florence')) # doctest: +ELLIPSIS - ('florence', -307.5473096791...) - """ - def worker(message, key_length, fitness): - splits = every_nth(sanitised_message, key_length) - key = ''.join([chr(-caesar_break(s)[0] % 26 + ord('a')) - for s in splits]) - plaintext = beaufort_decipher(message, key) - fit = fitness(plaintext) - return key, fit - sanitised_message = sanitise(message) - results = starmap(worker, [(sanitised_message, i, fitness) - for i in range(1, max_key_length+1)]) - return max(results, key=lambda k: k[1]) def plot_frequency_histogram(freqs, sort_key=None): x = range(len(freqs.keys()))