szyfrow/polybius.py

   1 import multiprocessing
   2 from szyfrow.support.utilities import *
   3 from szyfrow.support.language_models import *
   4 from szyfrow.keyword_cipher import KeywordWrapAlphabet, keyword_cipher_alphabet_of
   5
   6 def polybius_grid(keyword, column_order, row_order, letters_to_merge=None,
   7                   wrap_alphabet=KeywordWrapAlphabet.from_a):
   8     """Grid for a Polybius cipher, using a keyword to rearrange the
   9     alphabet.
  10
  11
  12     >>> polybius_grid('a', 'abcde', 'abcde')['x'] == ('e', 'c')
  13     True
  14     >>> polybius_grid('elephant', 'abcde', 'abcde')['e'] == ('a', 'a')
  15     True
  16     >>> polybius_grid('elephant', 'abcde', 'abcde')['b'] == ('b', 'c')
  17     True
  18     """
  19     alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet=wrap_alphabet)
  20     if letters_to_merge is None:
  21         letters_to_merge = {'j': 'i'}
  22     grid = {l: k
  23             for k, l in zip([(c, r) for c in column_order for r in row_order],
  24                 [l for l in alphabet if l not in letters_to_merge])}
  25     for l in letters_to_merge:
  26         grid[l] = grid[letters_to_merge[l]]
  27     return grid
  28
  29 def polybius_reverse_grid(keyword, column_order, row_order, letters_to_merge=None,
  30                   wrap_alphabet=KeywordWrapAlphabet.from_a):
  31     """Grid for decrypting using a Polybius cipher, using a keyword to
  32     rearrange the alphabet.
  33
  34     >>> polybius_reverse_grid('a', 'abcde', 'abcde')['e', 'c'] == 'x'
  35     True
  36     >>> polybius_reverse_grid('elephant', 'abcde', 'abcde')['a', 'a'] == 'e'
  37     True
  38     >>> polybius_reverse_grid('elephant', 'abcde', 'abcde')['b', 'c'] == 'b'
  39     True
  40     """
  41     alphabet = keyword_cipher_alphabet_of(keyword, wrap_alphabet=wrap_alphabet)
  42     if letters_to_merge is None:
  43         letters_to_merge = {'j': 'i'}
  44     grid = {k: l
  45             for k, l in zip([(c, r) for c in column_order for r in row_order],
  46                 [l for l in alphabet if l not in letters_to_merge])}
  47     return grid
  48
  49
  50 def polybius_flatten(pair, column_first):
  51     """Convert a pair of characters into a single string."""
  52     if column_first:
  53         return str(pair[1]) + str(pair[0])
  54     else:
  55         return str(pair[0]) + str(pair[1])
  56
  57 def polybius_encipher(message, keyword, column_order, row_order,
  58                       column_first=False,
  59                       letters_to_merge=None, wrap_alphabet=KeywordWrapAlphabet.from_a):
  60     """Encipher a message with Polybius cipher, using a keyword to rearrange
  61     the alphabet
  62
  63
  64     >>> polybius_encipher('this is a test message for the ' \
  65           'polybius decipherment', 'elephant', \
  66           [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], \
  67           wrap_alphabet=KeywordWrapAlphabet.from_last)
  68     '2214445544551522115522511155551543114252542214111352123234442355411135441314115451112122'
  69     >>> polybius_encipher('this is a test message for the ' \
  70           'polybius decipherment', 'elephant', 'abcde', 'abcde', \
  71           column_first=False)
  72     'bbadccddccddaebbaaddbbceaaddddaecbaacadadcbbadaaacdaabedbcccdeddbeaabdccacadaadcceaababb'
  73     >>> polybius_encipher('this is a test message for the ' \
  74           'polybius decipherment', 'elephant', 'abcde', 'abcde', \
  75           column_first=True)
  76     'bbdaccddccddeabbaaddbbecaaddddeabcaaacadcdbbdaaacaadbadecbccedddebaadbcccadaaacdecaaabbb'
  77     """
  78     grid = polybius_grid(keyword, column_order, row_order, letters_to_merge, wrap_alphabet)
  79     return cat(polybius_flatten(grid[l], column_first)
  80                for l in message
  81                if l in grid)
  82
  83
  84 def polybius_decipher(message, keyword, column_order, row_order,
  85                       column_first=False,
  86                       letters_to_merge=None, wrap_alphabet=KeywordWrapAlphabet.from_a):
  87     """Decipher a message with a Polybius cipher, using a keyword to rearrange
  88     the alphabet
  89
  90     >>> polybius_decipher('bbdaccddccddeabbaaddbbecaaddddeabcaaacadcdbbdaaaca'\
  91     'adbadecbccedddebaadbcccadaaacdecaaabbb', 'elephant', 'abcde', 'abcde', \
  92     column_first=False)
  93     'toisisvtestxessvbephktoefhnugiysweqifoekxelt'
  94
  95     >>> polybius_decipher('bbdaccddccddeabbaaddbbecaaddddeabcaaacadcdbbdaaaca'\
  96     'adbadecbccedddebaadbcccadaaacdecaaabbb', 'elephant', 'abcde', 'abcde', \
  97     column_first=True)
  98     'thisisatestmessageforthepolybiusdecipherment'
  99     """
 100     grid = polybius_reverse_grid(keyword, column_order, row_order, letters_to_merge, wrap_alphabet)
 101     column_index_type = type(column_order[0])
 102     row_index_type = type(row_order[0])
 103     if column_first:
 104         pairs = [(column_index_type(p[1]), row_index_type(p[0]))
 105           for p in chunks(message, 2)]
 106     else:
 107         pairs = [(row_index_type(p[0]), column_index_type(p[1]))
 108           for p in chunks(message, 2)]
 109     return cat(grid[p] for p in pairs if p in grid)
 110
 111
 112 def polybius_break(message, column_labels, row_labels,
 113                       letters_to_merge=None,
 114                       wordlist=keywords, fitness=Pletters,
 115                       number_of_solutions=1, chunksize=500):
 116     """Breaks a Polybius substitution cipher using a dictionary and
 117     frequency analysis
 118
 119     >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
 120           'polybius decipherment', 'elephant', 'abcde', 'abcde'), \
 121           'abcde', 'abcde', \
 122           wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
 123     (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
 124     -54.53880...)
 125     >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
 126           'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=True), \
 127           'abcde', 'abcde', \
 128           wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
 129     (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', True), \
 130     -54.53880...)
 131     >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
 132           'polybius decipherment', 'elephant', 'abcde', 'abcde', column_first=False), \
 133           'abcde', 'abcde', \
 134           wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
 135     (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'abcde', False), \
 136     -54.53880...)
 137     >>> polybius_break_mp(polybius_encipher('this is a test message for the ' \
 138           'polybius decipherment', 'elephant', 'abcde', 'pqrst', column_first=True), \
 139           'abcde', 'pqrst', \
 140           wordlist=['cat', 'elephant', 'kangaroo']) # doctest: +ELLIPSIS, +NORMALIZE_WHITESPACE
 141     (('elephant', <KeywordWrapAlphabet.from_a: 1>, 'abcde', 'pqrst', True), \
 142     -54.53880...)
 143     """
 144     if letters_to_merge is None:
 145         letters_to_merge = {'j': 'i'}
 146     with multiprocessing.Pool() as pool:
 147         helper_args = [(message, word, wrap,
 148                         column_labels, row_labels, column_first,
 149                         letters_to_merge,
 150                         fitness)
 151                        for word in wordlist
 152                        for wrap in KeywordWrapAlphabet
 153                        for column_first in [False, True]]
 154         # Gotcha: the helper function here needs to be defined at the top level
 155         #   (limitation of Pool.starmap)
 156         breaks = pool.starmap(polybius_break_worker, helper_args, chunksize)
 157         if number_of_solutions == 1:
 158             return max(breaks, key=lambda k: k[1])
 159         else:
 160             return sorted(breaks, key=lambda k: k[1], reverse=True)[:number_of_solutions]
 161
 162 def polybius_break_worker(message, keyword, wrap_alphabet,
 163                           column_order, row_order, column_first,
 164                           letters_to_merge,
 165                           fitness):
 166     plaintext = polybius_decipher(message, keyword,
 167                                   column_order, row_order,
 168                                   column_first=column_first,
 169                                   letters_to_merge=letters_to_merge,
 170                                   wrap_alphabet=wrap_alphabet)
 171     if plaintext:
 172         fit = fitness(plaintext)
 173     else:
 174         fit = float('-inf')
 175     return (keyword, wrap_alphabet, column_order, row_order, column_first), fit
 176
 177 if __name__ == "__main__":
 178     import doctest