cipher/hill.py

   1 import multiprocessing
   2 import numpy as np
   3 from numpy import matrix
   4 from numpy import linalg
   5 from support.utilities import *
   6 from support.language_models import *
   7 from cipher.affine import modular_division_table
   8
   9 from logger import logger
  10
  11
  12 def hill_encipher(matrix, message_letters, fillvalue='a'):
  13     """Hill cipher
  14
  15     >>> hill_encipher(np.matrix([[7,8], [11,11]]), 'hellothere')
  16     'drjiqzdrvx'
  17     >>> hill_encipher(np.matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]]), \
  18         'hello there')
  19     'tfjflpznvyac'
  20     """
  21     n = len(matrix)
  22     sanitised_message = sanitise(message_letters)
  23     if len(sanitised_message) % n != 0:
  24         padding = fillvalue[0] * (n - len(sanitised_message) % n)
  25     else:
  26         padding = ''
  27     message = [pos(c) for c in sanitised_message + padding]
  28     message_chunks = [message[i:i+n] for i in range(0, len(message), n)]
  29     # message_chunks = chunks(message, len(matrix), fillvalue=None)
  30     enciphered_chunks = [((matrix * np.matrix(c).T).T).tolist()[0]
  31             for c in message_chunks]
  32     return cat([unpos(round(l))
  33             for l in sum(enciphered_chunks, [])])
  34
  35 def hill_decipher(matrix, message, fillvalue='a'):
  36     """Hill cipher
  37
  38     >>> hill_decipher(np.matrix([[7,8], [11,11]]), 'drjiqzdrvx')
  39     'hellothere'
  40     >>> hill_decipher(np.matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]]), \
  41         'tfjflpznvyac')
  42     'hellothereaa'
  43     """
  44     adjoint = linalg.det(matrix)*linalg.inv(matrix)
  45     inverse_determinant = modular_division_table[int(round(linalg.det(matrix))) % 26, 1]
  46     inverse_matrix = (inverse_determinant * adjoint) % 26
  47     return hill_encipher(inverse_matrix, message, fillvalue)
  48
  49 def hill_break(message, matrix_size=2, fitness=Pletters,
  50     number_of_solutions=1, chunksize=500):
  51
  52     all_matrices = [np.matrix(list(m))
  53         for m in itertools.product([list(r)
  54             for r in itertools.product(range(26), repeat=matrix_size)],
  55         repeat=matrix_size)]
  56     valid_matrices = [m for m, d in
  57         zip(all_matrices, (int(round(linalg.det(m))) for m in all_matrices))
  58                   if d != 0
  59                   if d % 2 != 0
  60                   if d % 13 != 0 ]
  61     with multiprocessing.Pool() as pool:
  62         helper_args = [(message, matrix, fitness)
  63                        for matrix in valid_matrices]
  64         # Gotcha: the helper function here needs to be defined at the top level
  65         #   (limitation of Pool.starmap)
  66         breaks = pool.starmap(hill_break_worker, helper_args, chunksize)
  67         if number_of_solutions == 1:
  68             return max(breaks, key=lambda k: k[1])
  69         else:
  70             return sorted(breaks, key=lambda k: k[1], reverse=True)[:number_of_solutions]
  71
  72 def hill_break_worker(message, matrix, fitness):
  73     plaintext = hill_decipher(matrix, message)
  74     fit = fitness(plaintext)
  75     logger.debug('Hill cipher break attempt using key {0} gives fit of '
  76                  '{1} and decrypt starting: {2}'.format(matrix,
  77                      fit, sanitise(plaintext)[:50]))
  78     return matrix, fit
  79
  80 if __name__ == "__main__":
  81     import doctest