Hill Cipher program in c

 

 Introduction to Hill Cipher

In classical cryptography, the Hill cipher is a polygraphic substitution cipher based on linear algebra. Invented by Lester S. Hill in 1929, it was the first polygraphic cipher in which it was practical (though barely) to operate on more than three symbols at once. The following discussion assumes an elementary knowledge of matrices.

This technique encrypt plaintext in matrix form of 2x2 or 3x3.when plaintext in 2x2 then key value also in 2x2 matrix and 3x3 use then 3x3 matrix key.Using matrix we can encrypt 4 or 9 plaintext letters at once.

Hill Cipher Theory

First of all need key in matrix form of 2x2 or 3x3 depends of requirement.

Here, we have formula to find Cipher text  (Encryption)

CT = K*PT mod 26

 Where, CT = CipherText ,

              K = Key ,

              PT = PlainText.

We have also formula to find Plain text from Cipher text (Decryption)

PT = K^-1*CT mod 26

 Where, CT = CipherText ,

              K^-1 = Inverse of key ,

              PT = PlainText.

Example: 

Plain text is "computer" and Key is in matrix 4 9 3 7. Apply Encryption and Decryption using Hill Cipher 2x2 matrix.

First perform Encryption:

In this we made 4-4 part of letters  because we use 2x2 matrix.
Also convert plain text using below format,
 a,b,c,d,........,x,y,z ==> 0,1,2,3,......,23,24,25. 

Here over plain text is "computer" ==> "2 14 12 15 20 19 4 17"

In first part "comp" is encrypted for this "2 14 12 15"

Answer of CT is "12 9 12 17" convert it into letters "mjmr".

second part of text is "uter" ==>"20 19 4 17" using formula cipher text is "12 21 10 20" convert into letters "mvku".

"computer" ==>"mjmrmvku" is our cipher text.

Decryption:

We perform inverse process of encryption.
First 4-4 parts of cipher text and find value of it like...
"mjmr mvku" ==>"12 9 12 17   12 21 10 20"

Use first 4 for decryption see in below image

In this find inverse of key and multiple matrix with first 4 cipher text letters.
(how to find inverse and multiplication click here)

 You can see in picture we get the plain text from cipher text.

Now we see Hill Cipher Program in c

First we see variable information:

  int key[2][2]={'\0'},p[50]={'\0'};  
  char pt[50]={'\0'};  
  int len=0,n=0,i=0,j=0,m=0;  
  clrscr();  

Key is 2x2 matrix use for get key value from user.
Pt is character array that is use for store plain text.
p in this array store plain text numeric value (a,b,c...==>0,1,2...) .

Get Plaintext and key from user: 

 printf("\n Enter PlainText:");  
  gets(pt);  
  printf("\n Enter key:");  
  for(i=0;i<2;i++)  
  {  
   for(j=0;j<2;j++)  
   scanf("%d",&key[i][j]);  
  }  

using gets() we get plain text and use for loop for get value of key.

Add Filler

In this part we add filler to our plain text for better out put.

why need filler?
Filler is use when 4 equal parts is not possible like..
In "hello" part is "hell" and "o" that time our program's first part is run completely but in second part we have only one letter there for error is occur or program miss behave.

Therefore we use filler 'x' in program "hello" ==> "hell oxxx".

 len=strlen(pt);  
  if(len % 4 == 1)  
  {  
   n=3;  
  }else if(len % 4 == 2)  
  {  
  n=2;  
  }else if(len % 4 == 3)  
  {  
  n=1;  
  }else  
  {  
  n=0;  
  }  
  if(n != 0)  
  {  
  for(i=0;i<n;i++)  
  {  
   pt[len]='x';  
   len++;  
  }  
  }  
  printf("\n new plaintext:");  
  puts(pt);  
  n=0;  
  printf("\n Your Key is:");  
  printf("\n");  
  for(i=0;i<2;i++)  
  {  
    for(j=0;j<2;j++)  
    {  
    printf("\t %d \t",key[i][j]);  
    }  
    printf("\n \n");  
  }  

Output of this:

Store plain text numeric value:

  for(i=0;i<strlen(pt);i++)  
  {  
   p[m]=pt[i]-97;  
   m++;  
  }  

here substitute 97 from each letter it will give numeric value of letters and store in array p.

Send values to function: 

 hill(p,m,key);  

here send array p in this all numeric value of plaintext that is use in encryption,
m it is index of p (in c language difficult to find length of integer array)
key it is most important for encryption and decryption.

Function of Hill Cipher:

 void hill(int [50],int ,int [2][2]);  

First add this function deceleration above of main function.

 Variables use in function:

  int i=0,sum=0,j=0,k=0,n=0,count=0,ic=0;  
  int ipt[2][2]={'\0'},cy[2][2]={'\0'},c[50]={'\0'};  
  char fcy[50]={'\0'},fpt[50]={'\0'};  
  float ikey[2][2]={'\0'},det=0,psum=0,pt[2][2]={'\0'};  
  int tpt[2][2]={'\0'};  

ipt is store 4 value of plain text that is use in matrix multiplication.
cy is cipher text value before of mod with 26.
fcy is final array of cipher text.
ikey in this store inverse of key.
pt is store value before of mod with 26.

Encryption:

 for(n=0;n<m;n++)  
  {  
   for(i=0;i<2;i++)  
   {  
   for(j=0;j<2;j++)  
   {  
    ipt[i][j]=p[count];  
    count++;  
   }  
   }  
  for(i=0;i<2;i++)  
  {  
  for(j=0;j<2;j++)  
  {  
  sum=0;  
   for(k=0;k<2;k++)  
   {  
    sum=sum+key[i][k]*ipt[k][j];  
   }  
   cy[i][j]=sum;  
  }  
  }  
  printf("\n cipher text is:");  
  sum=0;  
  for(i=0;i<2;i++)  
  {  
  for(j=0;j<2;j++)  
  {  
   fcy[sum]=(cy[i][j]%26)+97;  
   c[ic]=cy[i][j]%26;  
   ic++;  
   printf("%c \t",fcy[sum]);  
   sum++;  
  }  
  }  
  n=n+3;  
  printf("\n");  
  }  

In above code first for loop use for length of plaintext using index 'm'.
Below Two for loop is use for 4-4 partition and store in ipt.

then do matrix multiplication for 2x2 matrix and store in cy array.

fcy[sum]=(cy[i][j]%26)+97; //also present in above image

this is use for mod with 26 and add 97 for get cipher text.

c[ic]=cy[i][j]%26; //also present in above image

And this store numeric value of cipher text that is use for Decryption.

Decryption:

  count=0;  
  for(n=0;n<m;n++)  
  {  
   for(i=0;i<2;i++)  
   {  
   for(j=0;j<2;j++)  
   {  
    ipt[i][j]=c[count];  
    count++;  
   }  
   }  
  det=((key[0][0]*key[1][1])-(key[0][1]*key[1][0]));  
  if(det !=0)  
  {  
  for(i=0;i<2;i++)  
  {  
  for(j=0;j<2;j++)  
  {  
   if(i==0 && j==0)  
   {  
   ikey[i][j]=key[1][1];  
   }  
   if(i==1 && j==1)  
   {  
   ikey[i][j]=key[0][0];  
   }  
   if(i != j)  
   {  
   ikey[i][j]=-key[i][j];  
   }  
  }  
  }  
  for(i=0;i<2;i++)  
  {  
  for(j=0;j<2;j++)  
  {  
  psum=0;  
   for(k=0;k<2;k++)  
   {  
    psum=psum+ikey[i][k]*ipt[k][j];  
   }  
   pt[i][j]=psum;  
   while(pt[i][j] < 0)  
   {  
   pt[i][j]=pt[i][j]+26;  
   }  
   tpt[i][j]=pt[i][j];  
  }  
  }  
  printf("\n plain text is:");  
  psum=0;  
  for(i=0;i<2;i++)  
  {  
  for(j=0;j<2;j++)  
  {  
   fpt[psum]=(tpt[i][j]%26)+97;  
   printf("%c \t",fpt[psum]);  
   psum++;  
  }  
  }  
 }  
 else  
 printf("\n Invers not possible!!!...try with diff value of key..");  
 n=n+3;  
 printf("\n");  
 }  

All process same as encryption.like do 4-4 partition.

then find determinate  of array and check it is 0 or not.Whenever det=0 then decryption is not possible because inverse is infinite.

then find inverse.here use simple if statements for better understand.
Matrix multiplication with cipher text's numeric value and inverse of key.

pt[i][j]=psum;  
   while(pt[i][j] < 0)  
   {  
   pt[i][j]=pt[i][j]+26;  
   }  
   tpt[i][j]=pt[i][j];  //also present in above image

In this for loop store value of multiplication,but our value is also in negative therefore add value 26 till positive value not occur and store in temporary integer array 'tpt' .
why use while loop?
This while loop is for only negative value of pt because in next step we have to mod with 26.
We know that mod of negative is add value of 26 whenever positive value is not occur.

like -10 mod 256 is equal to -10+256=246.It is value of negative mod.
-275 mod 250 then -275+250 = - 25.still negative then add one more time -25+250=225.then -275 mod 250=225. 

fpt[psum]=(tpt[i][j]%26)+97;  //also present in above image

in this step we store final plain text value.here add 97 into mod value.

Output of Full Program:

 

Use Download button for Code

Thank You!!