Hill Cipher

                                           Hill cipher encryption-decryption.

PSEUDOCODE

Encryption

To encrypt a message using the Hill Cipher we must first turn our keyword into a key matrix (a 2 x 2 matrix for working with digraphs, a 3 x 3 matrix for working with trigraphs, etc). We also turn the plaintext into digraphs (or trigraphs) and each of these into a column vector. We then perform matrix multiplication modulo the length of the alphabet (i.e. 26) on each vector. These vectors are then converted back into letters to produce the ciphertext.

Step 1:  We shall encrypt the plaintext message "short example" using the keyword hill and a 2 x 2 matrix. The first step is to turn the keyword into a matrix. If the keyword was longer than the 4 letters needed, we would only take the first 4 letters, and if it was shorter, we would fill it up with the alphabet in order (much like a Mixed Alphabet).

The keyword written as a matrix.

Step 2: With the keyword in a matrix, we need to convert this into a key matrix. We do this by converting each letter into a number by its position in the alphabet (starting at 0). So, A = 0, B = 1, C= 2, D = 3, etc.

The key matrix (each letter of the keyword is converted to a number).

Step3:  We now split the plaintext into digraphs, and write these as column vectors. That is, in the first column vector we write the first plaintext letter at the top, and the second letter at the bottom. Then we move to the next column vector, where the third plaintext letter goes at the top, and the fourth at the bottom. This continues for the whole plaintext.

Step4: Now we must convert the plaintext column vectors in the same way that we converted the keyword into the key matrix. Each letter is replaced by its appropriate number.

Step5: Now we must perform some matrix multiplication. We multiply the key matrix by each column vector in turn. We shall go through the first of these in detail, then the rest shall be presented in less detail. We write the key matrix first, followed by the column vector.

Step6: Next we have to take each of these numbers, in our resultant column vector, modulo 26 (remember that means divide by 26 and take the remainder)

Step7: Finally we have to convert these numbers back to letters, so 0 becomes "A" and 15 becomes "P", and our first two letters of the ciphertext are "AP".

Decryption

To decrypt a ciphertext encoded using the Hill Cipher, we must find the inverse matrix. Once we have the inverse matrix, the process is the same as encrypting. That is we multiply the inverse key matrix by the column vectors that the ciphertext is split into, take the results modulo the length of the alphabet, and finally convert the numbers back to letters.

Since the majority of the process is the same as encryption, we are going ot focus on finding the inverse key matrix (not an easy task), and will then skim quickly through the other steps (for more information see Encryption above).

In general, to find the inverse of the key matrix, we perform the calculation below, where K is the key matrix, d is the determinant of the key matrix and adj(K) is the adjugate matrix of K.

Step 1: Find the Multiplicative Inverse of Matrix The determinant is a number that relates directly to the entries of the matrix. It is found by multiplying the top left number by the bottom right number and subtracting from this the product of the top right number and the bottom left number. This is shown algebraically below. 

We now have to find the multiplicative inverse of the determinant working modulo 26. That is, the number between 1 and 25 that gives an answer of 1 when we multiply it by the determinant. So, in this case, we are looking for the number that we need to multiply 15 by to get an answer of 1 modulo 26. There are algorithms to calculate this, but it is often easiest to use trial and error to find the inverse.

So the multiplicative inverse of the determinant modulo 26 is 7. We shall need this number later.

Step 2 - Find the Adjugate Matrix

The adjugate matrix is a matrix of the same size as the original. For a 2 x 2 matrix, this is fairly straightforward as it is just moving the elements to different positions and changing a couple of signs. That is, we swap the top left and bottom right numbers in the key matrix, and change the sign of the the top right and bottom left numbers. 

Step 3 - Multiply the Multiplicative Inverse of the Determinant by the Adjugate Matrix

Step 6: Find the Plaintext by multiplying the key^-1 with Ciphertext

C Program

#include<stdio.h>

#include<string.h>

void main()

{

int i,j,key[5][5],ikey[5][5],row,col,plen,suc;

int devide,count,h,k,no,p1[100],e1[100],d1[100],m,pp[10],temp;

char p[100],e[100],d[100],clen,det;

printf("Enter your plaintext::::::::");

gets(p);

plen=strlen(p);

printf("\n HOW MANY SUCCESSIVE ELMENTS YOU WILL TAKE IN PLAINTEXT??");

scanf("%d",&suc);

row=suc;

col=suc;

printf("\n ENTER ELEMENTS OF KEY MATRIX (row by row)::::");

for(i=0;i<row;i++)

for(j=0;j<col;j++)

scanf("%d",&key[i][j]);

/*for(i=0;i<row;i++)

{printf("\n");

for(j=0;j<col;j++)

printf(" %d ",key[i][j]);

}

*/

devide=(plen+1)/suc;

count=0;

no=0;

for(h=0;h<devide;h++)

{

  for(i=0;i<suc;i++)

  { if(p[count]!='\0')

    {p1[i]=p[count]-97;

    count++;

    }

  }

  for(i=0;i<suc;i++)

  {   e1[no]=0;

      for(k=0;k<suc;k++)

      {e1[no]=e1[no]+(key[i][k]*p1[k]);

      }

      no++;

  }

}

printf("\n PLAIN TEXT::::::::::::::::::::::::::::");

puts(p);

printf("\n ENCRYPTED TEXT::::::::::::::::::::::::");

for(i=0;i<plen;i++)

{e[i]=(e1[i]%26)+97;

printf("%c",e[i]);

}

//decryption part;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

clen=strlen(e);

devide=(clen+1)/suc;

//start decryption:::::::::::::

printf("\n ENter inverse matrix values");

for(i=0;i<suc;i++)

for(j=0;j<suc;j++)

{scanf("%d",&ikey[i][j]);

}

count=0;

no=0;

for(h=0;h<devide;h++)

{

  for(i=0;i<suc;i++)

  { if(e[count]!='\0')

    {p1[i]=e[count]-97;

    count++;

    //printf("p %c",p1[i]);

    }

  }

  for(i=0;i<suc;i++)

  {   d1[no]=0;

      for(k=0;k<suc;k++)

      {d1[no]=d1[no]+(ikey[i][k]*p1[k]);

      }

      no++;

  }

}

printf("\n DECRYPTED TEXT::::::::::::::::::::::::");

for(i=0;i<plen;i++)

{d[i]=(d1[i]%26)+97;

printf("%c",d[i]);

}

}

VIVA Questions:

1.      Solve the above question completely.

2.      Encrypt the plaintext message "retreat now" using the keyphrase back up and a 3 x 3 matrix.

3.      We shall decrypt the example above, so we are using the keyword hill and our ciphertext is "APADJ TFTWLFJ" now decrypt it.

4.      Encrypt the message “Good morning” using the Hill Cipher with the key “hell” and 2x2 matrix.

5.      Write a short note on “Hill Cipher”.