szyfrow/column_transposition.py

   1 """Enciphering and deciphering using the [Column transposition cipher](https://en.wikipedia.org/wiki/Bifid_cipher).
   2 Also attempts to break messages that use a column transpositon cipher.
   3
   4 A grid is layed out, with one column for each distinct letter in the keyword.
   5 The grid is filled by the plaintext, one letter per cell, either in rows or
   6 columns. The columns are rearranged so the keyword's letters are in alphabetical
   7 order, then the ciphertext is read from the rearranged grid, either in rows
   8 or columns.
   9
  10 The Scytale cipher is a column cipher with an identity transposition, where the
  11 message is written in rows and read in columns.
  12
  13 Messages that do not fill the grid are padded with fillvalue. Note that
  14 `szyfrow.support.utilities.pad` allows a callable, so that the message can be
  15 padded by random letters, for instance by calling
  16 `szyfrow.support.language_models.random_english_letter`.
  17 """
  18
  19 import math
  20 import multiprocessing
  21 from itertools import chain
  22 from szyfrow.support.utilities import *
  23 from szyfrow.support.language_models import *
  24
  25 def column_transposition_encipher(message, keyword, fillvalue=' ',
  26       fillcolumnwise=False,
  27       emptycolumnwise=False):
  28     """Enciphers using the column transposition cipher.
  29     Message is padded to allow all rows to be the same length.
  30
  31     >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True)
  32     'hlohr eltee '
  33     >>> column_transposition_encipher('hellothere', 'abcdef', fillcolumnwise=True, emptycolumnwise=True)
  34     'hellothere  '
  35     >>> column_transposition_encipher('hellothere', 'abcdef')
  36     'hellothere  '
  37     >>> column_transposition_encipher('hellothere', 'abcde')
  38     'hellothere'
  39     >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
  40     'hellothere'
  41     >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
  42     'hlohreltee'
  43     >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
  44     'htehlelroe'
  45     >>> column_transposition_encipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
  46     'hellothere'
  47     >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=True)
  48     'heotllrehe'
  49     >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=True, emptycolumnwise=False)
  50     'holrhetlee'
  51     >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=True)
  52     'htleehoelr'
  53     >>> column_transposition_encipher('hellothere', 'clever', fillcolumnwise=False, emptycolumnwise=False)
  54     'hleolteher'
  55     >>> column_transposition_encipher('hellothere', 'cleverly')
  56     'hleolthre e '
  57     >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue='!')
  58     'hleolthre!e!'
  59     >>> column_transposition_encipher('hellothere', 'cleverly', fillvalue=lambda: '*')
  60     'hleolthre*e*'
  61     """
  62     transpositions = transpositions_of(keyword)
  63     message += pad(len(message), len(transpositions), fillvalue)
  64     if fillcolumnwise:
  65         rows = every_nth(message, len(message) // len(transpositions))
  66     else:
  67         rows = chunks(message, len(transpositions))
  68     transposed = [transpose(r, transpositions) for r in rows]
  69     if emptycolumnwise:
  70         return combine_every_nth(transposed)
  71     else:
  72         return cat(chain(*transposed))
  73
  74 def column_transposition_decipher(message, keyword, fillvalue=' ',
  75       fillcolumnwise=False,
  76       emptycolumnwise=False):
  77     """Deciphers using the column transposition cipher.
  78     Message is padded to allow all rows to be the same length.
  79
  80     Note that `fillcolumnwise` and `emptycolumnwise` refer to how the message
  81     is enciphered. To decipher a message, the operations are performed as an
  82     inverse-empty, then inverse-transposition, then inverse-fill.
  83
  84     >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=True, emptycolumnwise=True)
  85     'hellothere'
  86     >>> column_transposition_decipher('hlohreltee', 'abcde', fillcolumnwise=True, emptycolumnwise=False)
  87     'hellothere'
  88     >>> column_transposition_decipher('htehlelroe', 'abcde', fillcolumnwise=False, emptycolumnwise=True)
  89     'hellothere'
  90     >>> column_transposition_decipher('hellothere', 'abcde', fillcolumnwise=False, emptycolumnwise=False)
  91     'hellothere'
  92     >>> column_transposition_decipher('heotllrehe', 'clever', fillcolumnwise=True, emptycolumnwise=True)
  93     'hellothere'
  94     >>> column_transposition_decipher('holrhetlee', 'clever', fillcolumnwise=True, emptycolumnwise=False)
  95     'hellothere'
  96     >>> column_transposition_decipher('htleehoelr', 'clever', fillcolumnwise=False, emptycolumnwise=True)
  97     'hellothere'
  98     >>> column_transposition_decipher('hleolteher', 'clever', fillcolumnwise=False, emptycolumnwise=False)
  99     'hellothere'
 100     """
 101     transpositions = transpositions_of(keyword)
 102     message += pad(len(message), len(transpositions), fillvalue)
 103     if emptycolumnwise:
 104         rows = every_nth(message, len(message) // len(transpositions))
 105     else:
 106         rows = chunks(message, len(transpositions))
 107     untransposed = [untranspose(r, transpositions) for r in rows]
 108     if fillcolumnwise:
 109         return combine_every_nth(untransposed)
 110     else:
 111         return cat(chain(*untransposed))
 112
 113 def scytale_encipher(message, rows, fillvalue=' '):
 114     """Enciphers using the scytale transposition cipher. `rows` is the
 115     circumference of the rod. The message is fitted inot columns so that
 116     all rows are used.
 117
 118     Message is padded with spaces to allow all rows to be the same length.
 119
 120     For ease of implementation, the cipher is performed on the transpose
 121     of the grid
 122
 123     >>> scytale_encipher('thequickbrownfox', 3)
 124     'tcnhkfeboqrxuo iw '
 125     >>> scytale_encipher('thequickbrownfox', 4)
 126     'tubnhirfecooqkwx'
 127     >>> scytale_encipher('thequickbrownfox', 5)
 128     'tubn hirf ecoo qkwx '
 129     >>> scytale_encipher('thequickbrownfox', 6)
 130     'tqcrnxhukof eibwo '
 131     >>> scytale_encipher('thequickbrownfox', 7)
 132     'tqcrnx hukof  eibwo  '
 133     """
 134     # transpositions = [i for i in range(math.ceil(len(message) / rows))]
 135     # return column_transposition_encipher(message, transpositions,
 136     #     fillvalue=fillvalue, fillcolumnwise=False, emptycolumnwise=True)
 137     transpositions = (i for i in range(rows))
 138     return column_transposition_encipher(message, transpositions,
 139         fillvalue=fillvalue, fillcolumnwise=True, emptycolumnwise=False)
 140
 141 def scytale_decipher(message, rows):
 142     """Deciphers using the scytale transposition cipher.
 143     Assumes the message is padded so that all rows are the same length.
 144
 145     >>> scytale_decipher('tcnhkfeboqrxuo iw ', 3)
 146     'thequickbrownfox  '
 147     >>> scytale_decipher('tubnhirfecooqkwx', 4)
 148     'thequickbrownfox'
 149     >>> scytale_decipher('tubn hirf ecoo qkwx ', 5)
 150     'thequickbrownfox    '
 151     >>> scytale_decipher('tqcrnxhukof eibwo ', 6)
 152     'thequickbrownfox  '
 153     >>> scytale_decipher('tqcrnx hukof  eibwo  ', 7)
 154     'thequickbrownfox     '
 155     """
 156     # transpositions = [i for i in range(math.ceil(len(message) / rows))]
 157     # return column_transposition_decipher(message, transpositions,
 158     #     fillcolumnwise=False, emptycolumnwise=True)
 159     transpositions = [i for i in range(rows)]
 160     return column_transposition_decipher(message, transpositions,
 161         fillcolumnwise=True, emptycolumnwise=False)
 162
 163
 164 def column_transposition_break(message, translist=None,
 165                                   fitness=Pbigrams, chunksize=500):
 166     """Breaks a column transposition cipher using a dictionary and
 167     n-gram frequency analysis
 168
 169     If `translist` is not specified, use
 170     [`szyfrow.support.langauge_models.transpositions`](support/language_models.html#szyfrow.support.language_models.transpositions).
 171
 172     >>> len(keywords)
 173     20
 174
 175     >>> column_transposition_break(column_transposition_encipher(sanitise( \
 176             "It is a truth universally acknowledged, that a single man in \
 177              possession of a good fortune, must be in want of a wife. However \
 178              little known the feelings or views of such a man may be on his \
 179              first entering a neighbourhood, this truth is so well fixed in \
 180              the minds of the surrounding families, that he is considered the \
 181              rightful property of some one or other of their daughters."), \
 182         'encipher'), \
 183         translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
 184                    (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
 185                    (6, 1, 0, 4, 5, 3, 2): ['keyword']}) # doctest: +ELLIPSIS
 186     (((2, 0, 5, 3, 1, 4, 6), False, False), -709.4646722...)
 187     >>> column_transposition_break(column_transposition_encipher(sanitise( \
 188             "It is a truth universally acknowledged, that a single man in \
 189              possession of a good fortune, must be in want of a wife. However \
 190              little known the feelings or views of such a man may be on his \
 191              first entering a neighbourhood, this truth is so well fixed in \
 192              the minds of the surrounding families, that he is considered the \
 193              rightful property of some one or other of their daughters."), \
 194         'encipher'), \
 195         translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
 196                    (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
 197                    (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
 198         fitness=Ptrigrams) # doctest: +ELLIPSIS
 199     (((2, 0, 5, 3, 1, 4, 6), False, False), -997.0129085...)
 200     """
 201     if translist is None:
 202         translist = transpositions
 203
 204     with multiprocessing.Pool() as pool:
 205         helper_args = [(message, trans, fillcolumnwise, emptycolumnwise,
 206                         fitness)
 207                        for trans in translist
 208                        for fillcolumnwise in [True, False]
 209                        for emptycolumnwise in [True, False]]
 210         # Gotcha: the helper function here needs to be defined at the top level
 211         #   (limitation of Pool.starmap)
 212         breaks = pool.starmap(column_transposition_break_worker,
 213                               helper_args, chunksize)
 214         return max(breaks, key=lambda k: k[1])
 215
 216 def column_transposition_break_worker(message, transposition,
 217         fillcolumnwise, emptycolumnwise, fitness):
 218     plaintext = column_transposition_decipher(message, transposition,
 219         fillcolumnwise=fillcolumnwise, emptycolumnwise=emptycolumnwise)
 220     fit = fitness(sanitise(plaintext))
 221     return (transposition, fillcolumnwise, emptycolumnwise), fit
 222
 223
 224 def scytale_break(message, max_key_length=20,
 225                      fitness=Pbigrams, chunksize=500):
 226     """Breaks a scytale cipher using a range of lengths and
 227     n-gram frequency analysis
 228
 229     >>> scytale_break(scytale_encipher(sanitise( \
 230             "It is a truth universally acknowledged, that a single man in \
 231              possession of a good fortune, must be in want of a wife. However \
 232              little known the feelings or views of such a man may be on his \
 233              first entering a neighbourhood, this truth is so well fixed in \
 234              the minds of the surrounding families, that he is considered the \
 235              rightful property of some one or other of their daughters."), \
 236         5)) # doctest: +ELLIPSIS
 237     (5, -709.4646722...)
 238     >>> scytale_break(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), \
 246         fitness=Ptrigrams) # doctest: +ELLIPSIS
 247     (5, -997.0129085...)
 248     """
 249     with multiprocessing.Pool() as pool:
 250         helper_args = [(message, trans, False, True, fitness)
 251             for trans in
 252                 [[col for col in range(math.ceil(len(message)/rows))]
 253                     for rows in range(1,max_key_length+1)]]
 254         # Gotcha: the helper function here needs to be defined at the top level
 255         #   (limitation of Pool.starmap)
 256         breaks = pool.starmap(column_transposition_break_worker,
 257                               helper_args, chunksize)
 258         best = max(breaks, key=lambda k: k[1])
 259         return math.trunc(len(message) / len(best[0][0])), best[1]
 260
 261 if __name__ == "__main__":
 262     import doctest