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!!

Comments

Post a Comment

Popular posts from this blog

Playfair Cipher program in c

Image
  Introduction to Playfair The Playfair cipher or Playfair square or Wheatstone-Playfair cipher is a manual symmetric encryption technique( Use same key for encryption of plaintext and decryption of ciphertext) and was the first literal digram substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but bears the name of Lord Playfair for promoting its use.  This technique encrypts pairs of letters (bigrams or digrams), instead of single letters as in the simple substitution cipher and rather more complex cipher systems then in use. History of playfair It was however later used for tactical purposes by British forces in the Second Boer War and in World War I and for the same purpose by the British and Australians during World War II. This was because Playfair is reasonably fast to use and requires no special equipment - just a pencil and some paper. A typical scenario for Playfair use was to protect important but non-critical s...
Read more