Introduction To Haskell
Rail Fence Cipher

Introduction

The Rail Fence cipher is a transposition cipher. It gets its name from the way that letters are transposed during encryption. First determine the number of 'rails' to use. Then write the message out, a letter at a time, starting from the top rail. When you reach the bottom rail, climb back up the rails to the top. The message, 'The secret is out' is written below on a rail fence of size 3, with all of the spaces having been removed from the message.

T---E---T---U-
-H-S-C-E-I-O-T
--E---R---S---

To form the cipher text, the letters are read off horizontally, starting from the top left. In this case, the cipher text becomes TETUHSCEIOTERS.

Programming

This cipher is relatively difficult to program using imperative languages. To maie it easier to program in Haskell, I have made use of some functions from the Data module. This results in a reasonably simple program.

import Data.Char
import Data.List
import Data.Ord


-- tidy up a string for processing
tidy :: [Char] -> [Char]
tidy = map toUpper . filter isLetter

-- make the rail fence pattern in numbers
rows r = cycle ([0..r-2] ++ [r-1,r-2..1])

-- zip a plain text message with its rows
-- sort the tuples by row numbers
-- map the result with fst to get the letters
rail p r = map fst $ sortBy (comparing snd) $ zip (tidy p) (rows r)

-- tidying the first message empties a list of numbers
-- this is the list of positions that characters came from
derailmap n r = map fst $ sortBy (comparing snd) $ zip [0..n-1] $ rows r

-- zip the message with the positions and then use this to sort
derail xs r = map fst $ sortBy (comparing snd) $ zip xs (derailmap (length xs) r)

The approach used is based around the function, rows. This function makes an infinite list that is the basis of the rail fence. If we have 3 rails, the letters from our message go on rows 0,1,2,1,0,1,2,1,0...

The rail function uses the zip function to alternately take items from the message (character list) and the infinite list. This forms tuples of the character and its row number. Sorting the list by row number groups the characters correctly. We take the first item in the tuple to form a new character list, our encrypted message.

To derail we have to work out what positions our letters must have come from. Knowing the rail size means that we can test this out on a list of numbers. The derailmap function is there to allow for tidying of plain text when railing. This creates a list of positions.

The derail function takes the derailmap list and uses this to make tuples of the characters from the cipher text and their positions in the plain text. This list is sorted by the first item in the tuples and detupled the same way as when we railed.

WinGHCI