# Columnar Transposition

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,

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 Columnar Transposition

### Encryption

We'll implement the algorithm in stages and use the message and keyword from the example on this page.

The first step is to tidy up the message and remove all non-letter characters. We'll also convert the whole thing to upper case.

```plain ← "The secret is out. Run and hide." upper ← UPPERCASE(plain) tidy ← "" FOR letter ← 0 TO upper.LENGTH - 1    tmpASC ← ASCII CODE OF upper[letter]    IF tmpASC > = 65 AND tmpASC <= 90 THEN       tidy ← tidy + CHR(tmpASC)    END IF END FOR plain ← tidy ```

The next step is to pad out the message with random letters so that it will fit our grid exactly.

```keyword ← "LEMON" WHILE plain.LENGTH MOD keyword.LENGTH <> 0    plain ← plain + CHR(random number from 65 to 90) END WHILE```

Next we create our columns. We aren't going to store the grid as individual letters - we don't need to. Each column will be an element in an array of strings.

```DECLARE STRING columns[keyword.LENGTH - 1] FOR i ← 0 TO columns.LENGTH - 1    columns[i] ← "" END FOR FOR i ← 0 TO plain.LENGTH - 1    columns[i MOD keyword.LENGTH] ← columns[i MOD keyword.LENGTH] + plain(i) END FOR```

Before we can print out the cipher text, we need to know the diplay order for each column. There are lots of ways to do this. This one depends on being able to convert the keyword string into an array of characters.

```DECLARE INTEGER perms[keyword.LENGTH - 1] DECLARE CHAR sortedKey[keyword.LENGTH - 1] sortedKey ← keyword.TOCHARARRAY() SORT sortedKey FOR i ← 0 TO keyword.LENGTH - 1    perms[i] = keyword.INDEXOF(sortedKey[i]) END FOR // Form the cipher text cipher ← "" FOR i ← 0 TO columns.LENGTH - 1    cipher ← cipher + columns[perms[i]] END FOR OUTPUT cipher```

### Decryption

This algorithm depends on the message being encrypted using the approach previously described. In particular, it depends on the grid being regular and all spaces filled in. The padding characters will be in our plain text but will not affect readability.

The first step is to rebuild the column strings from the message.

```cipher ← "HRONITCSUHEEUADEIRDCSTTNE" keyword ← "LEMON" DECLARE STRING columns[keyword.LENGTH - 1] FOR i &larr 0 TO keyword.LENGTH - 1    columns[i] = cipher.SUBSTRING(i * (cipher.LENGTH DIV keyword.LENGTH), cipher.LENGTH DIV keyword.LENGTH) END FOR```

These columns will not be in the original order since they were rearranged according to the keyword. We can use the same algorithm as before to work out the correct column order.

```DECLARE INTEGER perms[keyword.LENGTH - 1] DECLARE CHAR sortedKey[keyword.LENGTH - 1] sortedKey ← keyword.TOCHARARRAY() SORT sortedKey FOR i ← 0 TO keyword.LENGTH - 1    perms[i] = keyword.INDEXOF(sortedKey[i]) END FOR```

Once we have these numbers, we can rebuild the columns in the correct order,

```DECLARE STRING sortedColumns[keyword.LENGTH - 1] FOR i ← 0 TO keyword.LENGTH - 1    sortedColumns[i] ← columns[perms[i]] END FOR```

Finally, we have the information to reconstruct the original plain text,

```plain ← "" FOR i &larr 0 TO sortedColumns[0].LENGTH    FOR j ← 0 TO keyword.LENGTH -1       plain ← plain + sortedColumns[j][i]    END FOR END FOR OUTPUT plain```

## Challenges

This cipher is best used when combined with another cipher, like a substitution cipher. Double columnar transposition, where the message is transposed twice, is also quite effective. Adding the facility for this to your program would be useful.

The pseudocode used a regular grid, where all spaces were filled with random letters. Adapting your code to work with an irregular grid would also be an interesting way to take your work forward.