amsco.py

   1 from enum import Enum
   2 import multiprocessing
   3 import itertools
   4
   5 from szyfrow.support.utilities import *
   6 from szyfrow.support.language_models import *
   7 from szyfrow.column_transposition import transpositions, transpositions_of
   8
   9 # Where each piece of text ends up in the AMSCO transpositon cipher.
  10 # 'index' shows where the slice appears in the plaintext, with the slice
  11 # from 'start' to 'end'
  12 AmscoSlice = collections.namedtuple('AmscoSlice', ['index', 'start', 'end'])
  13
  14 class AmscoFillStyle(Enum):
  15     continuous = 1
  16     same_each_row = 2
  17     reverse_each_row = 3
  18
  19 def amsco_transposition_positions(message, keyword,
  20       fillpattern=(1, 2),
  21       fillstyle=AmscoFillStyle.continuous,
  22       fillcolumnwise=False,
  23       emptycolumnwise=True):
  24     """Creates the grid for the AMSCO transposition cipher. Each element in the
  25     grid shows the index of that slice and the start and end positions of the
  26     plaintext that go to make it up.
  27
  28     >>> amsco_transposition_positions(string.ascii_lowercase, 'freddy', \
  29         fillpattern=(1, 2)) # doctest:  +NORMALIZE_WHITESPACE
  30     [[AmscoSlice(index=3, start=4, end=6),
  31      AmscoSlice(index=2, start=3, end=4),
  32      AmscoSlice(index=0, start=0, end=1),
  33      AmscoSlice(index=1, start=1, end=3),
  34      AmscoSlice(index=4, start=6, end=7)],
  35     [AmscoSlice(index=8, start=12, end=13),
  36      AmscoSlice(index=7, start=10, end=12),
  37      AmscoSlice(index=5, start=7, end=9),
  38      AmscoSlice(index=6, start=9, end=10),
  39      AmscoSlice(index=9, start=13, end=15)],
  40     [AmscoSlice(index=13, start=19, end=21),
  41      AmscoSlice(index=12, start=18, end=19),
  42      AmscoSlice(index=10, start=15, end=16),
  43      AmscoSlice(index=11, start=16, end=18),
  44      AmscoSlice(index=14, start=21, end=22)],
  45     [AmscoSlice(index=18, start=27, end=28),
  46      AmscoSlice(index=17, start=25, end=27),
  47      AmscoSlice(index=15, start=22, end=24),
  48      AmscoSlice(index=16, start=24, end=25),
  49      AmscoSlice(index=19, start=28, end=30)]]
  50     """
  51     transpositions = transpositions_of(keyword)
  52     fill_iterator = itertools.cycle(fillpattern)
  53     indices = itertools.count()
  54     message_length = len(message)
  55
  56     current_position = 0
  57     grid = []
  58     current_fillpattern = fillpattern
  59     while current_position < message_length:
  60         row = []
  61         if fillstyle == AmscoFillStyle.same_each_row:
  62             fill_iterator = itertools.cycle(fillpattern)
  63         if fillstyle == AmscoFillStyle.reverse_each_row:
  64             fill_iterator = itertools.cycle(current_fillpattern)
  65         for _ in range(len(transpositions)):
  66             index = next(indices)
  67             gap = next(fill_iterator)
  68             row += [AmscoSlice(index, current_position, current_position + gap)]
  69             current_position += gap
  70         grid += [row]
  71         if fillstyle == AmscoFillStyle.reverse_each_row:
  72             current_fillpattern = list(reversed(current_fillpattern))
  73     return [transpose(r, transpositions) for r in grid]
  74
  75 def amsco_transposition_encipher(message, keyword,
  76     fillpattern=(1,2), fillstyle=AmscoFillStyle.reverse_each_row):
  77     """AMSCO transposition encipher.
  78
  79     >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(1, 2))
  80     'hoteelhler'
  81     >>> amsco_transposition_encipher('hellothere', 'abc', fillpattern=(2, 1))
  82     'hetelhelor'
  83     >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(1, 2))
  84     'hotelerelh'
  85     >>> amsco_transposition_encipher('hellothere', 'acb', fillpattern=(2, 1))
  86     'hetelorlhe'
  87     >>> amsco_transposition_encipher('hereissometexttoencipher', 'encode')
  88     'etecstthhomoerereenisxip'
  89     >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 2))
  90     'hetcsoeisterereipexthomn'
  91     >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 2), fillstyle=AmscoFillStyle.continuous)
  92     'hecsoisttererteipexhomen'
  93     >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(2, 1))
  94     'heecisoosttrrtepeixhemen'
  95     >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 3, 2))
  96     'hxtomephescieretoeisnter'
  97     >>> amsco_transposition_encipher('hereissometexttoencipher', 'cipher', fillpattern=(1, 3, 2), fillstyle=AmscoFillStyle.continuous)
  98     'hxomeiphscerettoisenteer'
  99     """
 100     grid = amsco_transposition_positions(message, keyword,
 101         fillpattern=fillpattern, fillstyle=fillstyle)
 102     ct_as_grid = [[message[s.start:s.end] for s in r] for r in grid]
 103     return combine_every_nth(ct_as_grid)
 104
 105
 106 def amsco_transposition_decipher(message, keyword,
 107     fillpattern=(1,2), fillstyle=AmscoFillStyle.reverse_each_row):
 108     """AMSCO transposition decipher
 109
 110     >>> amsco_transposition_decipher('hoteelhler', 'abc', fillpattern=(1, 2))
 111     'hellothere'
 112     >>> amsco_transposition_decipher('hetelhelor', 'abc', fillpattern=(2, 1))
 113     'hellothere'
 114     >>> amsco_transposition_decipher('hotelerelh', 'acb', fillpattern=(1, 2))
 115     'hellothere'
 116     >>> amsco_transposition_decipher('hetelorlhe', 'acb', fillpattern=(2, 1))
 117     'hellothere'
 118     >>> amsco_transposition_decipher('etecstthhomoerereenisxip', 'encode')
 119     'hereissometexttoencipher'
 120     >>> amsco_transposition_decipher('hetcsoeisterereipexthomn', 'cipher', fillpattern=(1, 2))
 121     'hereissometexttoencipher'
 122     >>> amsco_transposition_decipher('hecsoisttererteipexhomen', 'cipher', fillpattern=(1, 2), fillstyle=AmscoFillStyle.continuous)
 123     'hereissometexttoencipher'
 124     >>> amsco_transposition_decipher('heecisoosttrrtepeixhemen', 'cipher', fillpattern=(2, 1))
 125     'hereissometexttoencipher'
 126     >>> amsco_transposition_decipher('hxtomephescieretoeisnter', 'cipher', fillpattern=(1, 3, 2))
 127     'hereissometexttoencipher'
 128     >>> amsco_transposition_decipher('hxomeiphscerettoisenteer', 'cipher', fillpattern=(1, 3, 2), fillstyle=AmscoFillStyle.continuous)
 129     'hereissometexttoencipher'
 130     """
 131
 132     grid = amsco_transposition_positions(message, keyword,
 133         fillpattern=fillpattern, fillstyle=fillstyle)
 134     transposed_sections = [s for c in [l for l in zip(*grid)] for s in c]
 135     plaintext_list = [''] * len(transposed_sections)
 136     current_pos = 0
 137     for slice in transposed_sections:
 138         plaintext_list[slice.index] = message[current_pos:current_pos-slice.start+slice.end][:len(message[slice.start:slice.end])]
 139         current_pos += len(message[slice.start:slice.end])
 140     return cat(plaintext_list)
 141
 142
 143 def amsco_break(message, translist=transpositions, patterns = [(1, 2), (2, 1)],
 144                                   fillstyles = [AmscoFillStyle.continuous,
 145                                                 AmscoFillStyle.same_each_row,
 146                                                 AmscoFillStyle.reverse_each_row],
 147                                   fitness=Pbigrams,
 148                                   chunksize=500):
 149     """Breaks an AMSCO transposition cipher using a dictionary and
 150     n-gram frequency analysis
 151
 152     >>> amsco_break(amsco_transposition_encipher(sanitise( \
 153             "It is a truth universally acknowledged, that a single man in \
 154              possession of a good fortune, must be in want of a wife. However \
 155              little known the feelings or views of such a man may be on his \
 156              first entering a neighbourhood, this truth is so well fixed in \
 157              the minds of the surrounding families, that he is considered the \
 158              rightful property of some one or other of their daughters."), \
 159         'encipher'), \
 160         translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
 161                    (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
 162                    (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
 163         patterns=[(1, 2)]) # doctest: +ELLIPSIS
 164     (((2, 0, 5, 3, 1, 4, 6), (1, 2), <AmscoFillStyle.continuous: 1>), -709.4646722...)
 165     >>> amsco_break(amsco_transposition_encipher(sanitise( \
 166             "It is a truth universally acknowledged, that a single man in \
 167              possession of a good fortune, must be in want of a wife. However \
 168              little known the feelings or views of such a man may be on his \
 169              first entering a neighbourhood, this truth is so well fixed in \
 170              the minds of the surrounding families, that he is considered the \
 171              rightful property of some one or other of their daughters."), \
 172         'encipher', fillpattern=(2, 1)), \
 173         translist={(2, 0, 5, 3, 1, 4, 6): ['encipher'], \
 174                    (5, 0, 6, 1, 3, 4, 2): ['fourteen'], \
 175                    (6, 1, 0, 4, 5, 3, 2): ['keyword']}, \
 176         patterns=[(1, 2), (2, 1)], fitness=Ptrigrams) # doctest: +ELLIPSIS
 177     (((2, 0, 5, 3, 1, 4, 6), (2, 1), <AmscoFillStyle.continuous: 1>), -997.0129085...)
 178     """
 179     with multiprocessing.Pool() as pool:
 180         helper_args = [(message, trans, pattern, fillstyle, fitness)
 181                        for trans in translist
 182                        for pattern in patterns
 183                        for fillstyle in fillstyles]
 184         # Gotcha: the helper function here needs to be defined at the top level
 185         #   (limitation of Pool.starmap)
 186         breaks = pool.starmap(amsco_break_worker, helper_args, chunksize)
 187         return max(breaks, key=lambda k: k[1])
 188
 189 def amsco_break_worker(message, transposition,
 190         pattern, fillstyle, fitness):
 191     plaintext = amsco_transposition_decipher(message, transposition,
 192         fillpattern=pattern, fillstyle=fillstyle)
 193     fit = fitness(sanitise(plaintext))
 194     return (transposition, pattern, fillstyle), fit
 195
 196 if __name__ == "__main__":
 197     import doctest