6 logger
= logging
.getLogger(__name__
)
7 logger
.addHandler(logging
.FileHandler('cipher.log'))
8 logger
.setLevel(logging
.WARNING
)
9 logger
.setLevel(logging
.INFO
)
11 english_counts
= collections
.defaultdict(int)
12 with
open('count_1l.txt', 'r') as f
:
14 (letter
, count
) = line
.split("\t")
15 english_counts
[letter
] = int(count
)
16 normalised_english_counts
= norms
.normalise(english_counts
)
19 modular_division_table
= [[0]*26 for x
in range(26)]
23 modular_division_table
[b
][c
] = a
25 modular_division_table_one_based
= [[0]*27 for x
in range(27)]
28 c
= ((a
* b
)-1) % 26 + 1
29 modular_division_table_one_based
[b
][c
] = a
34 """Remove all non-alphabetic characters and convert the text to lowercase
36 >>> sanitise('The Quick')
38 >>> sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')
39 'thequickbrownfoxjumpedoverthelazydog'
41 sanitised
= [c
.lower() for c
in text
if c
in string
.ascii_letters
]
42 return ''.join(sanitised
)
45 return [tuple(text
[i
:i
+n
]) for i
in range(len(text
)-n
+1)]
47 def letter_frequencies(text
):
48 """Count the number of occurrences of each character in text
50 >>> sorted(letter_frequencies('abcdefabc').items())
51 [('a', 2), ('b', 2), ('c', 2), ('d', 1), ('e', 1), ('f', 1)]
52 >>> sorted(letter_frequencies('the quick brown fox jumped over the lazy dog').items())
53 [(' ', 8), ('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1), ('g', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('n', 1), ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2), ('v', 1), ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
54 >>> sorted(letter_frequencies('The Quick BROWN fox jumped! over... the (9lazy) DOG').items())
55 [(' ', 8), ('!', 1), ('(', 1), (')', 1), ('.', 3), ('9', 1), ('B', 1), ('D', 1), ('G', 1), ('N', 1), ('O', 2), ('Q', 1), ('R', 1), ('T', 1), ('W', 1), ('a', 1), ('c', 1), ('d', 1), ('e', 4), ('f', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('o', 2), ('p', 1), ('r', 1), ('t', 1), ('u', 2), ('v', 1), ('x', 1), ('y', 1), ('z', 1)]
56 >>> sorted(letter_frequencies(sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')).items())
57 [('a', 1), ('b', 1), ('c', 1), ('d', 2), ('e', 4), ('f', 1), ('g', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('n', 1), ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('t', 2), ('u', 2), ('v', 1), ('w', 1), ('x', 1), ('y', 1), ('z', 1)]
59 counts
= collections
.defaultdict(int)
64 def caesar_encipher_letter(letter
, shift
):
65 """Encipher a letter, given a shift amount
67 >>> caesar_encipher_letter('a', 1)
69 >>> caesar_encipher_letter('a', 2)
71 >>> caesar_encipher_letter('b', 2)
73 >>> caesar_encipher_letter('x', 2)
75 >>> caesar_encipher_letter('y', 2)
77 >>> caesar_encipher_letter('z', 2)
79 >>> caesar_encipher_letter('z', -1)
81 >>> caesar_encipher_letter('a', -1)
84 if letter
in string
.ascii_letters
:
85 if letter
in string
.ascii_uppercase
:
86 alphabet_start
= ord('A')
88 alphabet_start
= ord('a')
89 return chr(((ord(letter
) - alphabet_start
+ shift
) % 26) + alphabet_start
)
93 def caesar_decipher_letter(letter
, shift
):
94 """Decipher a letter, given a shift amount
96 >>> caesar_decipher_letter('b', 1)
98 >>> caesar_decipher_letter('b', 2)
101 return caesar_encipher_letter(letter
, -shift
)
103 def caesar_encipher(message
, shift
):
104 """Encipher a message with the Caesar cipher of given shift
106 >>> caesar_encipher('abc', 1)
108 >>> caesar_encipher('abc', 2)
110 >>> caesar_encipher('abcxyz', 2)
112 >>> caesar_encipher('ab cx yz', 2)
115 enciphered
= [caesar_encipher_letter(l
, shift
) for l
in message
]
116 return ''.join(enciphered
)
118 def caesar_decipher(message
, shift
):
119 """Encipher a message with the Caesar cipher of given shift
121 >>> caesar_decipher('bcd', 1)
123 >>> caesar_decipher('cde', 2)
125 >>> caesar_decipher('cd ez ab', 2)
128 return caesar_encipher(message
, -shift
)
130 def affine_encipher_letter(letter
, multiplier
=1, adder
=0, one_based
=True):
131 """Encipher a letter, given a multiplier and adder
133 >>> ''.join([affine_encipher_letter(l, 3, 5, True) for l in string.ascii_uppercase])
134 'HKNQTWZCFILORUXADGJMPSVYBE'
135 >>> ''.join([affine_encipher_letter(l, 3, 5, False) for l in string.ascii_uppercase])
136 'FILORUXADGJMPSVYBEHKNQTWZC'
138 if letter
in string
.ascii_letters
:
139 if letter
in string
.ascii_uppercase
:
140 alphabet_start
= ord('A')
142 alphabet_start
= ord('a')
143 letter_number
= ord(letter
) - alphabet_start
144 if one_based
: letter_number
+= 1
145 raw_cipher_number
= (letter_number
* multiplier
+ adder
)
148 cipher_number
= (raw_cipher_number
- 1) % 26
150 cipher_number
= raw_cipher_number
% 26
151 return chr(cipher_number
+ alphabet_start
)
155 def affine_decipher_letter(letter
, multiplier
=1, adder
=0, one_based
=True):
156 """Encipher a letter, given a multiplier and adder
158 >>> ''.join([affine_decipher_letter(l, 3, 5, True) for l in 'HKNQTWZCFILORUXADGJMPSVYBE'])
159 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
160 >>> ''.join([affine_decipher_letter(l, 3, 5, False) for l in 'FILORUXADGJMPSVYBEHKNQTWZC'])
161 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
163 if letter
in string
.ascii_letters
:
164 if letter
in string
.ascii_uppercase
:
165 alphabet_start
= ord('A')
167 alphabet_start
= ord('a')
168 cipher_number
= ord(letter
) - alphabet_start
169 if one_based
: cipher_number
+= 1
172 plaintext_number
= (modular_division_table_one_based
[multiplier
][(cipher_number
- adder
+ 26) % 26] - 1) % 26
174 #plaintext_number = (modular_division_table[multiplier][cipher_number] - adder) % 26
175 plaintext_number
= modular_division_table
[multiplier
][(cipher_number
- adder
+ 26) % 26]
176 return chr(plaintext_number
+ alphabet_start
)
180 def affine_encipher(message
, multiplier
=1, adder
=0, one_based
=True):
181 """Encipher a message
183 >>> affine_encipher('hours passed during which jerico tried every trick he could think of', 15, 22, True)
184 'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
187 enciphered
= [affine_encipher_letter(l
, multiplier
, adder
, one_based
) for l
in message
]
188 return ''.join(enciphered
)
190 def affine_decipher(message
, multiplier
=1, adder
=0, one_based
=True):
191 """Decipher a message
193 >>> affine_decipher('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh', 15, 22, True)
194 'hours passed during which jerico tried every trick he could think of'
196 enciphered
= [affine_decipher_letter(l
, multiplier
, adder
, one_based
) for l
in message
]
197 return ''.join(enciphered
)
200 def caesar_break(message
, metric
=norms
.euclidean_distance
, target_frequencies
=normalised_english_counts
, message_frequency_scaling
=norms
.normalise
):
201 """Breaks a Caesar cipher using frequency analysis
203 >>> caesar_break('ibxcsyorsaqcheyklxivoexlevmrimwxsfiqevvmihrsasrxliwyrhecjsppsamrkwleppfmergefifvmhixscsymjcsyqeoixlm')
204 (4, 0.3186395289018361)
205 >>> caesar_break('wxwmaxdgheetgwuxztgptedbgznitgwwhpguxyhkxbmhvvtlbhgteeraxlmhiixweblmxgxwmhmaxybkbgztgwztsxwbgmxgmert')
206 (19, 0.4215290123583277)
207 >>> caesar_break('yltbbqnqnzvguvaxurorgenafsbezqvagbnornfgsbevpnaabjurersvaquvzyvxrnznazlybequrvfohgriraabjtbaruraprur')
208 (13, 0.31602920807545154)
210 sanitised_message
= sanitise(message
)
212 best_fit
= float("inf")
213 for shift
in range(26):
214 plaintext
= caesar_decipher(sanitised_message
, shift
)
215 frequencies
= message_frequency_scaling(letter_frequencies(plaintext
))
216 fit
= metric(target_frequencies
, frequencies
)
217 logger
.info('Caesar break attempt using key {0} gives fit of {1} and decrypt starting: {2}'.format(shift
, fit
, plaintext
[:50]))
221 logger
.info('Caesar break best fit: key {0} gives fit of {1} and decrypt starting: {2}'.format(best_shift
, best_fit
, caesar_decipher(sanitised_message
, best_shift
)[:50]))
222 return best_shift
, best_fit
224 def affine_break(message
, metric
=norms
.euclidean_distance
, target_frequencies
=normalised_english_counts
, message_frequency_scaling
=norms
.normalise
):
225 """Breaks an affine cipher using frequency analysis
227 >>> affine_break('lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh jm bfmibj umis hfsul axubafkjamx. ls kffkxwsd jls ofgbjmwfkiu olfmxmtmwaokttg jlsx ls kffkxwsd jlsi zg tsxwjl. jlsx ls umfjsd jlsi zg hfsqysxog. ls dmmdtsd mx jls bats mh bkbsf. ls bfmctsd kfmyxd jls lyj, mztanamyu xmc jm clm cku tmmeaxw kj lai kxd clm ckuxj.')
228 ((15, 22, True), 0.2357036181865554)
230 sanitised_message
= sanitise(message
)
233 best_one_based
= True
234 best_fit
= float("inf")
235 for one_based
in [True, False]:
236 for multiplier
in range(1, 26, 2):
237 for adder
in range(26):
238 plaintext
= affine_decipher(sanitised_message
, multiplier
, adder
, one_based
)
239 frequencies
= message_frequency_scaling(letter_frequencies(plaintext
))
240 fit
= metric(target_frequencies
, frequencies
)
241 logger
.info('Affine break attempt using key {0}x+{1} ({2}) gives fit of {3} and decrypt starting: {4}'.format(multiplier
, adder
, one_based
, fit
, plaintext
[:50]))
244 best_multiplier
= multiplier
246 best_one_based
= one_based
247 logger
.info('Affine break best fit with key {0}x+{1} ({2}) gives fit of {3} and decrypt starting: {4}'.format(best_multiplier
, best_adder
, best_one_based
, best_fit
, affine_decipher(sanitised_message
, best_multiplier
, best_adder
, best_one_based
)[:50]))
248 return (best_multiplier
, best_adder
, best_one_based
), best_fit
251 if __name__
== "__main__":