Cryptography Basics: Hill Cipher, Base Change and Caesar Cipher Encryption Explained with Python Implementation
Whether you’re a computer science student studying information security, an advanced mathematics students or a detective novel fanatic, cryptography is one domain which many of us find intriguing. So in this article, we will learn about some of these basic cryptography techniques, the mathematics involved and their implementation in Python.
Hill Cipher is a polygraphic substitution cipher based on linear algebra invented by Lester S. Hill in 1929. Although this ciphering method has lost its practicality in this technological era and easily succumb to plain text attacks, it is an important study topic for students studying cryptography basics or linear algebra.
Caesar Cipher or Shift Cipher, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.[Source: Wikipedia]
Base Change Cipher is a simple yet effective method to hide numerical data. In this method, we simply convert the numeric data in out text file (usually in decimal base (base 10) to any other base as per the user’s choice of base. This results in a new number, which is seems significant and correct but actually feeds the numeric data in a different base to attacker, who often mistake it as decimal system based data.
Hill cipher encryption works on simple linear algebra mathematics of matrix computation. For English alphabets, the character set consists of 26 characters but it is advisable to take a larger character set containing uppercase characters, lowercase characters, numbers, spaces and the commonly used special characters.
To encrypt a message, each block of N letters from the message(considered as an n-component vector) is multiplied by an invertible N× N matrix, against modulus L, where L denotes the length of character set containing all possible characters in the text. The matrix used for encryption is the cipher key, taken as input from the user of length N² formed into invertible N× N matrices (with values equal to the character’s index in the character set) which is modulo with L. To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption. The resultant integers are the indices of the original characters in the character set which are obtained and concatenated to form the original text. This ciphering based on linear algebra therefore finds application in modern encryption for data security
Consider the message ‘ACT’, and the key GYBNQKURP in letters.
The key matrix formed is:
Since ‘A’ is 0, ‘C’ is 2 and ‘T’ is 19, the message is the vector:
Now we can apply the following matrix operations to cipher the text :-
K x M = E’
E’ % L = E (Nx1 encryption vector)
Thus the enciphered vector is given by:
which corresponds to a ciphertext of ‘POH’ . The word “ACT” has now become “POH”.
Therefore, Hill cipher computes 3 characters at a time for a 3x3 key matrix( key length 9). To generalize this, we can say that Hill Cipher computes N characters at a time for N x N key matrix (key length N²).
Caesar cipher is one of the simplest yet widely used encryption techniques. It is a substitution cipher in which all the characters are shifted by an integer N to obtain a new string with the shifted characters, earning this algorithm the name of Shift cipher. Encryption of a letter x by a shift N can be described mathematically as
EN ( x ) = ( x + N ) % 26
Decryption is performed similarly using :-
DN ( x ) = ( x — N ) % 26
Here, 26 is taken for English alphabet length. Alternatively, for any other character set, modulus with L can be taken where L is the length of the character set.
EN ( x ) = ( x + N ) % L
DN ( x ) = ( x — N ) % L
Caesar cipher work on 1 character at a time and is very easy to decode, both manually and computationally.
Base Change Cipher
By converting the number from decimal base to any other natural base (except 1), the numerical representation is changed and a new numerical representation is obtained which enables one to safeguard the original numerical data such, especially account details, phone numbers etc. For decryption, the number from the known changed base is simply converted into a decimal number system. Both encryption and decryption is carried out by standard number system conversion method, by dividing and taking mod of the number NUM to new base N to obtain the new base changed number.
Python allows base conversion using inbuilt functions which you can use during implementation.[Refer : GeeksForGeeks]
The original algorithm is for converting base is same as we use in decimal to binary conversion. Keep dividing the number NUM by the new base N and store the remainders till the number is reduced to 0.
Finally, popping the stack will give the new number changed to base N. For implementation in all languages refer GeeksForGeeks.
For implementation of these ciphers in python you can refer my Github repository. It also facilitates multiple encryption using an indigenous algorithm which can increase the strength of the cipher.
Hope this article helps get you an insight on these basic cryptography techniques. For any queries and suggestion, contact me at my LinkedIn.