Columnar Transposition
The Columnar Transposition rearranges the plaintext letters, based on a matrix filled with letters in the order determined by the secret keyword.
Usage
The Columnar Transposition is a simple transposition cipher that can be performed manually, without the need of using additional equipment. It was very popular throughout centuries, and it was used in various situations by diplomats, soldiers, and spies.
The encryption and decryption can be performed by hand, using a piece of paper and a simple matrix, into which the user enters the letters of the message.
Algorithm
The name of the cipher comes after the operations on a matrix, that are performed during both, encryption and decryption. The number of columns of the matrix is determined by the secret key.
The secret key is usually a word (or just a sequence of letters). It has to be converted into a sequence of numbers. The numbers are defined by an alphabetical order of the letters in the keyword. The letter which is first in the alphabet will be the number 1, the second letter in the alphabetical order will be 2, and so on.
If there are multiple identical letters in the keyword, each next occurrence of the same letter should be converted into a number that is equal to the number for the previous occurrence increased by one.
For example, the keyword:
SWINDON
would produce the following sequence of numbers:
6723154
We can see, that we converted the letters N into the numbers 3 and 4.
To encrypt a message, all the letters should be entered into the matrix, row by row, from left to right. The size of the matrix depends on the length of the message. The only known dimension is width, which is determined by the length of the secret keyword (which is the same as the length of the corresponding sequence of numbers), and known to both sides of the communication.
If, after entering the whole message, there are some empty cells in the bottom row of the matrix, one of two approaches can be taken:
- The cells may be left empty, and just ignored during all further operations (this is so called an irregular columnar transposition cipher).
- The sender may enter there some rare letters, and treat them as a part of the plaintext. After decryption, the receiver should be able to determine, that the letters have no sense, and that they should be ignored (in this case, the cipher is called a regular columnar transposition cipher).
Next, the letters should be read off in a specific way, and write down to form the ciphertext. The order of reading the letters is determined by the sequence of numbers, produced from the keyword. They should be read column by column, from top to bottom, starting from the column, which position is the same as the position of the number 1 in the key sequence. The next column to read off is determined by the number 2 in the key sequence, and so on, until all the columns are read off. To make this step easier, it is recommended to write the sequence numbers above the corresponding columns.
As an example, let's encrypt a message A Midsummer Night's Dream, which is a comedy written by Shakespeare. We will use the secret key mentioned above. The number sequence derived from this keyword is 6723154, so the matrix created for the encryption will have seven columns.
After removing all non-letter characters, and changing the letters to upper case, the message should be entered into the table:
| 6 | 7 | 2 | 3 | 1 | 5 | 4 |
| A | M | I | D | S | U | M |
| M | E | R | N | I | G | H |
| T | S | D | R | E | A | M |
Above the message, there are numbers derived from the keyword. These numbers determine the order, in which the columns should be read (top to bottom), and appended to the produced ciphertext. In our example, the first column will be SIE, the second will be IRD, and so on. The produced ciphertext is:
SIE IRD DNR MHM UGA AMT MES
Finally, after removing the spaces, which were added to indicate separate columns, we receive the encrypted message:
SIEIRDDNRMHMUGAAMTMES
To decrypt a received ciphertext, the receiver has to perform the following steps:
- Knowing the secret keyword, and the length of the received message, the table of the same size, as the one used for encryption, should be created.
- The ciphertext should be entered into columns, from the leftmost columns to the rightmost column, from top to bottom.
- The columns should be rearranged, and put into the order defined by the keyword.
- The decrypted message should be read out, row by row, starting from the top row, and from left to right.
Security of the Columnar Transposition
The Columnar Transposition was used for serious purposes all over the world, until the beginning of the second half of the 20th century.
To break the ciphertext, an attacker should try to create the tables of different sizes, enter the encrypted message down into the columns, and for each table look for anagrams appearing in rows.
Implementation
Encryption
Below, there are encryption functions written in Python. The input parameters are the message and the secret keyword. The main function, encrypt, uses two helper functions to create the matrix and the keyword sequence of numbers.
matrix = createEncMatrix(len(keyword), message)
keywordSequence = getKeywordSequence(keyword)
ciphertext = "";
for num in range(len(keywordSequence)):
pos = keywordSequence.index(num+1)
for row in range(len(matrix)):
if len(matrix[row]) > pos:
ciphertext += matrix[row][pos]
return ciphertext
def createEncMatrix(width, message):
r = 0
c = 0
matrix = [[]]
for pos, ch in enumerate(message):
matrix[r].append(ch)
c += 1
if c >= width:
c = 0
r += 1
matrix.append([])
return matrix
def getKeywordSequence(keyword):
sequence = []
for pos, ch in enumerate(keyword):
previousLetters = keyword[:pos]
newNumber = 1
for previousPos, previousCh in enumerate(previousLetters):
if previousCh > ch:
sequence[previousPos] += 1
else:
newNumber += 1
sequence.append(newNumber)
return sequence
Decryption
The Python functions written below allow to decrypt Columnar Transposition ciphertext. The input parameters are the message and the secret keyword. The main function, decrypt, uses helper functions to create the matrix and the keyword sequence of numbers.
matrix = createDecrMatrix(getKeywordSequence(keyword), message)
plaintext = "";
for r in range(len(matrix)):
for c in range (len(matrix[r])):
plaintext += matrix[r][c]
return plaintext
def createDecrMatrix(keywordSequence, message):
width = len(keywordSequence)
height = len(message) / width
if height * width < len(message):
height += 1
matrix = createEmptyMatrix(width, height, len(message))
pos = 0
for num in range(len(keywordSequence)):
column = keywordSequence.index(num+1)
r = 0
while (r < len(matrix)) and (len(matrix[r]) > column):
matrix[r][column] = message[pos]
r += 1
pos += 1
return matrix
def createEmptyMatrix(width, height, length):
matrix = []
totalAdded = 0
for r in range(height):
matrix.append([])
for c in range(width):
if totalAdded >= length:
return matrix
matrix[r].append('')
totalAdded += 1
return matrix
def getKeywordSequence(keyword):
sequence = []
for pos, ch in enumerate(keyword):
previousLetters = keyword[:pos]
newNumber = 1
for previousPos, previousCh in enumerate(previousLetters):
if previousCh > ch:
sequence[previousPos] += 1
else:
newNumber += 1
sequence.append(newNumber)
return sequence
