Deciphering the Hill Cipher and Rail Fence Cipher Algorithms

Encryption and Decryption! You definitely must have come across these words once in your lifetime. Let me start with a very basic question then. What comes to our mind when we hear these two words? Maybe some of us will think about a detective like Sherlock Holmes decoding a mysterious message while solving a case on the streets of London, some will think about the famous movie ‘The Imitation Game’ where the famous mathematician Alan Turing helps the cryptography team to decipher the German Enigma Code, which saved millions of lives during the world war.

So basically, cryptography is very important in the view of transmitting confidential messages which can be decoded by only a few who know how to decipher it and save the classified information from getting into the wrong hands. Of course, until they know the key to decipher it ;)

In cryptography, Encryption is the process of translating plain text data, usually called plaintext into something that appears to be random and meaningless, usually called ciphertext. Decryption is the process of converting ciphertext back to plaintext.

A symmetric key is used during both the encryption and decryption processes. To decrypt a particular piece of ciphertext, the key that was used to encrypt the data must be used.

The goal of every encryption algorithm is to make it as difficult as possible to decrypt the generated ciphertext without using the key. If a really good encryption algorithm is used, there is no technique significantly better than methodically trying every possible key. For such an algorithm, the longer the key, the more difficult it is to decrypt a piece of ciphertext without possessing the key.

We will be discussing two ciphering algorithms here, namely Hill Cipher Algorithm and Rail Fence Cipher Algorithm.

Climbing the Hill Cipher Algorithm

Hill Cipher is a polygraphic substitution cipher based on linear algebra. Each letter is represented by a number modulo 26. Often the simple scheme A=0, B=1, …., Z=25 is used. Let us see the step-wise breakdown for encrypting a text using Hill Cipher:

1. To encrypt a message using the Hill Cipher, we must first turn our plaintext into a column vector.
2. We also turn our keyword (same for encryption and decryption) into an invertible nxn key matrix.
3. We then perform matrix multiplication modulo 26 (length of the alphabets) on each vector.
4. These vectors are then converted back into letters, based on the scheme used, to produce the ciphertext.

Considering an example would set the things straight for us. Let us take an example where:

We have to encrypt the message ‘ACT’ (length, n=3). The key is ‘GYBNQKURP’ which can be written as the nxn matrix:

Keyword written as the nxn matrix

Following is the pseudo code to generate the key matrix:

The message ‘ACT’ is written as vector:

Message written as the Column Vector

After performing matrix multiplication against modulo 26, the enciphered vector is given as:

The Final Vector obtained after performing all the operations

As you can see from the column vector obtained after performing said operations, the enciphered text received corresponds to ‘POH’.

Following is the pseudo code to perform matrix multiplication modulo 26:

To decrypt a ciphertext encoded using the Hill Cipher, the majority of process is same as the encryption. We turn the ciphertext back into a vector, then simply multiply by the inverse matrix of the key matrix (IFKVIVVMI in letters).The inverse of the matrix used in the previous example is:

Inverse of the Key Matrix

Performing the inverse key matrix multiplication for the ciphertext ‘POH’:

The original column vector obtained after decryption

The deciphered text corresponds to ‘ACT’, which is same as the original plaintext.

An important note: We should keep in mind that not every possible matrix is a possible key matrix. This is because, in order to decrypt, we need to have an inverse key matrix, and not every matrix is invertible. To determine it, see if the determinant is 0 or shares a factor other than 1, then the matrix will not have an inverse. If this is the case, a different key must be used, since otherwise the ciphertext will not be able to be decrypted.

A Github Repository link is attached at the end of the blog that contains the whole working code for encryption and decryption using Hill Cipher algorithm.

Tracking the Rail Fence Cipher Algorithm

The Rail Fence Cipher (also called a zigzag cipher) is a form of transposition cipher. It works by writing your message on alternate lines across the page, and then reading off each line in turn. Let us see the step-wise breakdown for encrypting a text using Rail Fence Cipher :

1. To encrypt a message using the Rail Fence Cipher, firstly we need to have a key (same for encryption and decryption), which is the number of rows you are going to have for this cipher.
2. We then start writing the letters of the given plaintext down diagonally to the right side until the number of rows specified by the key is reached.
3. We then bounce back up in a similar way diagonally till we hit the first row again. Thus, the alphabets of the plaintext are written in a zig-zag manner.
4. This cycle continues till the end of plaintext is reached. The individual rows are then read in order to obtain the ciphertext.

Considering an example would set the things straight for us. Let us take an example where: Plaintext is given as “defend the east wall” and number of rails (key)=3, then encryption process is as shown below:

The Rail Fence Cipher with a key of 3

Note that at the end of the message we have inserted two letter “X”s, which are called as nulls and act as placeholders. This is done to make sure that the message fits neatly in to the grid, so that there are same number of letters on the top row and the bottom row.

Following is the pseudo code for the encryption process:

Now reading the image row by row gives us the ciphertext as “DNETLEEDHESWLXFTAAX”.

Following is the pseudo code for reading the rail matrix row by row and forming the ciphertext:

To decrypt a ciphertext encoded using the Rail Fence Cipher, we have to reconstruct the diagonal grid used to encrypt the message. We start writing the message, but leaving a star in place of the spaces yet to be occupied (as shown in the figure below). Gradually, you can replace all the stars with the corresponding letters and read the plaintext from the table in a similar manner as encryption.

Placing stars in the place of spaces to be occupied

Let us see the step-wise breakdown:

1. We start by making a grid (rail matrix) with as many rows as the given key (number of rails) is, and as many columns as the length of the ciphertext.
2. We then place the first letter in the top left square and proceed diagonally downwards where the letters are present.
3. When we get back to the top row, we place the next letter in the ciphertext. We continue this process across the row, and start the next row when we reach the end.
4. We traverse the matrix in zig-zag manner to obtain the original plaintext.

Following is the pseudo code for constructing the rail matrix for decryption of the ciphertext:

Following is the pseudo code for filling the rail matrix and reading it in a zig-zag manner in order to obtain the plaintext:

An important note: The Rail Fence Cipher is a very easy to apply transposition cipher. However, it is not particularly secure, since there are a limited number of usable keys, especially for short messages (for there to be enough movement of letters, the length of the message needs to be preferably 3 times the key). You could easily process these quickly by the hand or a computer.

Resources

Following Github Repository can be referred for the whole working code of Encryption and Decryption using Hill Cipher Algorithm and Rail Fence Cipher Algoirthm: Link

References

1. Rail Fence Cipher — Encryption and Decryption
2. Hill Cipher