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