AIM:
To develop a program to encrypt and decrypt using the Hill cipher substitution technique
PRELAB DISCUSSION:
The Hill cipher is a substitution cipher invented by Lester S. Hill in 1929. Hill's major
contribution was the use of mathematics to design and analyse cryptosystems. The Hill cipher is a
polygraphic substitution cipher based on linear algebra. Hill ciphers are applications of linear algebra
because a Hill cipher is simply a linear transformation represented by a matrix with respect to the
standard basis. Groups of letters are represented by vectors. The domain of the linear transformation
is all plaintext vectors, while the codomain is made up of all ciphertext vectors. Matrix multiplication
is involved in the encoding and decoding process. And when trying to find the inverse key, we will
use elementary row operations to row reduce the key matrix in order to find its inverse in the standard
manner. Each letter is represented by a number modulo 26. To encrypt a message, each block of n
letters is multiplied by an invertible n × n matrix, again modulus 26.To decrypt the message, each
block is multiplied by the inverse of the matrix used for encryption. The matrix used for encryption is
the cipher key, and it should be chosen randomly from the set of invertible n × n matrices (modulo
26).The cipher can, be adapted to an alphabet with any number of letters. All arithmetic just needs to
be done modulo the number of letters instead of modulo 26.
Encryption : Cipher text = ( Plain text * Key ) mod 26
Decryption : Plain text = ( Cipher text * Key-1
) mod 26
ALGORITHM:
1. Get the n-by-n key matrix with vectors of length n.
2. Separate the plaintext from left to right into some number k of groups of n letters each. If you
run out of letters when forming the final group, repeat the last plaintext letter or ‘X’ as many
times as needed to fill out the final group of n letters.
3. Replace each letter by the corresponding number of its position (from 0 through m-1) in the
alphabet to get k groups of n integers each.
4. Encryption:
a. Reshape each of the k groups of integers into an n-row column vector called Plain text
matrix
b. Cipher Text Matrix = ( Plain Text Matrix * Key Matrix ) mod 26.
c. Using step 4.b, perform matrix multiplication of Plain text matrix and Key matrix and
modulus 26 to yield Cipher text matrix.
d. Translate the Cipher text matrix to string representation by replacing each of the
entries with the corresponding letter of the alphabet, after arranging all k of the
resulting column vectors in order into a single vector of length k x n
5. Decryption:
a. Find the inverse of the key matrix
i. Find the determinant of the key matrix
26
ii. Transpose the key matrix
iii. Find minor matrix and then Cofactor of the key matrix
iv. Key-1
= [ [ Det(key matrix) ]
-1
* Cofactor ] mod 26 using modulus
arithmetic
b. Plain Text = ( Cipher Text * Key-1
) mod 26
c. Using step 5.b, perform matrix multiplication of Cipher text matrix and Key inverse
matrix and modulus 26 to yield Plain text matrix.
d. Translate the Plain text matrix to string representation by replacing each of the entries
with the corresponding letter of the alphabet, after arranging all k of the resulting
column vectors and removing any letters padded in order into a single vector of length
k x n
6. Stop
PROGRAM:
import java.util.*;
public class Hillcipher
{
public int keyinverse[][] = new int[3][3];
public int key[][] = { {17, 17, 5}, {21, 18, 21}, {2, 2, 19} };
public int plainmat[][] = new int[8][3];
public int ciphermat[][] = new int[8][3];
public String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
String plain,cipher;
int row, flag=0, decrypt=0;
public void matdisplay(int mat[][])
{
int i, j;
for(i=0;i<row;i++)
{
for(j=0;j<3;j++)
System.out.print(mat[i][j] + " ");
System.out.println();
}
}
public void keydisplay(int mat[][])
{
int i, j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
System.out.print(mat[i][j] + " ");
System.out.println();
}
}
public void inverse()
{
int dtrmnt = 0;
int mulinvdtrmnt = 0;
int x, y, z, i, j, a, tmp, p, q;
int transkey[][] = new int[3][3];
int minormat[][] = new int[3][3];
int temp[][] = new int[2][2];
System.out.println("HILL CIPHER KEY");
keydisplay(key);
x = key[0][0] * (( key[1][1] * key[2][2]) - (key[1][2] * key[2][1]));
y = key[0][1] * (( key[1][0] * key[2][2]) - (key[1][2] * key[2][0]));
z = key[0][2] * (( key[1][0] * key[2][1]) - (key[1][1] * key[2][0]));
dtrmnt = (x-y+z)%26;
if ( dtrmnt < 0 )
dtrmnt = dtrmnt + 26;
System.out.println("DETERMINANT :" + dtrmnt);
a = dtrmnt;
for(i=0;i<25;i++)
{
tmp = ( a * i ) % 26;
if ( tmp == 1 )
{
mulinvdtrmnt = i;
break;
}
}
System.out.println("MULTIPLICATIVE INVERSE OF DETERMINANT:" +
mulinvdtrmnt);
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
transkey[i][j] = key[j][i];
}
// keydisplay(transkey);
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
p=0;
q=0;
for(x=0;x<3;x++)
{
for(y=0;y<3;y++)
{
if ((x!=i) && (y!=j))
{
temp[p][q] = transkey[x][y];
q++;
if ( q == 2)
{
q=0;
p++;
}
}
}
}
minormat[i][j]=(temp[0][0]*temp[1][1])-(temp[0][1]*temp[1][0]);
minormat[i][j] = minormat[i][j] * (int)Math.pow(-1,(i+j));
}
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
keyinverse[i][j]=(mulinvdtrmnt * minormat[i][j])%26;
if (keyinverse[i][j] < 0)
keyinverse[i][j] = keyinverse[i][j] + 26;
}
}
System.out.println("KEY INVERSE");
keydisplay(keyinverse);
}
public void str2matrix(String text)
{
int k, p, n;
if ((text.length() % 3) == 1)
{
n=text.length();
text += 'X';
text += 'X';
flag = 2;
}
if ((text.length() % 3) == 2)
{
text += 'X';
flag = 1;
}
row = (text.length()) / 3;
k = 0;
for(int i=0; i<row; i++)
{
for(int j=0;j<3;j++)
{
for (p=0;p<26;p++)
{
if (text.charAt(k) == ALPHABET.charAt(p))
{
plainmat[i][j] = p;
k++;
break;
}
}
}
}
// System.out.println("PLAIN TEXT MATRIX");
matdisplay(plainmat);
System.out.println();
}
public String matrix2str(int mat[][])
{
int i, j, k;
String txt="";
String tmp="";
for(i=0;i<row;i++)
{
for(j=0;j<3;j++)
{
k = mat[i][j];
txt += ALPHABET.charAt(k);
}
}
if (decrypt == 1)
{
if ( flag == 1 )
{
tmp = txt.substring(0, (txt.length()-1));
return tmp;
}
if ( flag == 2 )
{
tmp = txt.substring(0, (txt.length()-2));
return tmp;
}
}
return txt;
}
public String hcencryption(String ptxt)
{
int i,j,k;
int sum=0;
String ctxt="";
decrypt=0;
System.out.println("HILL CIPHER ENCRYPTION");
System.out.println("PLAIN TEXT MATRIX");
str2matrix(ptxt);
for(i=0;i<row;i++)
{
for(j=0;j<3;j++)
{
for(k=0;k<3;k++)
sum += plainmat[i][k] * key[k][j];
ciphermat[i][j] = sum % 26;
sum = 0;
}
}
System.out.println("CIPHER TEXT MATRIX");
matdisplay(ciphermat);
ctxt = matrix2str(ciphermat);
return ctxt;
}
public String hcdecryption(String ctxt)
{
int i,j,k;
int sum=0;
String ptxt="";
decrypt=1;
System.out.println("HILL CIPHER DECRYPTION");
System.out.println("CIPHER TEXT MATRIX");
str2matrix(ctxt);
for(i=0;i<row;i++)
{
for(j=0;j<3;j++)
{
for(k=0;k<3;k++)
sum += ciphermat[i][k] * keyinverse[k][j];
plainmat[i][j] = sum % 26;
sum = 0;
}
}
System.out.println("PLAIN TEXT MATRIX");
matdisplay(plainmat);
ptxt = matrix2str(plainmat);
return ptxt;
}
public static void main(String[] args)
{
Hillcipher hc = new Hillcipher();
Scanner sc = new Scanner(System.in);
hc.inverse();
String ptext = new String();
System.out.println("Enter PLAIN TEXT");
ptext = sc.next();
String ctext = new String();
ctext = hc.hcencryption(ptext);
System.out.println();
System.out.println("CIPHER TEXT :" + ctext);
System.out.println();
String plaintext = new String();
plaintext = hc.hcdecryption(ctext);
System.out.println();
System.out.println("PLAIN TEXT :" + plaintext);
sc.close();
}
}
OUTPUT:
C:\Program Files\Java\jdk1.8.0_71\bin>javac Hillcipher.java
C:\Program Files\Java\jdk1.8.0_71\bin>java Hillcipher
HILL CIPHER KEY
17 17 5
21 18 21
2 2 19
DETERMINANT : 23
MULTIPLICATIVE INVERSE OF DETERMINANT : 17
KEY INVERSE
4 9 15
15 17 6
24 0 17
Enter PLAIN TEXT
PAYMOREMONEY
HILL CIPHER ENCRYPTION
PLAIN TEXT MATRIX
15 0 24
12 14 17
4 12 14
13 4 24
32
CIPHER TEXT MATRIX
17 17 11
12 22 1
10 0 18
15 3 7
CIPHER TEXT :RRLMWBKASPDH
HILL CIPHER DECRYPTION
CIPHER TEXT MATRIX
17 17 11
12 22 1
10 0 18
15 3 7
PLAIN TEXT MATRIX
15 0 24
12 14 17
4 12 14
13 4 24
PLAIN TEXT :PAYMOREMONEY
C:\Program Files\Java\jdk1.8.0_71\bin>javac Hillcipher.java
C:\Program Files\Java\jdk1.8.0_71\bin>java Hillcipher
HILL CIPHER KEY
17 17 5
21 18 21
2 2 19
DETERMINANT :23
MULTIPLICATIVE INVERSE OF DETERMINANT:17
KEY INVERSE
4 9 15
15 17 6
24 0 17
Enter PLAIN TEXT
TECHNOLOGY
HILL CIPHER ENCRYPTION
PLAIN TEXT MATRIX
19 4 2
7 13 14
11 14 6
24 23 23
33
CIPHER TEXT MATRIX
21 9 9
4 17 2
25 9 21
1 10 0
CIPHER TEXT :VJJERCZJVBKA
HILL CIPHER DECRYPTION
CIPHER TEXT MATRIX
21 9 9
4 17 2
25 9 21
1 10 0
PLAIN TEXT MATRIX
19 4 2
7 13 14
11 14 6
24 23 23
PLAIN TEXT :TECHNOLOGY
VIVA QUESTIONS (PRELAB and POSTLAB):
1. Name the aspects to be considered of information security.
2. What is meant by deciphering?
3. What are the two different uses of public key cryptography related to key distribution?
4. How many bit keys are used in S-DES algorithm?
5. What are the parameters are include the certificate request message?
6. What is S/MIME?
7. What is the purpose of dual signature?
8. What are the two common techniques used to protect a password file?
9. What is the size of the key for substitution block cipher?
10. Define Stream Cipher.
RESULT:
Thus the program to implement Hill cipher encryption technique was developed and executed
successfully
https://t.me/questionbankss
ReplyDeleteBest study group in the world
https://t.me/questionbankss
ReplyDeletePost a Comment