cipher/railfence.py

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