Transposition Algorithm in Python (Expert Guide)

What is a Transposition Algorithm?

A substitution algorithm, such as previously mentioned Caesar’s algorithm, works by substituting each symbol of the plaintext message with another symbol, according to a predetermined offset defined by a key.

In contrast, a transposition algorithm shifts, or changes the positions of its symbols by following a specific, predetermined key.

Since the plaintext message length and original symbols are preserved in the ciphertext, it is very easy to establish both the encryption and decryption procedures.

There are several different approaches to constructing a transposition cipher, but we will begin by introducing a simple one, where the plaintext is read symbol by symbol, and the symbols are placed inside of a two-dimensional matrix.

“Unfortunately, no one can be told what the Matrix is. You have to see it for yourself.” – Morpheus

We can think of a two-dimensional matrix as a data structure when we’re implementing it in a programming language, or as an array of elements in a more abstract, mathematical sense.

A matrix is a rectangular form defined by its rows m and columns n that form its dimensions, commonly expressed as A_m,n with dimensions m x n. Variable m stands for the number of rows, and variable n stands for the number of columns.

An individual element of matrix A is denoted as A_i,j, where i and j mark a specific row and column. Now that we have learned how to index a specific element of the matrix, we can explain how matrix transposition works.

There are numerous ways to transpose a matrix, but when we’re talking about pure mathematical transposition operation, it’s very simple and works like this: we take every element A_i,j of our matrix A and construct a new matrix A_t by placing the element on the position (j,i).

Effectively, we’re rotating the matrix elements around the primary diagonal, i.e. the one connecting the elements A_(0,0) and A_(m,n).

💡 Note: We have to take note that matrix indexing in math is usually one-based, but when we’re programming, the matrix indexing is usually zero-based, i.e. an index goes from 0 to m-1 for matrix rows and from 0 to n-1 for matrix columns.

The form of transposition we use in our transposition cipher works by rearranging the elements by using a key. First, let’s explain what a key is.

“We do only what we’re meant to do.” – The Keymaker

How a transposition algorithm will encrypt the plaintext depends on the key.

A key is an integer, i.e., a whole number, whose value can be anywhere between 2 and len(plaintext)/2.

We will take a look at this specific prerequisite and explain why the key size shouldn’t be outside of this range a bit later. But first, let’s explain how a key works.

The encryption process starts with the construction of a two-dimensional matrix of specific dimensions. Its dimensions are made of a specific number of rows and columns.

• The number of columns is simply set equal to the key, and we’ll refer to it as parameter ncols.
• The number of rows, which is a parameter we’ll refer to as nrows, is determined by two factors: the plaintext length, which we’ll write as len(plaintext), and the key, and we can calculate it by applying a simple formula: ceil(len(plaintext)/key).

💡 Function ceil() is both a program function and a mathematical function that rounds its argument up to the closest whole (integer) number.

For instance, ceil(2.5) = 3 and ceil(2) = 2. Now that we know our matrix dimensions, we can construct it and give it a practical name: matrix A, with its indices ranging from (0,0) to (nrows-1, ncols-1).

We are using zero-based indexing throughout the text to make our described algorithm easily transferrable to the source code at a later stage.

The Encryption and Decryption Step

Next, we proceed with the encryption process, i.e., we populate our matrix A by reading the plaintext message one symbol at a time, and by writing each symbol to matrix A, starting with the position A_(0,0) and the symbol at position plaintext[0] (index of the starting symbol in each iteration corresponds to the current column index), then continuing with the next symbol (+key positions away from the last read symbol) written to the position A_(1,0), i.e., row 1 and column 0.

After we write to position A_{(nrows-1, 0)}, which is the last position in the column, we wrap around to the first position in the next column, currently A_(0,1), and to the symbol at position plaintext[1], and just continue with reading and writing in the same way.

Matrix A is populated after reading the last symbol from the plaintext and writing it to a position in the last row, nrows-1.

The column of the position can be anything in the range from 0 to ncols-1, depending on the length of the plaintext message, len(plaintext).

It is possible to have some empty positions in our matrix A after writing the entire plaintext message. This is possible since the matrix has to have a rectangular form, and that means we had to round up its number of columns by using the ceil() function to ensure enough space for the whole plaintext message.

In cases where len(plaintext)/key is not an integer, there will be some empty positions in the last row. Either way, the last encryption step works the same, regardless of having empty positions.

In this encryption step, we will produce the ciphertext message. After having our plaintext message written to matrix A, we generate the ciphertext message first by forming an empty string (see the source code).

Then, we start reading from matrix A by descending along each of the columns. The starting position is A_(0,0), which is where we read the first symbol and add it to the cipher string.

The next symbol read (and added to the cipher string) is at position A_(1,0), continuing down to A_{(nrows-1, 0)}.

Then we wrap around to position A_(0,1), descend accordingly to position A_(nrows-1,1), and follow the same pattern of movement over the matrix A until we reach the last symbol of our plaintext message.

At this point, we have our plaintext message completely transposed to a ciphertext message, because we wrote the plaintext message to matrix A by following a row-to-row pattern of movement, and read the contents of matrix A by following a column-to-column pattern of movement.

The following example will demonstrate how encryption works: if we take a plaintext message "Here is our first message!" with a key =  6, it would get encrypted as "Hsfmee ie!rorseuss rtai  g" and rearranged to fit in a matrix with dimensions nrows = 5 and ncols = 6,

Decryption steps are very similar to encryption steps, but they differ in two important points: our matrix’s dimensions are swapped, i.e., nrows = key and ncols = math.ceil(len(message) / key), and we also have to restore the empty positions (if there are any).

We populate our matrix A^t (‘t’ stands for transposed) by reading the ciphertext message one symbol at a time, and by writing each symbol to matrix A^t, starting with the position A^t_(0,0), then continuing with the next symbol written to the position A^t_(0,1), i.e. row 0 and column 1.

After we write to the position A^t_{(0, ncols-1)}, which is the last position in the row, we wrap around to the first position in the next row, currently A^t_(1,0), and just continue with reading and writing. Knowing that the empty positions can occur only in the last column, and by calculating their number:

empty_positions = nrows * ncols - len(message)

we can precisely determine the condition which will instruct us to wrap around and continue writing to the next row at column zero, expressed in a more compact and general form as A^t_(row+1,0).

The condition is simple and states that when column == ncols - 1 and row >= nrows - empty_positions, we should leave the current position empty (by wrapping around to the beginning of the next row).

Matrix A^t is populated after reading the last symbol from the ciphertext message and writing it to a position in the last row, nrows-1.

The column of the position can be anything in the range from 0 to ncols-1, or even ncols-2, if there is an empty position, depending on the length of the plaintext message, len(plaintext).

The following example will demonstrate how decryption works; if we continue with our ciphertext message "Hsfmee ie!rorseuss rtai  g" with a key =  6, it would get decrypted as "Here is our first message!" and rearranged to fit in a matrix with dimensions nrows = 6 and ncols = 5, with four empty positions:

Python Source Code

Here we’ll take a look at our source code and see how easy it is to figure out what’s going on.

The comments are here to help in understanding particular ideas and choices in each of the algorithm steps.

import math

def encrypt(key, message):
    # Simulates columns in the matrix by using string array.
    ciphertext = [''] * key
    # Iterates through each column in the ciphertext.
    for column in range(key):
        index = column
        # Iterates until the plaintext end.
        while index < len(message):
            # Places the character at the end of the column:
            ciphertext[column] += message[index]
            # Moves the index to the next symbol.
            index += key

    # Returns the ciphertext array as a single string.
    return ''.join(ciphertext)


def decrypt(key, message):
    # Calculates the matrix dimensions: how many rows and columns
    # - we need this for position tracking.
    nrows = key
    ncols = math.ceil(len(message) / key)

    # Calculates the number of empty positions in the matrix due to
    # the ceil() function.
    empty_positions = nrows * ncols - len(message)

    # Simulates columns in the matrix by using string array.
    plaintext = [''] * ncols

    # Initializes the position tracking variables.
    column = 0
    row = 0

    # Iterates through each symbol in the ciphered message.
    for symbol in message:
        # Fills the matrix in a row by row movement pattern.
        plaintext[column] += symbol
        column += 1

        # In case we're positioned after the last column...
        # ... or at the position that should be empty - such positions are
        # possible only in the last column - wrap to the start of the next row.
        if column == ncols or (column == ncols - 1 and row >= nrows - empty_positions):
            column = 0
            row += 1

    # Returns the plaintext array as a single string.
    return ''.join(plaintext)


message = 'Here is our first message!'
key = 6
ciphertext = encrypt(key, message)
# Delimits the ciphertext for displaying purposes, i.e. to show
# a <space> symbol if there is one at the end.
print(f'Ciphertext: {ciphertext}<end>')
# Prints the plaintext for algorithm validity checking.
plaintext = decrypt(key, ciphertext)
print(f'Plaintext: {plaintext}')

About the Value of a Key (Length)

I have previously remarked on the key value, stating that it can be anywhere between 2 and len(plaintext)/2 (boundaries included), and now is the best moment to explain what is it all about.

Since the transposition algorithm works by essentially turning rows into columns, it would make no sense to have a key = 1, because row after row would get read.

Still, with our matrix containing only one column, the ciphertext would end up being the same as the plaintext.

Hence, the minimum value for a key is 2.

For the second part of the remark, the key should be no longer than len(plaintext)/2 because otherwise, a part of the plaintext message would remain unencrypted.

Specifically, with a plaintext message of length = len(plaintext) and key > len(plaintext)/2, our matrix A would have dimensions nrows = 2, ncols = key.

With such dimensions, exactly 2 * key - len(plaintext) symbols would remain unencrypted, because their columns would be the only ones populated and they would transpose to themselves.

In the following example with key = 17 the red part of the message would get encrypted, but the red part would stay unencrypted:

Plaintext:  Here is our first message!
Ciphertext: H emrees siasg eo!ur first<end>

According to the formula and the recommendation for key value selection, we notice how our example plaintext message of 26 symbols and key = 17 left exactly 34 – 26 = 8 symbols unencrypted, because the bottom part of the row is empty.

Conclusion

In this article, we learned about Transposition Cipher, an encryption and decryption algorithm that shifts the plaintext symbols according to a selected key.

• First, we gave a few outlines of Transposition Cipher.
• Second, we saw and learned about the matrix. Neo would be so proud of us.
• Third, we got acquainted with the key role of the Key. Pun intended.
• Fourth, we explained how everything put together locks and unlocks our secrets.
• Fifth, we stormed through the source code and became one with the algorithm.
• Sixth, we looked in disbelief at how a badly chosen key could leave the door to Zion partially open.