import collections
import norms
import logging
+import math
+from itertools import zip_longest
+from segment import segment
+from multiprocessing import Pool
+
+# To time a run:
+#
+# import timeit
+# c5a = open('2012/5a.ciphertext', 'r').read()
+# timeit.timeit('keyword_break(c5a)', setup='gc.enable() ; from __main__ import c5a ; from cipher import keyword_break', number=1)
+
logger = logging.getLogger(__name__)
logger.addHandler(logging.FileHandler('cipher.log'))
logger.setLevel(logging.WARNING)
#logger.setLevel(logging.INFO)
+#logger.setLevel(logging.DEBUG)
english_counts = collections.defaultdict(int)
with open('count_1l.txt', 'r') as f:
for line in f:
(letter, count) = line.split("\t")
english_counts[letter] = int(count)
-normalised_english_counts = norms.normalise(english_counts)
+normalised_english_counts = norms.normalise(english_counts)
+
+english_bigram_counts = collections.defaultdict(int)
+with open('count_2l.txt', 'r') as f:
+ for line in f:
+ (bigram, count) = line.split("\t")
+ english_bigram_counts[bigram] = int(count)
+normalised_english_bigram_counts = norms.normalise(english_bigram_counts)
-keywords = []
with open('words.txt', 'r') as f:
keywords = [line.rstrip() for line in f]
-
modular_division_table = [[0]*26 for x in range(26)]
for a in range(26):
for b in range(26):
c = (a * b) % 26
modular_division_table[b][c] = a
-modular_division_table_one_based = [[0]*27 for x in range(27)]
-for a in range(27):
- for b in range(27):
- c = ((a * b)-1) % 26 + 1
- modular_division_table_one_based[b][c] = a
-
-
def sanitise(text):
"""Remove all non-alphabetic characters and convert the text to lowercase
"""Returns all n-grams of a text
>>> ngrams(sanitise('the quick brown fox'), 2)
- [('t', 'h'), ('h', 'e'), ('e', 'q'), ('q', 'u'), ('u', 'i'), ('i', 'c'), ('c', 'k'), ('k', 'b'), ('b', 'r'), ('r', 'o'), ('o', 'w'), ('w', 'n'), ('n', 'f'), ('f', 'o'), ('o', 'x')]
+ ['th', 'he', 'eq', 'qu', 'ui', 'ic', 'ck', 'kb', 'br', 'ro', 'ow', 'wn', 'nf', 'fo', 'ox']
>>> ngrams(sanitise('the quick brown fox'), 4)
- [('t', 'h', 'e', 'q'), ('h', 'e', 'q', 'u'), ('e', 'q', 'u', 'i'), ('q', 'u', 'i', 'c'), ('u', 'i', 'c', 'k'), ('i', 'c', 'k', 'b'), ('c', 'k', 'b', 'r'), ('k', 'b', 'r', 'o'), ('b', 'r', 'o', 'w'), ('r', 'o', 'w', 'n'), ('o', 'w', 'n', 'f'), ('w', 'n', 'f', 'o'), ('n', 'f', 'o', 'x')]
+ ['theq', 'hequ', 'equi', 'quic', 'uick', 'ickb', 'ckbr', 'kbro', 'brow', 'rown', 'ownf', 'wnfo', 'nfox']
+ """
+ return [text[i:i+n] for i in range(len(text)-n+1)]
+
+def every_nth(text, n):
+ """Returns n strings, each of which consists of every nth character,
+ starting with the 0th, 1st, 2nd, ... (n-1)th character
+
+ >>> every_nth(string.ascii_lowercase, 5)
+ ['afkpuz', 'bglqv', 'chmrw', 'dinsx', 'ejoty']
+ >>> every_nth(string.ascii_lowercase, 1)
+ ['abcdefghijklmnopqrstuvwxyz']
+ >>> every_nth(string.ascii_lowercase, 26)
+ ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
"""
- return [tuple(text[i:i+n]) for i in range(len(text)-n+1)]
+ split_text = [text[i:i+n] for i in range(0, len(text), n)]
+ return [''.join(l) for l in zip_longest(*split_text, fillvalue='')]
-def letter_frequencies(text):
+def combine_every_nth(split_text):
+ """Reforms a text split into every_nth strings
+
+ >>> combine_every_nth(every_nth(string.ascii_lowercase, 5))
+ 'abcdefghijklmnopqrstuvwxyz'
+ >>> combine_every_nth(every_nth(string.ascii_lowercase, 1))
+ 'abcdefghijklmnopqrstuvwxyz'
+ >>> combine_every_nth(every_nth(string.ascii_lowercase, 26))
+ 'abcdefghijklmnopqrstuvwxyz'
+ """
+ return ''.join([''.join(l) for l in zip_longest(*split_text, fillvalue='')])
+
+
+def frequencies(text):
"""Count the number of occurrences of each character in text
- >>> sorted(letter_frequencies('abcdefabc').items())
+ >>> sorted(frequencies('abcdefabc').items())
[('a', 2), ('b', 2), ('c', 2), ('d', 1), ('e', 1), ('f', 1)]
- >>> sorted(letter_frequencies('the quick brown fox jumped over the lazy dog').items())
+ >>> sorted(frequencies('the quick brown fox jumped over the lazy dog').items())
[(' ', 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)]
- >>> sorted(letter_frequencies('The Quick BROWN fox jumped! over... the (9lazy) DOG').items())
+ >>> sorted(frequencies('The Quick BROWN fox jumped! over... the (9lazy) DOG').items())
[(' ', 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)]
- >>> sorted(letter_frequencies(sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')).items())
+ >>> sorted(frequencies(sanitise('The Quick BROWN fox jumped! over... the (9lazy) DOG')).items())
[('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)]
"""
counts = collections.defaultdict(int)
for c in text:
counts[c] += 1
return counts
+letter_frequencies = frequencies
def deduplicate(text):
return list(collections.OrderedDict.fromkeys(text))
alphabet_start = ord('a')
letter_number = ord(letter) - alphabet_start
if one_based: letter_number += 1
- raw_cipher_number = (letter_number * multiplier + adder)
- cipher_number = 0
- if one_based:
- cipher_number = (raw_cipher_number - 1) % 26
- else:
- cipher_number = raw_cipher_number % 26
- return chr(cipher_number + alphabet_start)
+ cipher_number = (letter_number * multiplier + adder) % 26
+ if one_based: cipher_number -= 1
+ return chr(cipher_number % 26 + alphabet_start)
else:
return letter
alphabet_start = ord('a')
cipher_number = ord(letter) - alphabet_start
if one_based: cipher_number += 1
- plaintext_number = 0
- if one_based:
- plaintext_number = (modular_division_table_one_based[multiplier][(cipher_number - adder + 26) % 26] - 1) % 26
- else:
- #plaintext_number = (modular_division_table[multiplier][cipher_number] - adder) % 26
- plaintext_number = modular_division_table[multiplier][(cipher_number - adder + 26) % 26]
- return chr(plaintext_number + alphabet_start)
+ plaintext_number = modular_division_table[multiplier][(cipher_number - adder) % 26]
+ if one_based: plaintext_number -= 1
+ return chr(plaintext_number % 26 + alphabet_start)
else:
return letter
>>> affine_encipher('hours passed during which jerico tried every trick he could think of', 15, 22, True)
'lmyfu bkuusd dyfaxw claol psfaom jfasd snsfg jfaoe ls omytd jlaxe mh'
"""
-
enciphered = [affine_encipher_letter(l, multiplier, adder, one_based) for l in message]
return ''.join(enciphered)
return ''.join(enciphered)
-def keyword_cipher_alphabet_of(keyword, wrap_alphabet=False):
- """Find the cipher alphabet given a keyword
-
- >>> keyword_cipher_alphabet_of('harry')
- 'harybcdefgijklmnopqstuvwxz'
- >>> keyword_cipher_alphabet_of('harry', True)
- 'haryzbcdefgijklmnopqstuvwx'
- >>> keyword_cipher_alphabet_of('harry', False)
- 'harybcdefgijklmnopqstuvwxz'
+def keyword_cipher_alphabet_of(keyword, wrap_alphabet=0):
+ """Find the cipher alphabet given a keyword.
+ wrap_alphabet controls how the rest of the alphabet is added
+ after the keyword.
+ 0 : from 'a'
+ 1 : from the last letter in the sanitised keyword
+ 2 : from the largest letter in the sanitised keyword
+
+ >>> keyword_cipher_alphabet_of('bayes')
+ 'bayescdfghijklmnopqrtuvwxz'
+ >>> keyword_cipher_alphabet_of('bayes', 0)
+ 'bayescdfghijklmnopqrtuvwxz'
+ >>> keyword_cipher_alphabet_of('bayes', 1)
+ 'bayestuvwxzcdfghijklmnopqr'
+ >>> keyword_cipher_alphabet_of('bayes', 2)
+ 'bayeszcdfghijklmnopqrtuvwx'
"""
- cipher_alphabet = ''
- if wrap_alphabet:
- last_keyword_letter = deduplicate(sanitise(keyword))[-1]
- last_keyword_position = string.ascii_lowercase.find(last_keyword_letter) + 1
- cipher_alphabet = ''.join(deduplicate(sanitise(keyword) + string.ascii_lowercase[last_keyword_position:] + string.ascii_lowercase))
- else:
+ if wrap_alphabet == 0:
cipher_alphabet = ''.join(deduplicate(sanitise(keyword) + string.ascii_lowercase))
+ else:
+ if wrap_alphabet == 1:
+ last_keyword_letter = deduplicate(sanitise(keyword))[-1]
+ else:
+ last_keyword_letter = sorted(sanitise(keyword))[-1]
+ last_keyword_position = string.ascii_lowercase.find(last_keyword_letter) + 1
+ cipher_alphabet = ''.join(deduplicate(sanitise(keyword) +
+ string.ascii_lowercase[last_keyword_position:] +
+ string.ascii_lowercase))
return cipher_alphabet
-def keyword_encipher(message, keyword, wrap_alphabet=False):
- """Enciphers a message with a keyword substitution cipher
-
- >>> keyword_encipher('test message', 'harry')
- 'sbqs kbqqhdb'
- >>> keyword_encipher('test message', 'harry', True)
- 'qzpq jzpphcz'
- >>> keyword_encipher('test message', 'harry', False)
- 'sbqs kbqqhdb'
+def keyword_encipher(message, keyword, wrap_alphabet=0):
+ """Enciphers a message with a keyword substitution cipher.
+ wrap_alphabet controls how the rest of the alphabet is added
+ after the keyword.
+ 0 : from 'a'
+ 1 : from the last letter in the sanitised keyword
+ 2 : from the largest letter in the sanitised keyword
+
+ >>> keyword_encipher('test message', 'bayes')
+ 'rsqr ksqqbds'
+ >>> keyword_encipher('test message', 'bayes', 0)
+ 'rsqr ksqqbds'
+ >>> keyword_encipher('test message', 'bayes', 1)
+ 'lskl dskkbus'
+ >>> keyword_encipher('test message', 'bayes', 2)
+ 'qspq jsppbcs'
"""
cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
cipher_translation = ''.maketrans(string.ascii_lowercase, cipher_alphabet)
return message.lower().translate(cipher_translation)
-def keyword_decipher(message, keyword, wrap_alphabet=False):
- """Deciphers a message with a keyword substitution cipher
-
- >>> keyword_decipher('sbqs kbqqhdb', 'harry')
+def keyword_decipher(message, keyword, wrap_alphabet=0):
+ """Deciphers a message with a keyword substitution cipher.
+ wrap_alphabet controls how the rest of the alphabet is added
+ after the keyword.
+ 0 : from 'a'
+ 1 : from the last letter in the sanitised keyword
+ 2 : from the largest letter in the sanitised keyword
+
+ >>> keyword_decipher('rsqr ksqqbds', 'bayes')
+ 'test message'
+ >>> keyword_decipher('rsqr ksqqbds', 'bayes', 0)
'test message'
- >>> keyword_decipher('qzpq jzpphcz', 'harry', True)
+ >>> keyword_decipher('lskl dskkbus', 'bayes', 1)
'test message'
- >>> keyword_decipher('sbqs kbqqhdb', 'harry', False)
+ >>> keyword_decipher('qspq jsppbcs', 'bayes', 2)
'test message'
"""
cipher_alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet)
cipher_translation = ''.maketrans(cipher_alphabet, string.ascii_lowercase)
return message.lower().translate(cipher_translation)
+def scytale_encipher(message, rows):
+ """Enciphers using the scytale transposition cipher.
+ Message is padded with spaces to allow all rows to be the same length.
+
+ >>> scytale_encipher('thequickbrownfox', 3)
+ 'tcnhkfeboqrxuo iw '
+ >>> scytale_encipher('thequickbrownfox', 4)
+ 'tubnhirfecooqkwx'
+ >>> scytale_encipher('thequickbrownfox', 5)
+ 'tubn hirf ecoo qkwx '
+ >>> scytale_encipher('thequickbrownfox', 6)
+ 'tqcrnxhukof eibwo '
+ >>> scytale_encipher('thequickbrownfox', 7)
+ 'tqcrnx hukof eibwo '
+ """
+ if len(message) % rows != 0:
+ message += ' '*(rows - len(message) % rows)
+ row_length = round(len(message) / rows)
+ slices = [message[i:i+row_length] for i in range(0, len(message), row_length)]
+ return ''.join([''.join(r) for r in zip_longest(*slices, fillvalue='')])
+
+def scytale_decipher(message, rows):
+ """Deciphers using the scytale transposition cipher.
+ Assumes the message is padded so that all rows are the same length.
+
+ >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
+ 'thequickbrownfox '
+ >>> scytale_decipher('tubnhirfecooqkwx', 4)
+ 'thequickbrownfox'
+ >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
+ 'thequickbrownfox '
+ >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
+ 'thequickbrownfox '
+ >>> scytale_decipher('tqcrnx hukof eibwo ', 7)
+ 'thequickbrownfox '
+ """
+ cols = round(len(message) / rows)
+ columns = [message[i:i+rows] for i in range(0, cols * rows, rows)]
+ return ''.join([''.join(c) for c in zip_longest(*columns, fillvalue='')])
+
-def caesar_break(message, metric=norms.euclidean_distance, target_frequencies=normalised_english_counts, message_frequency_scaling=norms.normalise):
+def caesar_break(message, metric=norms.euclidean_distance, target_counts=normalised_english_counts, message_frequency_scaling=norms.normalise):
"""Breaks a Caesar cipher using frequency analysis
>>> caesar_break('ibxcsyorsaqcheyklxivoexlevmrimwxsfiqevvmihrsasrxliwyrhecjsppsamrkwleppfmergefifvmhixscsymjcsyqeoixlm') # doctest: +ELLIPSIS
best_fit = float("inf")
for shift in range(26):
plaintext = caesar_decipher(sanitised_message, shift)
- frequencies = message_frequency_scaling(letter_frequencies(plaintext))
- fit = metric(target_frequencies, frequencies)
+ counts = message_frequency_scaling(letter_frequencies(plaintext))
+ fit = metric(target_counts, counts)
logger.debug('Caesar break attempt using key {0} gives fit of {1} and decrypt starting: {2}'.format(shift, fit, plaintext[:50]))
if fit < best_fit:
best_fit = fit
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]))
return best_shift, best_fit
-def affine_break(message, metric=norms.euclidean_distance, target_frequencies=normalised_english_counts, message_frequency_scaling=norms.normalise):
+def affine_break(message, metric=norms.euclidean_distance, target_counts=normalised_english_counts, message_frequency_scaling=norms.normalise):
"""Breaks an affine cipher using frequency analysis
>>> 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.') # doctest: +ELLIPSIS
for multiplier in range(1, 26, 2):
for adder in range(26):
plaintext = affine_decipher(sanitised_message, multiplier, adder, one_based)
- frequencies = message_frequency_scaling(letter_frequencies(plaintext))
- fit = metric(target_frequencies, frequencies)
+ counts = message_frequency_scaling(letter_frequencies(plaintext))
+ fit = metric(target_counts, counts)
logger.debug('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]))
if fit < best_fit:
best_fit = fit
return (best_multiplier, best_adder, best_one_based), best_fit
-def keyword_break(message, wordlist=keywords, metric=norms.euclidean_distance, target_frequencies=normalised_english_counts, message_frequency_scaling=norms.normalise):
+def keyword_break(message, wordlist=keywords, metric=norms.euclidean_distance, target_counts=normalised_english_counts, message_frequency_scaling=norms.normalise):
"""Breaks a keyword substitution cipher using a dictionary and frequency analysis
- >>> keyword_break(keyword_encipher('this is a test message for the keyword decipherment', 'elephant', True))
- (('elephant', True), 0.41643991598441...) # doctest: +ELLIPSIS
+ >>> keyword_break(keyword_encipher('this is a test message for the keyword decipherment', 'elephant', 1), wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
+ (('elephant', 1), 0.41643991598441...)
"""
best_keyword = ''
best_wrap_alphabet = True
best_fit = float("inf")
- for wrap_alphabet in [True, False]:
+ for wrap_alphabet in range(3):
for keyword in wordlist:
plaintext = keyword_decipher(message, keyword, wrap_alphabet)
- frequencies = message_frequency_scaling(letter_frequencies(plaintext))
- fit = metric(target_frequencies, frequencies)
- logger.debug('Keyword break attempt using key {0} ({1}) gives fit of {2} and decrypt starting: {3}'.format(keyword, wrap_alphabet, fit, sanitise(plaintext)[:50]))
+ counts = message_frequency_scaling(letter_frequencies(plaintext))
+ fit = metric(target_counts, counts)
+ logger.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of {2} and decrypt starting: {3}'.format(keyword, wrap_alphabet, fit, sanitise(plaintext)[:50]))
if fit < best_fit:
best_fit = fit
best_keyword = keyword
best_wrap_alphabet = wrap_alphabet
- logger.info('Keyword break best fit with key {0} ({1}) gives fit of {2} and decrypt starting: {3}'.format(best_keyword, best_wrap_alphabet, best_fit, sanitise(keyword_decipher(message, best_keyword))[:50]))
+ logger.info('Keyword break best fit with key {0} (wrap={1}) gives fit of {2} and decrypt starting: {3}'.format(best_keyword, best_wrap_alphabet, best_fit, sanitise(keyword_decipher(message, best_keyword))[:50]))
return (best_keyword, best_wrap_alphabet), best_fit
+def keyword_break_mp(message, wordlist=keywords, metric=norms.euclidean_distance, target_counts=normalised_english_counts, message_frequency_scaling=norms.normalise):
+ """Breaks a keyword substitution cipher using a dictionary and frequency analysis
+
+ >>> keyword_break_mp(keyword_encipher('this is a test message for the keyword decipherment', 'elephant', 1), wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS
+ (('elephant', 1), 0.41643991598441...)
+ """
+ with Pool() as pool:
+ keys = [(word, wrap) for word in wordlist for wrap in range(3)]
+ # breaks = map(lambda kw: keyword_break_one(message, kw[0], kw[1], metric, target_counts, message_frequency_scaling), keys)
+ breaks = pool.starmap(lambda k, w: keyword_break_one(message, k, w, metric, target_counts, message_frequency_scaling), keys, 1000)
+ return min(breaks, key=lambda k: k[1])
+
+def keyword_break_one(message, keyword, wrap_alphabet, metric, target_counts, message_frequency_scaling):
+ plaintext = keyword_decipher(message, keyword, wrap_alphabet)
+ counts = message_frequency_scaling(letter_frequencies(plaintext))
+ fit = metric(target_counts, counts)
+ logger.debug('Keyword break attempt using key {0} (wrap={1}) gives fit of {2} and decrypt starting: {3}'.format(keyword, wrap_alphabet, fit, sanitise(plaintext)[:50]))
+ return (keyword, wrap_alphabet), fit
+
+
+def scytale_break(message, metric=norms.euclidean_distance, target_counts=normalised_english_bigram_counts, message_frequency_scaling=norms.normalise):
+ """Breaks a Scytale cipher
+
+ >>> scytale_break('tfeulchtrtteehwahsdehneoifeayfsondmwpltmaoalhikotoeredcweatehiplwxsnhooacgorrcrcraotohsgullasenylrendaianeplscdriiotoaek') # doctest: +ELLIPSIS
+ (6, 0.83453041115025...)
+ """
+ best_key = 0
+ best_fit = float("inf")
+ for key in range(1, 20):
+ if len(message) % key == 0:
+ plaintext = scytale_decipher(message, key)
+ counts = message_frequency_scaling(frequencies(ngrams(sanitise(plaintext), 2)))
+ fit = metric(target_counts, counts)
+ logger.debug('Scytale break attempt using key {0} gives fit of {1} and decrypt starting: {2}'.format(key, fit, sanitise(plaintext)[:50]))
+ if fit < best_fit:
+ best_fit = fit
+ best_key = key
+ logger.info('Scytale break best fit with key {0} gives fit of {1} and decrypt starting: {2}'.format(best_key, best_fit, sanitise(scytale_decipher(message, best_key))[:50]))
+ return best_key, best_fit
+
if __name__ == "__main__":
import doctest
projects / cipher-tools.git / blobdiff