column_transposition.py

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