Encryption & Decryption using Hill & Rail Fence Algorithm
So many things in the world would have never come into existence if there hadn’t been a problem that needed solving. This truth applies to everything, but boy, is it obvious in the world of computer science.
So, its a big “YES”, but I do think that it’s unique in one way: computer science’s innovations rely and build upon its own abstractions.
But what leads to the need of Ciphering & Deciphering algorithms ??
Have you ever wondered how companies securely store your passwords? Or how your credit card information is kept private when making online purchases?
The answer is cryptography. The vast majority of internet sites now use some form of cryptography to ensure the privacy of its users. Even information such as emails from your Gmail account are encrypted as they float around in Google’s data centers.
What is Cryptography ?
Cryptography is a method of protecting information and communications through the use of codes, so that only those for whom the information is intended can read and process it.
In cryptography, Encryption is the process of translating plain text data, usually called plain text into something that appears to be random and meaningless, usually called cipher text. Decryption is the process of converting cipher text back to plain text.
So, to decrypt the ciphered text, you need to have the same key that was used during encryption.
Here, we will be discussing about two such algorithms
1) Hill Cipher Algorithm
2) Rail Fence Algorithm
To make our message strongly encrypted, we will encode our message twice, first encode it using Hill Cipher, and then pass it through rail fence cipher algorithm.
If this is your very first foray into cyber security, fear not — it’s mine, too!
Let’s tackle it together — and try not to lose our sanity in the process.
Mounting 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’s see it step-wise:
Step 1: Convert your message or “plain text” into a column vector & your key into a n*n matrix.
Step 2: Perform matrix multiplication of (Key Matrix * Message Vector) modulo 26 and store it in a string.
now we will pass this ciphered text as an input to the rail fence cipher algorithm.
Trailing over the Rail Fence Cipher Algorithm
The rail fence cipher (also called a zigzag cipher) is a form of transposition cipher. It derives its name from the way in which it is encoded.
- In the rail fence cipher, the plain-text is written downwards and diagonally on successive rails of an imaginary fence.
- When we reach the bottom rail, we traverse upwards moving diagonally, after reaching the top rail, the direction is changed again. Thus the alphabets of the message are written in a zig-zag manner.
- After each alphabet has been written, the individual rows are combined to obtain the cipher-text.
Step 1: Take an integer key as an input and create a matrix with:
number of rows = key
number of columns = size of message (text that is to be encrypted)
Store the message in this matrix in a zig-zag manner.
An important note: keep in mind to take the value of key less than the size of message, otherwise the encoded string will be same as input string.
Step 2 : Traverse the matrix in row wise manner and if the element is not equal to “ * “, then store it in a string.
This string is the encoded string after rail fence encoding. Now it is send to the receiver, and he has to decode it.
First decrypt using Rail Fence Decipher algorithm, then Hill Decipher algorithm.
Tracing back through Rail Fence Decipher Algorithm
As we’ve seen earlier, the number of columns in rail fence cipher remains equal to the length of plain-text message. And the key corresponds to the number of rails.
- Hence, rail matrix can be constructed accordingly. Once we’ve got the matrix we can figure-out the spots where texts should be placed (using the same way of moving diagonally up and down alternatively ).
- Then, we fill the cipher-text row wise. After filling it, we traverse the matrix in zig-zag manner to obtain the original text.
Step 1 : First create a character array, similar to, that we have created in its ciphering algorithm. Then store “ * ” in zig-zag manner in this matrix.
Step 2 : Now traverse this matrix row wise, and if element == “ * “ replace it with input string [index++]. After this process, again traverse this matrix in zig-zag manner and store the elements in a string.
This string is the decoded string after Rail Decipher algorithm, now pass it to Hill Decipher algorithm to get our original message.
Moving downhill through Hill Decipher Algorithm
The process of decrypting it is almost similar to its encryption process. Difference being, we turn the cipher text back into a vector, then simply multiply by the inverse matrix of the key matrix.
Step 1 : We will have to use the same key, that we used in the Hill Ciphering algorithm (actually that’s the main security advantage, that prevent it from going under the wrong hands). Create a key matrix, and calculate its inverse.
InverseMatrix( ) can be accessed from the GitHub link, I have mentioned at the end of this blog.
Step 2 : Perform matrix multiplication of (Inverse of key Matrix * Input string) modulo 26 and store the final vector in a string.
An important note: Since, inverse of every matrix is not possible, so keep in mind to choose the key such that its matrix do not have the determinant as zero. Otherwise its decryption won’t be possible.
This string is the final decoded string after Hill Decipher algorithm and it should be same as our original string.
Output window
Ciphering process :
Here our original message is “ ACT ” and its key is “ GYBNQKURP ” , It is passed through Hill Cipher Algorithm and we get encoded output as “ POH “.
Now “POH” is passed as an input to Rail Fence Cipher algorithm with key = 2, and we get the encoded output as “ PHO “.
Deciphering process :
Pass “ PHO “ as an input to Rail Fence Decipher algorithm with same key = 2 and the output we get is “ POH “. Now it is used as an input in Hill Decipher algorithm with key = “ GYBNQKURP “ and the final decrypted output we get is “ ACT “, which is same as the input message.
Resources
You can access the whole working code of both Encryption and Decryption using Hill Cipher algorithm & Rail Fence Cipher algorithm from this GitHub Repository : Link
