cipher/amsco.py

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