Hill Cipher in Java [Encryption and Decryption]

Here you will learn about hill cipher in java with program and algorithm.

To start with the program directly is not a good idea here. Until you don’t have a brief understanding of Hill cipher algorithm, their programs will merely a code to copy paste.

As per Wikipedia, Hill cipher is a polygraphic substitution cipher based on linear algebra, invented by Lester S. Hill in 1929. Basically Hill cipher is a cryptography algorithm to encrypt and decrypt data to ensure data security.

Also Read: Caesar Cipher in Java

Also Read: Java Vigenere Cipher

Hill cipher uses the calculations of matrices used in Linear Algebra but it’s simple to understand if one has the basic knowledge of matrix multiplication, modulo calculation and inverse calculation of matrices.

In this example we are going to take up a 2X2 matrix for better understanding and simplification. The same method can be applied to 3X3 matrix to get the desired results.

Encryption

So the first thing we have to do in encrypting the data using hill cipher is to take up a string of characters as key matrix to encrypt data and convert this key matrix to number matrix.

For this context we will be using the string –“mble” (this is just any random combination of letters) and on converting this string to a number matrix following the rule of numbering alphabets from 0 to 25 (i.e. A=0, B=1…), we get our key matrix as:

hill chipher in java 1

We will try to encrypt “helloworld” here.

For this purpose we will need to convert this plain text into diagraphs. For this purpose we will write this from the starting of our first column vector having first letter at the top and second letter at the bottom and after this jumping on to the second column vector having third letter at the top and fourth letter at the bottom and so on.

hill cipher in java 2

If there were any left places then we can put any wild character at that place say ‘x’.

Next step is to convert these column vectors into their corresponding number codes.

hill cipher in java 3

Now we need to multiple each column vector from the key matrix and obtain the result. The result after multiplication is shown down here:

hill cipher in java 4

After this, as all the numbers are greater than 26 so we need to divide these column vectors with 26 and note the remainder i.e. calculate mod26 of these vectors.

So the resultant vector becomes:

hill cipher in java 5

And now let’s convert these numbers back to letters, following the old rule, so our column vector becomes:

hill cipher in java 6

This gives us the encoded text as – “KPNJIIDOFD”

The same process can be repeated for 3X3 matrix to encrypt the data.

Decryption

To decrypt the data using the Hill Cipher, first we need to find the inverse of our key matrix.

To do this first find the determinant of our key matrix. In our case determinant evaluates to 37, which is again greater than 26 so we will find mod26 of out determinant i.e., 37 = 11 mod 26

The next step is to find a number which gives the answer 1 when mod26 is found after multiplying that number by the modulo of our determinant. This can be done with the help of hit and trial method.

Applying this, we get 11 x 19 = 1 mod 26 and now we need to find the adjoint of our matrix and convert the negative numbers into positive numbers by finding mod26:

hill chiper in java 7

Next step is to multiply this adjoint with the number we found above (19) and find mod26 to keep the range under 26. On doing this, we get

hill cipher in java 8

 

“KPNJIIDOFD” was our encoded string, and now we have to repeat the steps of encryption to decrypt this string. So first we will write this string in column vectors, and next convert this column vectors into corresponding number and multiply it with the inverse of key matrix we found above and find mod26 then.

After that we need to transfer these numbers back to letters to get our actual string. One is done here.

hill cipher in java 9

Now comes the program to have this algorithm implemented.

Hill Cipher Program in Java

import java.util.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class HillCipherExample {
	
	int[] lm;
    int[][] km;    
    int[] rm;
    static int choice;
    int [][] invK;
    
    public void performDivision(String temp, int s)
    {
        while (temp.length() > s)
        {
            String line = temp.substring(0, s);
            temp = temp.substring(s, temp.length());
            calLineMatrix(line);
            if(choice ==1){
                multiplyLineByKey(line.length());
            }else{
                multiplyLineByInvKey(line.length());
            }
            showResult(line.length());
        }
        if (temp.length() == s){
            
            if(choice ==1){
            calLineMatrix(temp);
            multiplyLineByKey(temp.length());
            showResult(temp.length());
            }
            else{
                calLineMatrix(temp);
                this.multiplyLineByInvKey(temp.length());
                showResult(temp.length());
            }
        }
        else if (temp.length() < s)
        {
            for (int i = temp.length(); i < s; i++)
                temp = temp + 'x';
            if(choice ==1){
            calLineMatrix(temp);
            multiplyLineByKey(temp.length());
            showResult(temp.length());
            }
            else{
                calLineMatrix(temp);
                multiplyLineByInvKey(temp.length());
                showResult(temp.length());
            }
        }
    }
 
 
    public void calKeyMatrix(String key, int len)
    {
        km = new int[len][len];
        int k = 0;
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < len; j++)
            {
                km[i][j] = ((int) key.charAt(k)) - 97;
                k++;
            }
        }
    }
 
    public void calLineMatrix(String line)
    {
        lm = new int[line.length()];
        for (int i = 0; i < line.length(); i++)
        {
            lm[i] = ((int) line.charAt(i)) - 97;
        }
    }
 
    public void multiplyLineByKey(int len)
    {
        rm = new int[len];
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < len; j++)
            {
                rm[i] += km[i][j] * lm[j];
            }
            rm[i] %= 26;
        }
    }
    public void multiplyLineByInvKey(int len)
    {
        
        rm = new int[len];
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < len; j++)
            {
                rm[i] += invK[i][j] * lm[j];
            }
            rm[i] %= 26;
        }
    }
    
 
    public void showResult(int len)
    {
        String result = "";
        for (int i = 0; i < len; i++)
        {
            result += (char) (rm[i] + 97);
        }
        System.out.print(result);
    }
 
   
 
    public int calDeterminant(int A[][], int N)
    {
        int resultOfDet;
        switch (N) {
            case 1:
                resultOfDet = A[0][0];
                break;
            case 2:
                resultOfDet = A[0][0] * A[1][1] - A[1][0] * A[0][1];
                break;
            default:
                resultOfDet = 0;
                for (int j1 = 0; j1 < N; j1++)
                {
                    int m[][] = new int[N - 1][N - 1];
                    for (int i = 1; i < N; i++)
                    {
                        int j2 = 0;
                        for (int j = 0; j < N; j++)
                        {
                            if (j == j1)
                                continue;
                            m[i - 1][j2] = A[i][j];
                            j2++;
                        }
                    }
                    resultOfDet += Math.pow(-1.0, 1.0 + j1 + 1.0) * A[0][j1]
                            * calDeterminant(m, N - 1);
                }   break;
        }
        return resultOfDet;
    }
 
    public void cofact(int num[][], int f)
    {
        int b[][], fac[][];
        b = new int[f][f];
        fac = new int[f][f];
        int p, q, m, n, i, j;
        for (q = 0; q < f; q++)
        {
            for (p = 0; p < f; p++)
            {
                m = 0;
                n = 0;
                for (i = 0; i < f; i++)
                {
                    for (j = 0; j < f; j++)
                    {
                        b[i][j] = 0;
                        if (i != q && j != p)
                        {
                            b[m][n] = num[i][j];
                            if (n < (f - 2))
                                n++;
                            else
                            {
                                n = 0;
                                m++;
                            }
                        }
                    }
                }
                fac[q][p] = (int) Math.pow(-1, q + p) * calDeterminant(b, f - 1);
            }
        }
        trans(fac, f);
    }
 
    void trans(int fac[][], int r)
    {
        int i, j;
        int b[][], inv[][];
        b = new int[r][r];
        inv = new int[r][r];
        int d = calDeterminant(km, r);
        int mi = mi(d % 26);
        mi %= 26;
        if (mi < 0)
            mi += 26;
        for (i = 0; i < r; i++)
        {
            for (j = 0; j < r; j++)
            {
                b[i][j] = fac[j][i];
            }
        }
        for (i = 0; i < r; i++)
        {
            for (j = 0; j < r; j++)
            {
                inv[i][j] = b[i][j] % 26;
                if (inv[i][j] < 0)
                    inv[i][j] += 26;
                inv[i][j] *= mi;
                inv[i][j] %= 26;
            }
        }
        //System.out.println("\nInverse key:");
        //matrixtoinvkey(inv, r);
        
        invK = inv;
    }
 
    public int mi(int d)
    {
        int q, r1, r2, r, t1, t2, t;
        r1 = 26;
        r2 = d;
        t1 = 0;
        t2 = 1;
        while (r1 != 1 && r2 != 0)
        {
            q = r1 / r2;
            r = r1 % r2;
            t = t1 - (t2 * q);
            r1 = r2;
            r2 = r;
            t1 = t2;
            t2 = t;
        }
        return (t1 + t2);
    }
 
    public void matrixtoinvkey(int inv[][], int n)
    {
        String invkey = "";
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                invkey += (char) (inv[i][j] + 97);
            }
        }
        System.out.print(invkey);
    }
     public boolean check(String key, int len)
    {
        calKeyMatrix(key, len);
        int d = calDeterminant(km, len);
        d = d % 26;
        if (d == 0)
        {
            System.out.println("Key is not invertible");
            return false;
        }
        else if (d % 2 == 0 || d % 13 == 0)
        {
            System.out.println("Key is not invertible");
            return false;
        }
        else
        {
            return true;
        }
    }
 
    public static void main(String args[]) throws IOException
    {
        HillCipherExample obj = new HillCipherExample();
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Menu:\n1: Encryption\n2: Decryption");
        choice = Integer.parseInt(in.readLine());
        System.out.println("Enter the line: ");
        String line = in.readLine();
        System.out.println("Enter the key: ");
        String key = in.readLine();
        double sq = Math.sqrt(key.length());
        if (sq != (long) sq)
            System.out.println("Cannot Form a square matrix");
        else
        {
            int size = (int) sq;
            if (obj.check(key, size))
            {
                
                System.out.println("Result:");
                obj.cofact(obj.km, size);
                obj.performDivision(line, size);
                
                
            }
        }
    }
}

Output

Menu:
1: Encryption
2: Decryption
1
Enter the line:
helloworld
Enter the key:
mble
Result:
kpnjiidofd

Menu:
1: Encryption
2: Decryption
2
Enter the line:
kpnjiidofd
Enter the key:
mble
Result:
helloworld

Reference: https://www.sanfoundry.com/java-program-implement-hill-cypher/

Comment below if you have queries regarding hill cipher in java.

1 thought on “Hill Cipher in Java [Encryption and Decryption]”

Leave a Comment

Your email address will not be published. Required fields are marked *