Ciphers
Substitution Ciphers
Transposition Ciphers
Polybius Square
Steganography
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.
| L | E | M | O | N |
|---|---|---|---|---|
| T | H | E | S | E |
| C | R | E | T | I |
| S | O | U | T | R |
| U | N | A | N | D |
| H | I | D | E | C |
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 |
|---|---|---|---|---|
| T | H | E | S | E |
| C | R | E | T | I |
| S | O | U | T | R |
| U | N | A | N | D |
| H | I | D | E | C |
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 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.