From dad438b5689c3748bb0ac4e4aa70802504abcea8 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Wed, 5 Mar 2014 13:17:14 -0500 Subject: [PATCH] Finished the revision of norms, with the revised method for finding the best parameters for breaking caesar ciphers --- caesar_break_parameter_trials.csv | 114 +++++++++++++++++++++------ cipherbreak.py | 9 --- find_best_caesar_break_parameters.py | 85 +++++++++++++------- 3 files changed, 147 insertions(+), 61 deletions(-) diff --git a/caesar_break_parameter_trials.csv b/caesar_break_parameter_trials.csv index 465cb85..6f71f07 100644 --- a/caesar_break_parameter_trials.csv +++ b/caesar_break_parameter_trials.csv @@ -1,23 +1,93 @@ ,message_length -metric+scaling, 300,100,50,30,20,10,5 -l1:normalised, 0.9988, 0.9996, 0.9984, 0.9896, 0.953, 0.736, 0.44 -l1:euclidean_scaled, 0.9996, 1.0, 0.9988, 0.9896, 0.9518, 0.7536, 0.4418 -l1:normalised_with_identity, 0.9606, 0.9922, 0.988, 0.9644, 0.909, 0.7028, 0.4288 -l2:normalised, 0.9996, 0.9994, 0.9984, 0.981, 0.9302, 0.723, 0.4354 -l2:euclidean_scaled, 0.9992, 0.9992, 0.9984, 0.9836, 0.9298, 0.7116, 0.423 -l2:normalised_with_identity, 1.0, 0.9998, 0.9982, 0.986, 0.9322, 0.722, 0.4262 -l3:normalised, 0.9998, 0.999, 0.9952, 0.9536, 0.8742, 0.5964, 0.4078 -l3:euclidean_scaled, 0.9992, 0.9992, 0.9958, 0.9672, 0.8894, 0.6276, 0.4014 -l3:normalised_with_identity, 0.9998, 0.998, 0.97, 0.9002, 0.7686, 0.5484, 0.391 -cosine_distance:normalised, 0.999, 0.9994, 0.9984, 0.9854, 0.934, 0.7092, 0.4338 -cosine_distance:euclidean_scaled, 0.9996, 0.9992, 0.999, 0.9822, 0.9342, 0.7114, 0.4326 -cosine_distance:normalised_with_identity, 0.9994, 0.9994, 0.9984, 0.986, 0.9354, 0.7166, 0.4294 -harmonic_mean:normalised, 0.8154, 0.8382, 0.7618, 0.2696, 0.8678, 0.6736, 0.4566 -harmonic_mean:euclidean_scaled, 0.4756, 0.5108, 0.686, 0.6098, 0.5342, 0.4322, 0.3568 -harmonic_mean:normalised_with_identity, 0.9574, 0.969, 0.952, 0.9254, 0.897, 0.7368, 0.4434 -geometric_mean:normalised, 0.9996, 0.9996, 0.9914, 0.9178, 0.9368, 0.7114, 0.4562 -geometric_mean:euclidean_scaled, 0.9998, 0.999, 0.9962, 0.9534, 0.8824, 0.6548, 0.443 -geometric_mean:normalised_with_identity, 0.9426, 0.9872, 0.9848, 0.9694, 0.9358, 0.7654, 0.4582 -inverse_log_pl:normalised, 0.9994, 0.9996, 0.9992, 0.996, 0.98, 0.8088, 0.488 -inverse_log_pl:euclidean_scaled, 0.9998, 0.9998, 0.9996, 0.996, 0.9826, 0.817, 0.481 -inverse_log_pl:normalised_with_identity, 0.999, 0.9996, 0.9992, 0.9978, 0.9802, 0.8106, 0.483 +scoring, 300, 100, 50, 30, 20, 10, 5 +Pletters, 0.9994, 0.9994, 0.9994, 0.9966, 0.9778, 0.8174, 0.4712 +Pletters, 0.9994, 0.9994, 0.9994, 0.9966, 0.9778, 0.8174, 0.4712 +Pletters, 0.9994, 0.9994, 0.9994, 0.9966, 0.9778, 0.8174, 0.4712 +Pletters, 0.9994, 0.9994, 0.9994, 0.9966, 0.9778, 0.8174, 0.4712 +Pletters, 0.9994, 0.9994, 0.9994, 0.9966, 0.9778, 0.8174, 0.4712 +Pletters, 0.9994, 0.9994, 0.9994, 0.9966, 0.9778, 0.8174, 0.4712 +Pletters, 0.9994, 0.9994, 0.9994, 0.9966, 0.9778, 0.8174, 0.4712 +cosine_distance + euclidean_scaled, 0.9996, 0.9996, 0.9974, 0.9836, 0.9356, 0.7124, 0.4218 +cosine_distance + euclidean_scaled, 0.9996, 0.9996, 0.9974, 0.9836, 0.9356, 0.7124, 0.4218 +cosine_distance + euclidean_scaled, 0.9996, 0.9996, 0.9974, 0.9836, 0.9356, 0.7124, 0.4218 +cosine_distance + euclidean_scaled, 0.9996, 0.9996, 0.9974, 0.9836, 0.9356, 0.7124, 0.4218 +cosine_distance + euclidean_scaled, 0.9996, 0.9996, 0.9974, 0.9836, 0.9356, 0.7124, 0.4218 +cosine_distance + euclidean_scaled, 0.9996, 0.9996, 0.9974, 0.9836, 0.9356, 0.7124, 0.4218 +cosine_distance + euclidean_scaled, 0.9996, 0.9996, 0.9974, 0.9836, 0.9356, 0.7124, 0.4218 +cosine_distance + normalised, 0.9994, 0.9996, 0.998, 0.9836, 0.934, 0.7186, 0.4402 +cosine_distance + normalised, 0.9994, 0.9996, 0.998, 0.9836, 0.934, 0.7186, 0.4402 +cosine_distance + normalised, 0.9994, 0.9996, 0.998, 0.9836, 0.934, 0.7186, 0.4402 +cosine_distance + normalised, 0.9994, 0.9996, 0.998, 0.9836, 0.934, 0.7186, 0.4402 +cosine_distance + normalised, 0.9994, 0.9996, 0.998, 0.9836, 0.934, 0.7186, 0.4402 +cosine_distance + normalised, 0.9994, 0.9996, 0.998, 0.9836, 0.934, 0.7186, 0.4402 +cosine_distance + normalised, 0.9994, 0.9996, 0.998, 0.9836, 0.934, 0.7186, 0.4402 +geometric_mean + euclidean_scaled, 0.9996, 0.9996, 0.99, 0.9506, 0.8892, 0.6562, 0.4368 +geometric_mean + euclidean_scaled, 0.9996, 0.9996, 0.99, 0.9506, 0.8892, 0.6562, 0.4368 +geometric_mean + euclidean_scaled, 0.9996, 0.9996, 0.99, 0.9506, 0.8892, 0.6562, 0.4368 +geometric_mean + euclidean_scaled, 0.9996, 0.9996, 0.99, 0.9506, 0.8892, 0.6562, 0.4368 +geometric_mean + euclidean_scaled, 0.9996, 0.9996, 0.99, 0.9506, 0.8892, 0.6562, 0.4368 +geometric_mean + euclidean_scaled, 0.9996, 0.9996, 0.99, 0.9506, 0.8892, 0.6562, 0.4368 +geometric_mean + euclidean_scaled, 0.9996, 0.9996, 0.99, 0.9506, 0.8892, 0.6562, 0.4368 +geometric_mean + normalised, 0.9996, 0.9992, 0.9902, 0.9222, 0.9408, 0.7062, 0.4568 +geometric_mean + normalised, 0.9996, 0.9992, 0.9902, 0.9222, 0.9408, 0.7062, 0.4568 +geometric_mean + normalised, 0.9996, 0.9992, 0.9902, 0.9222, 0.9408, 0.7062, 0.4568 +geometric_mean + normalised, 0.9996, 0.9992, 0.9902, 0.9222, 0.9408, 0.7062, 0.4568 +geometric_mean + normalised, 0.9996, 0.9992, 0.9902, 0.9222, 0.9408, 0.7062, 0.4568 +geometric_mean + normalised, 0.9996, 0.9992, 0.9902, 0.9222, 0.9408, 0.7062, 0.4568 +geometric_mean + normalised, 0.9996, 0.9992, 0.9902, 0.9222, 0.9408, 0.7062, 0.4568 +harmonic_mean + euclidean_scaled, 0.4688, 0.5122, 0.6894, 0.5948, 0.5258, 0.4426, 0.3642 +harmonic_mean + euclidean_scaled, 0.4688, 0.5122, 0.6894, 0.5948, 0.5258, 0.4426, 0.3642 +harmonic_mean + euclidean_scaled, 0.4688, 0.5122, 0.6894, 0.5948, 0.5258, 0.4426, 0.3642 +harmonic_mean + euclidean_scaled, 0.4688, 0.5122, 0.6894, 0.5948, 0.5258, 0.4426, 0.3642 +harmonic_mean + euclidean_scaled, 0.4688, 0.5122, 0.6894, 0.5948, 0.5258, 0.4426, 0.3642 +harmonic_mean + euclidean_scaled, 0.4688, 0.5122, 0.6894, 0.5948, 0.5258, 0.4426, 0.3642 +harmonic_mean + euclidean_scaled, 0.4688, 0.5122, 0.6894, 0.5948, 0.5258, 0.4426, 0.3642 +harmonic_mean + normalised, 0.8134, 0.8368, 0.7672, 0.2674, 0.8608, 0.6736, 0.453 +harmonic_mean + normalised, 0.8134, 0.8368, 0.7672, 0.2674, 0.8608, 0.6736, 0.453 +harmonic_mean + normalised, 0.8134, 0.8368, 0.7672, 0.2674, 0.8608, 0.6736, 0.453 +harmonic_mean + normalised, 0.8134, 0.8368, 0.7672, 0.2674, 0.8608, 0.6736, 0.453 +harmonic_mean + normalised, 0.8134, 0.8368, 0.7672, 0.2674, 0.8608, 0.6736, 0.453 +harmonic_mean + normalised, 0.8134, 0.8368, 0.7672, 0.2674, 0.8608, 0.6736, 0.453 +harmonic_mean + normalised, 0.8134, 0.8368, 0.7672, 0.2674, 0.8608, 0.6736, 0.453 +l1 + euclidean_scaled, 0.9998, 0.9994, 0.9984, 0.9904, 0.9502, 0.7558, 0.4348 +l1 + euclidean_scaled, 0.9998, 0.9994, 0.9984, 0.9904, 0.9502, 0.7558, 0.4348 +l1 + euclidean_scaled, 0.9998, 0.9994, 0.9984, 0.9904, 0.9502, 0.7558, 0.4348 +l1 + euclidean_scaled, 0.9998, 0.9994, 0.9984, 0.9904, 0.9502, 0.7558, 0.4348 +l1 + euclidean_scaled, 0.9998, 0.9994, 0.9984, 0.9904, 0.9502, 0.7558, 0.4348 +l1 + euclidean_scaled, 0.9998, 0.9994, 0.9984, 0.9904, 0.9502, 0.7558, 0.4348 +l1 + euclidean_scaled, 0.9998, 0.9994, 0.9984, 0.9904, 0.9502, 0.7558, 0.4348 +l1 + normalised, 0.9998, 0.9998, 0.9986, 0.9882, 0.955, 0.7252, 0.4432 +l1 + normalised, 0.9998, 0.9998, 0.9986, 0.9882, 0.955, 0.7252, 0.4432 +l1 + normalised, 0.9998, 0.9998, 0.9986, 0.9882, 0.955, 0.7252, 0.4432 +l1 + normalised, 0.9998, 0.9998, 0.9986, 0.9882, 0.955, 0.7252, 0.4432 +l1 + normalised, 0.9998, 0.9998, 0.9986, 0.9882, 0.955, 0.7252, 0.4432 +l1 + normalised, 0.9998, 0.9998, 0.9986, 0.9882, 0.955, 0.7252, 0.4432 +l1 + normalised, 0.9998, 0.9998, 0.9986, 0.9882, 0.955, 0.7252, 0.4432 +l2 + euclidean_scaled, 0.9996, 0.9988, 0.9992, 0.9786, 0.9368, 0.712, 0.4336 +l2 + euclidean_scaled, 0.9996, 0.9988, 0.9992, 0.9786, 0.9368, 0.712, 0.4336 +l2 + euclidean_scaled, 0.9996, 0.9988, 0.9992, 0.9786, 0.9368, 0.712, 0.4336 +l2 + euclidean_scaled, 0.9996, 0.9988, 0.9992, 0.9786, 0.9368, 0.712, 0.4336 +l2 + euclidean_scaled, 0.9996, 0.9988, 0.9992, 0.9786, 0.9368, 0.712, 0.4336 +l2 + euclidean_scaled, 0.9996, 0.9988, 0.9992, 0.9786, 0.9368, 0.712, 0.4336 +l2 + euclidean_scaled, 0.9996, 0.9988, 0.9992, 0.9786, 0.9368, 0.712, 0.4336 +l2 + normalised, 0.9998, 0.999, 0.998, 0.9818, 0.933, 0.709, 0.4356 +l2 + normalised, 0.9998, 0.999, 0.998, 0.9818, 0.933, 0.709, 0.4356 +l2 + normalised, 0.9998, 0.999, 0.998, 0.9818, 0.933, 0.709, 0.4356 +l2 + normalised, 0.9998, 0.999, 0.998, 0.9818, 0.933, 0.709, 0.4356 +l2 + normalised, 0.9998, 0.999, 0.998, 0.9818, 0.933, 0.709, 0.4356 +l2 + normalised, 0.9998, 0.999, 0.998, 0.9818, 0.933, 0.709, 0.4356 +l2 + normalised, 0.9998, 0.999, 0.998, 0.9818, 0.933, 0.709, 0.4356 +l3 + euclidean_scaled, 0.9996, 0.999, 0.996, 0.9684, 0.8934, 0.6282, 0.4084 +l3 + euclidean_scaled, 0.9996, 0.999, 0.996, 0.9684, 0.8934, 0.6282, 0.4084 +l3 + euclidean_scaled, 0.9996, 0.999, 0.996, 0.9684, 0.8934, 0.6282, 0.4084 +l3 + euclidean_scaled, 0.9996, 0.999, 0.996, 0.9684, 0.8934, 0.6282, 0.4084 +l3 + euclidean_scaled, 0.9996, 0.999, 0.996, 0.9684, 0.8934, 0.6282, 0.4084 +l3 + euclidean_scaled, 0.9996, 0.999, 0.996, 0.9684, 0.8934, 0.6282, 0.4084 +l3 + euclidean_scaled, 0.9996, 0.999, 0.996, 0.9684, 0.8934, 0.6282, 0.4084 +l3 + normalised, 1.0, 0.9986, 0.9932, 0.963, 0.8696, 0.594, 0.4122 +l3 + normalised, 1.0, 0.9986, 0.9932, 0.963, 0.8696, 0.594, 0.4122 +l3 + normalised, 1.0, 0.9986, 0.9932, 0.963, 0.8696, 0.594, 0.4122 +l3 + normalised, 1.0, 0.9986, 0.9932, 0.963, 0.8696, 0.594, 0.4122 +l3 + normalised, 1.0, 0.9986, 0.9932, 0.963, 0.8696, 0.594, 0.4122 +l3 + normalised, 1.0, 0.9986, 0.9932, 0.963, 0.8696, 0.594, 0.4122 +l3 + normalised, 1.0, 0.9986, 0.9932, 0.963, 0.8696, 0.594, 0.4122 diff --git a/cipherbreak.py b/cipherbreak.py index 3993a42..03165e5 100644 --- a/cipherbreak.py +++ b/cipherbreak.py @@ -57,15 +57,6 @@ def frequencies(text): return collections.Counter(c for c in text) -def frequency_compare(text, target_frequency, frequency_scaling, metric): - counts = frequency_scaling(frequencies(text)) - return -1 * metric(target_frequency, counts) - -def euclidean_compare(text): - return frequency_compare(text, norms.euclidean_scale(english_counts), - norms.euclidean_scale, norms.euclidean_distance) - - def caesar_break(message, fitness=Pletters): """Breaks a Caesar cipher using frequency analysis diff --git a/find_best_caesar_break_parameters.py b/find_best_caesar_break_parameters.py index edab90f..9ed5348 100644 --- a/find_best_caesar_break_parameters.py +++ b/find_best_caesar_break_parameters.py @@ -11,55 +11,80 @@ corpus_length = len(corpus) euclidean_scaled_english_counts = norms.euclidean_scale(english_counts) -metrics = [{'func': norms.l1, 'name': 'l1'}, - {'func': norms.l2, 'name': 'l2'}, - {'func': norms.l3, 'name': 'l3'}, - {'func': norms.cosine_distance, 'name': 'cosine_distance'}, - {'func': norms.harmonic_mean, 'name': 'harmonic_mean'}, - {'func': norms.geometric_mean, 'name': 'geometric_mean'}, - {'func': norms.inverse_log_pl, 'name': 'inverse_log_pl'}] +# def frequency_compare(text, target_frequency, frequency_scaling, metric): +# counts = frequency_scaling(frequencies(text)) +# return -1 * metric(target_frequency, counts) + +# def euclidean_compare(text): +# return frequency_compare(text, norms.euclidean_scale(english_counts), +# norms.euclidean_scale, norms.euclidean_distance) + +metrics = [{'func': norms.l1, 'invert': True, 'name': 'l1'}, + {'func': norms.l2, 'invert': True, 'name': 'l2'}, + {'func': norms.l3, 'invert': True, 'name': 'l3'}, + {'func': norms.cosine_distance, 'invert': False, 'name': 'cosine_distance'}, + {'func': norms.harmonic_mean, 'invert': True, 'name': 'harmonic_mean'}, + {'func': norms.geometric_mean, 'invert': True, 'name': 'geometric_mean'}] scalings = [{'corpus_frequency': normalised_english_counts, 'scaling': norms.normalise, 'name': 'normalised'}, {'corpus_frequency': euclidean_scaled_english_counts, 'scaling': norms.euclidean_scale, - 'name': 'euclidean_scaled'}, - {'corpus_frequency': normalised_english_counts, - 'scaling': norms.identity_scale, - 'name': 'normalised_with_identity'}] + 'name': 'euclidean_scaled'}] message_lengths = [300, 100, 50, 30, 20, 10, 5] trials = 5000 -scores = collections.defaultdict(int) +scores = {} + + +def make_frequency_compare_function(target_frequency, frequency_scaling, metric, invert): + def frequency_compare(text): + counts = frequency_scaling(frequencies(text)) + if invert: + score = -1 * metric(target_frequency, counts) + else: + score = metric(target_frequency, counts) + return score + return frequency_compare + + +def scoring_functions(): + return [{'func': make_frequency_compare_function(s['corpus_frequency'], + s['scaling'], m['func'], m['invert']), + 'name': '{} + {}'.format(m['name'], s['name'])} + for m in metrics + for s in scalings] + [{'func': Pletters, 'name': 'Pletters'}] -def eval_all(): - list(itertools.starmap(eval_one_parameter_set, - itertools.product(metrics, scalings, message_lengths))) +def eval_scores(): + [eval_one_score(f, l) + for f in scoring_functions() + for l in message_lengths] -def eval_one_parameter_set(metric, scaling, message_length): +def eval_one_score(scoring_function, message_length): + print(scoring_function['name'], message_length) + if scoring_function['name'] not in scores: + scores[scoring_function['name']] = collections.defaultdict(int) for _ in range(trials): sample_start = random.randint(0, corpus_length - message_length) sample = corpus[sample_start:(sample_start + message_length)] key = random.randint(1, 25) - sample_ciphertext = caesar_encipher(sample, key) - found_key, _ = caesar_break(sample_ciphertext, - metric=metric['func'], - target_counts=scaling['corpus_frequency'], - message_frequency_scaling=scaling['scaling']) + ciphertext = caesar_encipher(sample, key) + found_key, _ = caesar_break(ciphertext, scoring_function['func']) if found_key == key: - scores[(metric['name'], scaling['name'], message_length)] += 1 - return scores[(metric['name'], scaling['name'], message_length)] + scores[scoring_function['name']][message_length] += 1 + return scores[scoring_function['name']][message_length] def show_results(): with open('caesar_break_parameter_trials.csv', 'w') as f: print(',message_length', file = f) - print('metric+scaling,', ','.join([str(l) for l in message_lengths]), file = f) - for (metric, scaling) in itertools.product(metrics, scalings): - print('{}:{}'.format(metric['name'], scaling['name']), end='', file=f) - for l in message_lengths: - print(',', scores[(metric['name'], scaling['name'], l)] / trials, end='', file=f) - print('', file = f) + print('scoring,', ', '.join([str(l) for l in message_lengths]), file = f) + for scoring in sorted(scores.keys()): + for length in message_lengths: + print(scoring, end='', sep='', file=f) + for l in message_lengths: + print(',', scores[scoring][l] / trials, end='', file=f) + print('', file = f) -eval_all() +eval_scores() show_results() -- 2.34.1