cipher/column_transposition.py

   1 import math
   2 import multiprocessing
   3 from itertools import chain
   4 from support.utilities import *
   5 from support.language_models import *
   6
   7 from logger import logger
   8
   9 def transpositions_of(keyword):
  10     """Finds the transpostions given by a keyword. For instance, the keyword
  11     'clever' rearranges to 'celrv', so the first column (0) stays first, the
  12     second column (1) moves to third, the third column (2) moves to second,
  13     and so on.
  14
  15     If passed a tuple, assume it's already a transposition and just return it.
  16
  17     >>> transpositions_of('clever')
  18     (0, 2, 1, 4, 3)
  19     >>> transpositions_of('fred')
  20     (3, 2, 0, 1)
  21     >>> transpositions_of((3, 2, 0, 1))
  22     (3, 2, 0, 1)
  23     """
  24     if isinstance(keyword, tuple):
  25         return keyword
  26     else:
  27         key = deduplicate(keyword)
  28         transpositions = tuple(key.index(l) for l in sorted(key))
  29         return transpositions
  30
  31
  32 transpositions = collections.defaultdict(list)
  33 for word in keywords:
  34     transpositions[transpositions_of(word)] += [word]
  35
  36
  37 def pad(message_len, group_len, fillvalue):
  38     padding_length = group_len - message_len % group_len
  39     if padding_length == group_len: padding_length = 0
  40     padding = ''
  41     for i in range(padding_length):
  42         if callable(fillvalue):
  43             padding += fillvalue()
  44         else:
  45             padding += fillvalue
  46     return padding
  47
  48 def column_transposition_encipher(message, keyword, fillvalue=' ',
  49       fillcolumnwise=False,
  50       emptycolumnwise=False):
  51     """Enciphers using the column transposition cipher.
  52     Message is padded to allow all rows to be the same length.
  53
  54     >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True)
  55     'hlohr eltee '
  56     >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True, emptycolumnwise=True)
  57     'hellothere  '
  58     >>> column_transposition_encipher('hellothere', 'abcdef')
  59     'hellothere  '
  60     >>> column_transposition_encipher('hellothere', 'abcde')
  61     'hellothere'
  62     >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
  63     'hellothere'
  64     >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
  65     'hlohreltee'
  66     >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
  67     'htehlelroe'
  68     >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
  69     'hellothere'
  70     >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=True)
  71     'heotllrehe'
  72     >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=False)
  73     'holrhetlee'
  74     >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=True)
  75     'htleehoelr'
  76     >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=False)
  77     'hleolteher'
  78     >>> column_transposition_encipher('hellothere', 'cleverly')
  79     'hleolthre e '
  80     >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
  81     'hleolthre!e!'
  82     >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue=lambda: '*')
  83     'hleolthre*e*'
  84     """
  85     transpositions = transpositions_of(keyword)
  86     message += pad(len(message), len(transpositions), fillvalue)
  87     if fillcolumnwise:
  88         rows = every_nth(message, len(message) // len(transpositions))
  89     else:
  90         rows = chunks(message, len(transpositions))
  91     transposed = [transpose(r, transpositions) for r in rows]
  92     if emptycolumnwise:
  93         return combine_every_nth(transposed)
  94     else:
  95         return cat(chain(*transposed))
  96
  97 def column_transposition_decipher(message, keyword, fillvalue=' ',
  98       fillcolumnwise=False,
  99       emptycolumnwise=False):
 100     """Deciphers using the column transposition cipher.
 101     Message is padded to allow all rows to be the same length.
 102
 103     >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
 104     'hellothere'
 105     >>> column_transposition_decipher('hlohreltee', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
 106     'hellothere'
 107     >>> column_transposition_decipher('htehlelroe', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
 108     'hellothere'
 109     >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
 110     'hellothere'
 111     >>> column_transposition_decipher('heotllrehe', 'clever', fillcolumnwise=True, emptycolumnwise=True)
 112     'hellothere'
 113     >>> column_transposition_decipher('holrhetlee', 'clever', fillcolumnwise=True, emptycolumnwise=False)
 114     'hellothere'
 115     >>> column_transposition_decipher('htleehoelr', 'clever', fillcolumnwise=False, emptycolumnwise=True)
 116     'hellothere'
 117     >>> column_transposition_decipher('hleolteher', 'clever', fillcolumnwise=False, emptycolumnwise=False)
 118     'hellothere'
 119     """
 120     transpositions = transpositions_of(keyword)
 121     message += pad(len(message), len(transpositions), fillvalue)
 122     if emptycolumnwise:
 123         rows = every_nth(message, len(message) // len(transpositions))
 124     else:
 125         rows = chunks(message, len(transpositions))
 126     untransposed = [untranspose(r, transpositions) for r in rows]
 127     if fillcolumnwise:
 128         return combine_every_nth(untransposed)
 129     else:
 130         return cat(chain(*untransposed))
 131
 132 def scytale_encipher(message, rows, fillvalue=' '):
 133     """Enciphers using the scytale transposition cipher.
 134     Message is padded with spaces to allow all rows to be the same length.
 135
 136     >>> scytale_encipher('thequickbrownfox', 3)
 137     'tcnhkfeboqrxuo iw '
 138     >>> scytale_encipher('thequickbrownfox', 4)
 139     'tubnhirfecooqkwx'
 140     >>> scytale_encipher('thequickbrownfox', 5)
 141     'tubn hirf ecoo qkwx '
 142     >>> scytale_encipher('thequickbrownfox', 6)
 143     'tqcrnxhukof eibwo '
 144     >>> scytale_encipher('thequickbrownfox', 7)
 145     'tqcrnx hukof  eibwo  '
 146     """
 147     # transpositions = [i for i in range(math.ceil(len(message) / rows))]
 148     # return column_transposition_encipher(message, transpositions,
 149     #     fillvalue=fillvalue, fillcolumnwise=False, emptycolumnwise=True)
 150     transpositions = [i for i in range(rows)]
 151     return column_transposition_encipher(message, transpositions,
 152         fillvalue=fillvalue, fillcolumnwise=True, emptycolumnwise=False)
 153
 154 def scytale_decipher(message, rows):
 155     """Deciphers using the scytale transposition cipher.
 156     Assumes the message is padded so that all rows are the same length.
 157
 158     >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
 159     'thequickbrownfox  '
 160     >>> scytale_decipher('tubnhirfecooqkwx', 4)
 161     'thequickbrownfox'
 162     >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
 163     'thequickbrownfox    '
 164     >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
 165     'thequickbrownfox  '
 166     >>> scytale_decipher('tqcrnx hukof  eibwo  ', 7)
 167     'thequickbrownfox     '
 168     """
 169     # transpositions = [i for i in range(math.ceil(len(message) / rows))]
 170     # return column_transposition_decipher(message, transpositions,
 171     #     fillcolumnwise=False, emptycolumnwise=True)
 172     transpositions = [i for i in range(rows)]
 173     return column_transposition_decipher(message, transpositions,
 174         fillcolumnwise=True, emptycolumnwise=False)
 175
 176
 177 def column_transposition_break_mp(message, translist=transpositions,
 178                                   fitness=Pbigrams, chunksize=500):
 179     """Breaks a column transposition cipher using a dictionary and
 180     n-gram frequency analysis
 181
 182     >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
 183             "It is a truth universally acknowledged, that a single man in \
 184              possession of a good fortune, must be in want of a wife. However \
 185              little known the feelings or views of such a man may be on his \
 186              first entering a neighbourhood, this truth is so well fixed in \
 187              the minds of the surrounding families, that he is considered the \
 188              rightful property of some one or other of their daughters."), \
 189         'encipher'), \
 190         translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
 191                    (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
 192                    (6, 1, 0, 4, 5, 3, 2): ['keyword']}) # doctest: +ELLIPSIS
 193     (((2, 0, 5, 3, 1, 4, 6), False, False), -709.4646722...)
 194     >>> column_transposition_break_mp(column_transposition_encipher(sanitise( \
 195             "It is a truth universally acknowledged, that a single man in \
 196              possession of a good fortune, must be in want of a wife. However \
 197              little known the feelings or views of such a man may be on his \
 198              first entering a neighbourhood, this truth is so well fixed in \
 199              the minds of the surrounding families, that he is considered the \
 200              rightful property of some one or other of their daughters."), \
 201         'encipher'), \
 202         translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
 203                    (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
 204                    (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
 205         fitness=Ptrigrams) # doctest: +ELLIPSIS
 206     (((2, 0, 5, 3, 1, 4, 6), False, False), -997.0129085...)
 207     """
 208     with multiprocessing.Pool() as pool:
 209         helper_args = [(message, trans, fillcolumnwise, emptycolumnwise,
 210                         fitness)
 211                        for trans in translist
 212                        for fillcolumnwise in [True, False]
 213                        for emptycolumnwise in [True, False]]
 214         # Gotcha: the helper function here needs to be defined at the top level
 215         #   (limitation of Pool.starmap)
 216         breaks = pool.starmap(column_transposition_break_worker,
 217                               helper_args, chunksize)
 218         return max(breaks, key=lambda k: k[1])
 219 column_transposition_break = column_transposition_break_mp
 220
 221 def column_transposition_break_worker(message, transposition,
 222         fillcolumnwise, emptycolumnwise, fitness):
 223     plaintext = column_transposition_decipher(message, transposition,
 224         fillcolumnwise=fillcolumnwise, emptycolumnwise=emptycolumnwise)
 225     fit = fitness(sanitise(plaintext))
 226     logger.debug('Column transposition break attempt using key {0} '
 227                          'gives fit of {1} and decrypt starting: {2}'.format(
 228                              transposition, fit,
 229                              sanitise(plaintext)[:50]))
 230     return (transposition, fillcolumnwise, emptycolumnwise), fit
 231
 232
 233 def scytale_break_mp(message, max_key_length=20,
 234                      fitness=Pbigrams, chunksize=500):
 235     """Breaks a scytale cipher using a range of lengths and
 236     n-gram frequency analysis
 237
 238     >>> scytale_break_mp(scytale_encipher(sanitise( \
 239             "It is a truth universally acknowledged, that a single man in \
 240              possession of a good fortune, must be in want of a wife. However \
 241              little known the feelings or views of such a man may be on his \
 242              first entering a neighbourhood, this truth is so well fixed in \
 243              the minds of the surrounding families, that he is considered the \
 244              rightful property of some one or other of their daughters."), \
 245         5)) # doctest: +ELLIPSIS
 246     (5, -709.4646722...)
 247     >>> scytale_break_mp(scytale_encipher(sanitise( \
 248             "It is a truth universally acknowledged, that a single man in \
 249              possession of a good fortune, must be in want of a wife. However \
 250              little known the feelings or views of such a man may be on his \
 251              first entering a neighbourhood, this truth is so well fixed in \
 252              the minds of the surrounding families, that he is considered the \
 253              rightful property of some one or other of their daughters."), \
 254         5), \
 255         fitness=Ptrigrams) # doctest: +ELLIPSIS
 256     (5, -997.0129085...)
 257     """
 258     with multiprocessing.Pool() as pool:
 259         helper_args = [(message, trans, False, True, fitness)
 260             for trans in
 261                 [[col for col in range(math.ceil(len(message)/rows))]
 262                     for rows in range(1,max_key_length+1)]]
 263         # Gotcha: the helper function here needs to be defined at the top level
 264         #   (limitation of Pool.starmap)
 265         breaks = pool.starmap(column_transposition_break_worker,
 266                               helper_args, chunksize)
 267         best = max(breaks, key=lambda k: k[1])
 268         return math.trunc(len(message) / len(best[0][0])), best[1]
 269 scytale_break = scytale_break_mp
 270
 271 if __name__ == "__main__":
 272     import doctest