36ffa856b49ad45d987af125c5bcde468aeae8da
[szyfrow.git] / autokey.py
1 import math
2 import multiprocessing
3 from szyfrow.support.utilities import *
4 from szyfrow.support.language_models import *
5 from szyfrow.caesar import caesar_encipher_letter, caesar_decipher_letter
6
7
8 def autokey_encipher(message, keyword):
9 """Encipher with the autokey cipher
10
11 >>> autokey_encipher('meetatthefountain', 'kilt')
12 'wmpmmxxaeyhbryoca'
13 """
14 shifts = [pos(l) for l in keyword + message]
15 pairs = zip(message, shifts)
16 return cat([caesar_encipher_letter(l, k) for l, k in pairs])
17
18 def autokey_decipher(ciphertext, keyword):
19 """Decipher with the autokey cipher
20
21 >>> autokey_decipher('wmpmmxxaeyhbryoca', 'kilt')
22 'meetatthefountain'
23 """
24 plaintext = []
25 keys = list(keyword)
26 for c in ciphertext:
27 plaintext_letter = caesar_decipher_letter(c, pos(keys[0]))
28 plaintext += [plaintext_letter]
29 keys = keys[1:] + [plaintext_letter]
30 return cat(plaintext)
31
32
33
34 def autokey_sa_break( message
35 , min_keylength=2
36 , max_keylength=20
37 , workers=10
38 , initial_temperature=200
39 , max_iterations=20000
40 , fitness=Pletters
41 , chunksize=1
42 , result_count=1
43 ):
44 """Break an autokey cipher by simulated annealing
45 """
46 worker_args = []
47 ciphertext = sanitise(message)
48 for keylength in range(min_keylength, max_keylength+1):
49 for i in range(workers):
50 key = cat(random.choice(string.ascii_lowercase) for _ in range(keylength))
51 worker_args.append((ciphertext, key,
52 initial_temperature, max_iterations, fitness))
53
54 with multiprocessing.Pool() as pool:
55 breaks = pool.starmap(autokey_sa_break_worker,
56 worker_args, chunksize)
57 if result_count <= 1:
58 return max(breaks, key=lambda k: k[1])
59 else:
60 return sorted(set(breaks), key=lambda k: k[1], reverse=True)[:result_count]
61
62
63 def autokey_sa_break_worker(message, key,
64 t0, max_iterations, fitness):
65
66 temperature = t0
67
68 dt = t0 / (0.9 * max_iterations)
69
70 plaintext = autokey_decipher(message, key)
71 current_fitness = fitness(plaintext)
72 current_key = key
73
74 best_key = current_key
75 best_fitness = current_fitness
76 best_plaintext = plaintext
77
78 # print('starting for', max_iterations)
79 for i in range(max_iterations):
80 swap_pos = random.randrange(len(current_key))
81 swap_char = random.choice(string.ascii_lowercase)
82
83 new_key = current_key[:swap_pos] + swap_char + current_key[swap_pos+1:]
84
85 plaintext = autokey_decipher(message, new_key)
86 new_fitness = fitness(plaintext)
87 try:
88 sa_chance = math.exp((new_fitness - current_fitness) / temperature)
89 except (OverflowError, ZeroDivisionError):
90 # print('exception triggered: new_fit {}, current_fit {}, temp {}'.format(new_fitness, current_fitness, temperature))
91 sa_chance = 0
92 if (new_fitness > current_fitness or random.random() < sa_chance):
93 current_fitness = new_fitness
94 current_key = new_key
95
96 if current_fitness > best_fitness:
97 best_key = current_key
98 best_fitness = current_fitness
99 best_plaintext = plaintext
100
101 temperature = max(temperature - dt, 0.001)
102
103 # print(best_key, best_fitness, best_plaintext[:70])
104 return best_key, best_fitness # current_alphabet, current_fitness
105
106 if __name__ == "__main__":
107 import doctest