railfence.py

   1 from utilities import *
   2 from language_models import *
   3 from enum import Enum
   4 from itertools import starmap
   5 from itertools import zip_longest
   6
   7 from logger import logger
   8
   9 def railfence_encipher(message, height, fillvalue=''):
  10     """Railfence cipher.
  11     Works by splitting the text into sections, then reading across them to
  12     generate the rows in the cipher. The rows are then combined to form the
  13     ciphertext.
  14
  15     Example: the plaintext "hellotherefriends", with a height of four, written
  16     out in the railfence as
  17        h h i
  18        etere*
  19        lorfns
  20        l e d
  21     (with the * showing the one character to finish the last section).
  22     Each 'section' is two columns, but unfolded. In the example, the first
  23     section is 'hellot'.
  24
  25     >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 2, fillvalue='!')
  26     'hlohraateerishsslnpeefetotsigaleccpeselteevsmhatetiiaogicotxfretnrifneihr!'
  27     >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 3, fillvalue='!')
  28     'horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihr!!lhateihsnefttiaece!'
  29     >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 5, fillvalue='!')
  30     'hresleogcseeemhetaocofrnrner!!lhateihsnefttiaece!!ltvsatiigitxetifih!!oarspeslp!'
  31     >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 10, fillvalue='!')
  32     'hepisehagitnr!!lernesge!!lmtocerh!!otiletap!!tseaorii!!hassfolc!!evtitffe!!rahsetec!!eixn!'
  33     >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 3)
  34     'horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihrlhateihsnefttiaece'
  35     >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 5)
  36     'hresleogcseeemhetaocofrnrnerlhateihsnefttiaeceltvsatiigitxetifihoarspeslp'
  37     >>> railfence_encipher('hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers', 7)
  38     'haspolsevsetgifrifrlatihnettaeelemtiocxernhorersleesgcptehaiaottneihesfic'
  39     """
  40     sections = chunks(message, (height - 1) * 2, fillvalue=fillvalue)
  41     n_sections = len(sections)
  42     # Add the top row
  43     rows = [cat([s[0] for s in sections])]
  44     # process the middle rows of the grid
  45     for r in range(1, height-1):
  46         rows += [cat([s[r:r+1] + s[height*2-r-2:height*2-r-1] for s in sections])]
  47     # process the bottom row
  48     rows += [cat([s[height - 1:height] for s in sections])]
  49     # rows += [wcat([s[height - 1] for s in sections])]
  50     return cat(rows)
  51
  52 def railfence_decipher(message, height, fillvalue=''):
  53     """Railfence decipher.
  54     Works by reconstructing the grid used to generate the ciphertext, then
  55     unfolding the sections so the text can be concatenated together.
  56
  57     Example: given the ciphertext 'hhieterelorfnsled' and a height of 4, first
  58     work out that the second row has a character missing, find the rows of the
  59     grid, then split the section into its two columns.
  60
  61     'hhieterelorfnsled' is split into
  62         h h i
  63         etere
  64         lorfns
  65         l e d
  66     (spaces added for clarity), which is stored in 'rows'. This is then split
  67     into 'down_rows' and 'up_rows':
  68
  69     down_rows:
  70        hhi
  71        eee
  72        lrn
  73        led
  74
  75     up_rows:
  76        tr
  77        ofs
  78
  79     These are then zipped together (after the up_rows are reversed) to recover
  80     the plaintext.
  81
  82     Most of the procedure is about finding the correct lengths for each row then
  83     splitting the ciphertext into those rows.
  84
  85     >>> railfence_decipher('hlohraateerishsslnpeefetotsigaleccpeselteevsmhatetiiaogicotxfretnrifneihr!', 2).strip('!')
  86     'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
  87     >>> railfence_decipher('horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihr!!lhateihsnefttiaece!', 3).strip('!')
  88     'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
  89     >>> railfence_decipher('hresleogcseeemhetaocofrnrner!!lhateihsnefttiaece!!ltvsatiigitxetifih!!oarspeslp!', 5).strip('!')
  90     'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
  91     >>> railfence_decipher('hepisehagitnr!!lernesge!!lmtocerh!!otiletap!!tseaorii!!hassfolc!!evtitffe!!rahsetec!!eixn!', 10).strip('!')
  92     'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
  93     >>> railfence_decipher('horaersslpeeosglcpselteevsmhatetiiaogicotxfretnrifneihrlhateihsnefttiaece', 3)
  94     'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
  95     >>> railfence_decipher('hresleogcseeemhetaocofrnrnerlhateihsnefttiaeceltvsatiigitxetifihoarspeslp', 5)
  96     'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
  97     >>> railfence_decipher('haspolsevsetgifrifrlatihnettaeelemtiocxernhorersleesgcptehaiaottneihesfic', 7)
  98     'hellothereavastmeheartiesthisisalongpieceoftextfortestingrailfenceciphers'
  99     """
 100     # find the number and size of the sections, including how many characters
 101     #   are missing for a full grid
 102     n_sections = math.ceil(len(message) / ((height - 1) * 2))
 103     padding_to_add = n_sections * (height - 1) * 2 - len(message)
 104     # row_lengths are for the both up rows and down rows
 105     row_lengths = [n_sections] * (height - 1) * 2
 106     for i in range((height - 1) * 2 - 1, (height - 1) * 2 - (padding_to_add + 1), -1):
 107         row_lengths[i] -= 1
 108     # folded_rows are the combined row lengths in the middle of the railfence
 109     folded_row_lengths = [row_lengths[0]]
 110     for i in range(1, height-1):
 111         folded_row_lengths += [row_lengths[i] + row_lengths[-i]]
 112     folded_row_lengths += [row_lengths[height - 1]]
 113     # find the rows that form the railfence grid
 114     rows = []
 115     row_start = 0
 116     for i in folded_row_lengths:
 117         rows += [message[row_start:row_start + i]]
 118         row_start += i
 119     # split the rows into the 'down_rows' (those that form the first column of
 120     #   a section) and the 'up_rows' (those that ofrm the second column of a
 121     #   section).
 122     down_rows = [rows[0]]
 123     up_rows = []
 124     for i in range(1, height-1):
 125         down_rows += [cat([c for n, c in enumerate(rows[i]) if n % 2 == 0])]
 126         up_rows += [cat([c for n, c in enumerate(rows[i]) if n % 2 == 1])]
 127     down_rows += [rows[-1]]
 128     up_rows.reverse()
 129     return cat(c for r in zip_longest(*(down_rows + up_rows), fillvalue='') for c in r)
 130
 131
 132 def railfence_break(message, max_key_length=20,
 133                      fitness=Pletters, chunksize=500):
 134     """Breaks a railfence cipher using a matrix of given rank and letter frequencies
 135
 136
 137     """
 138
 139     sanitised_message = sanitise(message)
 140     results = starmap(worker, [(sanitised_message, i, fitness)
 141                                for i in range(2, max_key_length+1)])
 142     return max(results, key=lambda k: k[1])
 143
 144
 145 def railfence_break(message, max_key_length=20,
 146                      fitness=Pbigrams, chunksize=500):
 147     """Breaks a railfence cipher using a range of lengths and
 148     n-gram frequency analysis
 149
 150     >>> railfence_break(railfence_encipher(sanitise( \
 151             "It is a truth universally acknowledged, that a single man in \
 152              possession of a good fortune, must be in want of a wife. However \
 153              little known the feelings or views of such a man may be on his \
 154              first entering a neighbourhood, this truth is so well fixed in \
 155              the minds of the surrounding families, that he is considered the \
 156              rightful property of some one or other of their daughters."), \
 157         7)) # doctest: +ELLIPSIS
 158     (7, -709.46467226...)
 159     >>> railfence_break(railfence_encipher(sanitise( \
 160             "It is a truth universally acknowledged, that a single man in \
 161              possession of a good fortune, must be in want of a wife. However \
 162              little known the feelings or views of such a man may be on his \
 163              first entering a neighbourhood, this truth is so well fixed in \
 164              the minds of the surrounding families, that he is considered the \
 165              rightful property of some one or other of their daughters."), \
 166         7), \
 167         fitness=Ptrigrams) # doctest: +ELLIPSIS
 168     (7, -997.0129085...)
 169     """
 170     def worker(message, height, fitness):
 171         plaintext = railfence_decipher(message, height)
 172         fit = fitness(plaintext)
 173         return height, fit
 174
 175     sanitised_message = sanitise(message)
 176     results = starmap(worker, [(sanitised_message, i, fitness)
 177                                for i in range(2, max_key_length+1)])
 178     return max(results, key=lambda k: k[1])