From f23ebe9e009e465a31bd0aac2a9d9cd82da642f8 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Tue, 24 Jun 2014 15:54:48 +0100 Subject: [PATCH] Added hill-climbing for monoalphabetic substitution ciphers --- cipherbreak.py | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) diff --git a/cipherbreak.py b/cipherbreak.py index e89407c..eae56cf 100644 --- a/cipherbreak.py +++ b/cipherbreak.py @@ -2,6 +2,7 @@ import string import collections import norms import logging +import random from itertools import zip_longest, cycle, permutations, starmap from segment import segment from multiprocessing import Pool @@ -228,6 +229,51 @@ def column_transposition_break_mp(message, translist=transpositions, return max(breaks, key=lambda k: k[1]) column_transposition_break = column_transposition_break_mp +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=100, + 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 column_transposition_break_worker(message, transposition, fillcolumnwise, emptycolumnwise, fitness): plaintext = column_transposition_decipher(message, transposition, -- 2.34.1