Introduction To Haskell
Columnar Transposition Cipher

Introduction

Columnar transposition, as its name suggests, is a method of enciphering text based on columns. A keyword is used to determine how many columns should be used and the order in which those columns should be placed in the enciphered text.

In this example, we will encrypt the message, 'The secret is out. Run and hide.' using the keyword, 'LEMON'.

STEP 1 - Write out the message in columns

For manual encryption, we start by creating a table with the keyword as a heading. The message is written out in rows underneath each heading. Our message wasn't quite long enough to fill all of the spaces in the table so a random letter was added.

LEMON
THESE
CRETI
SOUTR
UNAND
HIDEC

Step 2 - Determine the column order from the keyword

The numbering shown underneath the letters of the keyword is based on the order of these letters in the alphabet.

L
1
E
0
M
2
O
4
N
3
THESE
CRETI
SOUTR
UNAND
HIDEC

Step 3 - Construct the cipher text by taking columns in this order

Starting with the column marked 0 and following the numbers, we write out the finished message,

HRONI TCSUH EEUAD EIRDC STTNE

The spacing here would be an issue. It tells you the number of the columns and their length. This would be enough to crack the message. Changing the pattern of spaces would help.

Programming

A functional program for this is marginally easier than the imperative version although, I think I might have favoured that paradigm in working out the steps. The where statement is used here to allow some locally defined functions outlining the steps of the process.

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


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

-- make keyword length slices from message with padding & transpose
slice :: [Char] -> [Char] -> [[Char]]
slice m k = transpose (chunksOf (length k) b)
    where
        a = (length m + length k)
        n = a - (a `mod` (length k)) 
        b = take n (cycle m)

-- encipher a message
enc :: [Char] -> [Char] -> String
enc m k = concatMap fst s
    where
        c = slice (tidy m) (tidy k)
        o = zip c k
        s = sortBy (comparing snd) o

-- decipher a message
dec :: [Char] -> [Char] -> [Char]
dec m k = tidy.unwords.transpose $ (map fst ys)
    where
        xs = chunksOf (length k) m 
        ks = zip xs k
        ys = sortBy (comparing snd) ks

Although all of the imported library functions can be recreated in Prelude, it makes the program a little harder to follow.

The tidy function is for stripping non-letter characters out of arguments and converting to upper case.

The slice function is used for encrypting. The complication is the need to pad out the message before splitting into even-sized chunks. The transpose function does the work of converting rows into columns.

To encipher the message, the arguments are passed to the tidy function and sliced according to the keyword length. The columns are sorted by order of keyword letters and the final message created.

Decpihering is a little easier. The message is assumed to be in the same form as the ouptut from the enciphering function. With the keyword, it is easy to split the message up and reorder the columns according to the keyword.

Writing functions like this can be a useful process. You write the where parts first and use them as the first line as you build each one. That way, you can see what each part of your function is doing to the arguments.

WinGHCI