From 04150429da13371a54282c0d808ea3b45a73e18d Mon Sep 17 00:00:00 2001
From: Neil Smith <neil.github@njae.me.uk>
Date: Fri, 22 Nov 2013 09:10:18 +0000
Subject: [PATCH 1/1] Done Vigenere ciphers and breaking wth a keyword
 dictionary. Solved challenge 5

---
 cipher.py | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 86 insertions(+), 4 deletions(-)

diff --git a/cipher.py b/cipher.py
index 3251edd..84a4915 100644
--- a/cipher.py
+++ b/cipher.py
@@ -3,7 +3,7 @@ import collections
 import norms
 import logging
 import math
-from itertools import zip_longest, repeat
+from itertools import zip_longest, repeat, cycle
 from segment import segment
 from multiprocessing import Pool
 
@@ -497,7 +497,24 @@ def column_transposition_worker(message, keyword,
     return combine_every_nth(transposed_columns)
 
 def vigenere_encipher(message, keyword):
-    
+    """Vigenere encipher
+
+    >>> vigenere_encipher('hello', 'abc')
+    'hfnlp'
+    """
+    shifts = [ord(l) - ord('a') for l in sanitise(keyword)]
+    pairs = zip(message, cycle(shifts))
+    return ''.join([caesar_encipher_letter(l, k) for l, k in pairs])
+
+def vigenere_decipher(message, keyword):
+    """Vigenere decipher
+
+    >>> vigenere_decipher('hfnlp', 'abc')
+    'hello'
+    """
+    shifts = [ord(l) - ord('a') for l in sanitise(keyword)]
+    pairs = zip(message, cycle(shifts))
+    return ''.join([caesar_decipher_letter(l, k) for l, k in pairs])
 
 
 
@@ -632,10 +649,10 @@ def keyword_break_mp(message,
                        for word in wordlist for wrap in range(3)]
         # Gotcha: the helper function here needs to be defined at the top level 
         #   (limitation of Pool.starmap)
-        breaks = pool.starmap(keyword_break_one, helper_args, chunksize) 
+        breaks = pool.starmap(keyword_break_worker, helper_args, chunksize) 
         return min(breaks, key=lambda k: k[1])
 
-def keyword_break_one(message, keyword, wrap_alphabet, metric, target_counts, 
+def keyword_break_worker(message, keyword, wrap_alphabet, metric, target_counts, 
                       message_frequency_scaling):
     plaintext = keyword_decipher(message, keyword, wrap_alphabet)
     counts = message_frequency_scaling(letter_frequencies(plaintext))
@@ -767,6 +784,71 @@ def column_transposition_break_worker(message, keyword, metric, target_counts,
                              sanitise(plaintext)[:50]))
     return keyword, fit
 
+def vigenere_keyword_break(message, 
+                  wordlist=keywords, 
+                  metric=norms.euclidean_distance, 
+                  target_counts=normalised_english_counts, 
+                  message_frequency_scaling=norms.normalise):
+    """Breaks a vigenere cipher using a dictionary and 
+    frequency analysis
+    
+    >>> vigenere_keyword_break(keyword_encipher('this is a test message for the ' \
+             'keyword decipherment', 'elephant', 1), \
+             wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
+    ('elephant', 0.7166585201707...)
+    """
+    best_keyword = ''
+    best_fit = float("inf")
+    for keyword in wordlist:
+        plaintext = vigenere_decipher(message, keyword)
+        counts = message_frequency_scaling(letter_frequencies(plaintext))
+        fit = metric(target_counts, counts)
+        logger.debug('Vigenere break attempt using key {0} '
+                         'gives fit of {1} and decrypt starting: {2}'.format(
+                             keyword, fit, 
+                             sanitise(plaintext)[:50]))
+        if fit < best_fit:
+            best_fit = fit
+            best_keyword = keyword
+    logger.info('Vigenere break best fit with key {0} gives fit '
+                'of {1} and decrypt starting: {2}'.format(best_keyword, 
+                    best_fit, sanitise(
+                        vigenere_decipher(message, best_keyword))[:50]))
+    return best_keyword, best_fit
+
+def vigenere_keyword_break_mp(message, 
+                     wordlist=keywords, 
+                     metric=norms.euclidean_distance, 
+                     target_counts=normalised_english_counts, 
+                     message_frequency_scaling=norms.normalise, 
+                     chunksize=500):
+    """Breaks a vigenere cipher using a dictionary and 
+    frequency analysis
+
+    >>> vigenere_keyword_break_mp(keyword_encipher('this is a test message for the ' \
+             'keyword decipherment', 'elephant', 1), \
+             wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
+    ('elephant', 0.7166585201707...)
+    """
+    with Pool() as pool:
+        helper_args = [(message, word, metric, target_counts, 
+                        message_frequency_scaling) 
+                       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 min(breaks, key=lambda k: k[1])
+
+def vigenere_keyword_break_worker(message, keyword, metric, target_counts, 
+                      message_frequency_scaling):
+    plaintext = vigenere_decipher(message, keyword)
+    counts = message_frequency_scaling(letter_frequencies(plaintext))
+    fit = metric(target_counts, counts)
+    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
+
 
 
 if __name__ == "__main__":
-- 
2.34.1