szyfrow/column_transposition.py

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