CioheWednesday, April 13, 2016

University of Botswana

ISS 334 LAB 2 ASSIGNMENT
Ndlovu.I 200902852
Ndlovu.I

ISS 334 Lab 2 Assignment

Page 1 of 27

Wednesday, April 13, 2016

Contents
1.

Hill Cipher Description .......................................................................................................................... 3

2.

Question ................................................................................................................................................ 3

3.

Implementation .................................................................................................................................... 3
3.1.

Hill Cipher Encryption and Decryption.......................................................................................... 4

3.1.1.

Part 1 ..................................................................................................................................... 5

3.1.2.

Part 2 ..................................................................................................................................... 7

3.1.3.

Part 3 ..................................................................................................................................... 9

3.1.4.

Part 4 ................................................................................................................................... 11

3.1.5.

Part 5 ................................................................................................................................... 12

3.2.

Known plain text attack using simultaneous linear equations ................................................... 14

3.2.1.

Part 1 ................................................................................................................................... 15

3.2.2.

Part 2 ................................................................................................................................... 16

3.2.3.

Part 3 ................................................................................................................................... 18

3.3.

Known plain text attack using matrix multiplication .................................................................. 19

3.3.1.

Part 1 ................................................................................................................................... 20

3.3.2.

Part 2 ................................................................................................................................... 22

3.3.3.

Part 3 ................................................................................................................................... 24

3.3.4.

Part 4 ................................................................................................................................... 25

3.3.5.

Part 5 ................................................................................................................................... 25

3.4.

Ndlovu.I

Known plain text attack using matrix reduction ......................................................................... 26

ISS 334 Lab 2 Assignment

Page 2 of 27

Wednesday, April 13, 2016

1. Hill Cipher Description
The hill cipher is a polygraphic substitution cipher based on linear algebra modular mathematics. It also uses matrices and matrix multiplication to form a ciphertext from a plain text and vice versa. It was invented by Lester S. Hill in 1929.

2. Question
Write a program that reads two strings - ciphertext and the partial plaintext and finds the key matrix and the complete plaintext using the known plaintext cryptanalysis technique that we learned in class.

3. Implementation
The approach used to answer has 3 steps.
Step 1 is a program that is used to encrypt and decrypt a message using the Hill Cipher.
Step 2 is a program that uses the “known plain text attack” to find the key which was used to encrypt the message; this is achieved by using simultaneous linear equations.
Step 3 is the same as Step 2 but using a different matrix multiplication to find the key. All the programs have written in java using Dr. Java.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 3 of 27

Wednesday, April 13, 2016

3.1. Hill Cipher Encryption and Decryption

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 4 of 27

Wednesday, April 13, 2016

3.1.1. Part 1
Class Basic the class has the indexOfChar and indexAtChar method.
The first method matches characters of a string to the alphabet and returns a numeric value, the second method is used to return a char which is located at the position int pos.
Class Hill has an object basic of the class basic so as to access the methods from the basic class, this is done later on in the program.
Class Hill also contains method Hill, this ensures that the matrix we are using is a 2X2 matrix, that’s why the variable block=2.
The method reads the key matrix. The user will enter in the first number and press “enter” and do this until the fourth number is entered. The assumption is that we are using a 2x2 matrix as the key size.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 5 of 27

Wednesday, April 13, 2016

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 6 of 27

Wednesday, April 13, 2016

3.1.2. Part 2
The method KeyInverse also reads 4 integers which are stored to the double array Key[][] and uses them for the decryption key.
The method encryptBlock is the encryption method.
Plain.toUpperCase converts the text that is read to upper text.
The CipherMatrix stores the encrypted values of the plain text.
A for loop is used to iterate through the entered in plain text such that the method indexOfChar that converts a character to a numerical value occurs for each character of the plaintext. This is so that the matrix CipherMatrix is filled with intergers not cahracters, also note that CipherMatrix[][] is a double array variable.
Then follows a series of the for loops which are used for the most important part of the encryption, that’s the matrix multiplication. This is where the 2x2 key is multiplied by the 2x2 plain text matrix. The result is stored to the ciphertext matrix. The loops are executed in the order of the inner loop first then then middle loop then the outer loop last. This ensures that the cipher text matrix is filled in sequential order. Also note that the in the inner for loop [0][0] of the key is multiplied by row [0][0] of the plain text but [0][1] of the key is multiplied by [1][0] of the plain text matrix, this is done so that the mathematical rules of matrix mutilation are followed, also note that sum variable adds the sum of two [0][0]x[0][0] +
[0][1]X[1][0] of the key and plaint text matrices respectively.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 7 of 27

Wednesday, April 13, 2016

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 8 of 27

Wednesday, April 13, 2016

3.1.3. Part 3
The charAtIndex is the method which was mentioned in part 1 that is used to convert the cipher numerical values to text, this is after the matrix multiplication has taken place.
Therefore the return cipher returns a string as the result of the encryptBlock method.
Then follows the string encrypt method

The string ciphertext is initialized to an empty string
Method keyInsert receives the input for the plain text
While(len%block!=0) this is used to ensures that the plaintext is an even number as the matrix of a 2x2 two matrix is an even number
Plaintext+=”X” adds a character to the plaintext if it’s length is an odd number
The for loop is used to fill the string ciphertext with the values of plaintext that have been encrypted using the encryptBlock method.
The ciphertext is returned as the result of the encrypt method
The decryptBlock method takes takes in the ciphertext and changes all the characters to upper case.
Then a[][] and plainMatix [][] arrays are created to be used in part 4
String plain is initialized to an empty string

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 9 of 27

Wednesday, April 13, 2016

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 10 of 27

Wednesday, April 13, 2016

3.1.4. Part 4
Since this is the decryptBlock method, the a[][] array is filled with the ciphertext characters using a single for loop
Then matrix multiplication occurs to multiply the inverse key[][] by a[][] which is the array of ciphertext which has just been filled
Three is done using a nested for loop of three. The procedure is similar to when performing a matrix multiplication when encrypting mentioned in part 2.
In this case plainMatrix is populated with the numerical values that correspond to the plaintext.
The following single for loop converts the integers (the numerical values) to characters using the charAtIndex method which was created and defined in part 1.
The plaintext is returned.
The string decrypt method is the one which actuallys takes in the user input of the ciphertext to be deciphered, ciphertext is defined as an input parameter within the braces of the decrypt() method.
The length of the ciphertext entered in is determined and converted o uppercase. The method then continues to part 5.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 11 of 27

Wednesday, April 13, 2016

3.1.5.

Part 5

The decryptBlock is called which actually does the calculation of matrix multiplication using the inverse and cipherext just entered in the assigns the deciphered text to plaintext.
Plaintext is returned as the result.
Public class HillCipher contains the main method, the method responsible for running the entire program. Basically here the user is prompted with entering the plaintext which is then read to the scanner. Note the same scanner is used for reading all inputs.
The user is then prompted to enter the matrix size, which is expected to be a 2 the program is written to calculate a 2x2 matrix.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 12 of 27

Wednesday, April 13, 2016
The encrypt method is called from the Hill class and plaintext is converted to ciphertext.
The ouput is printed to the screen.
The decrypt method is called from the Hill class so that decryption is performed and the decrypted text is printed to the screen.
And the main method is closed followed by the HillCipher class being closed.
End of program.

Above are quick values the user can input into the program to test if It’s working.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 13 of 27

Wednesday, April 13, 2016

3.2. Known plain text attack using simultaneous linear equations

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 14 of 27

Wednesday, April 13, 2016

3.2.1. Part 1
The method solveForUnknown is the method used to find the value of a, b,c, d which is unkown in an equation. The comments I put in help to show how the equations would have looked on paper.
Step 1 is cross multiplication so as to get rid of a common varaible and be left to figure out the remaing variable. Step 2 is the subtraction of the equations so that we remain with one equation.

The multiplicative inverse is found using the getInverse methd which is explained in 3.3.4
The last part of the equation is multiping the constant by the multiliplicative inverse because when this is done on the other side of the equation, the unkown variable becomes a 1.
Hence we find the variable that we were looking for an return it.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 15 of 27

Wednesday, April 13, 2016

3.2.2. Part 2
The getA, getB, getC and getD methods all work similarly. They just manipulate the linear equations by inputting different values for the coefficients so as to work out the different values of the unknown variables. The get method takes in the two arrays P[] and C[] which are plaintext and ciphertext respectively.
The solveForUnkown method is called which takes in the 6 coefficients to make up two linear equations each consisting of 3 coefficients. The value of the desired unknown variable is the returned.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 16 of 27

Wednesday, April 13, 2016

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 17 of 27

Wednesday, April 13, 2016

3.2.3. Part 3
The string allCHar takes in the 26 characters of the alphabet.
The inner for loop iterates through each character of the alphabet to match it to plaintext or ciphertext.
The for loop loops from the first character of the text to the last.
In the main method the user is asked to enter In plaintext which is then read and also asked to enter in ciphertext which is read.
The matrices of the cipher and plaintext are printed to the screen in the form of matrices containing integers so that the user has a graphical representation of how the matrices look.
The get methods are called for eeach variable, a,b,c and d.
The key matrix that is found is then printed to the screen.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 18 of 27

Wednesday, April 13, 2016

3.3. Known plain text attack using matrix multiplication

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 19 of 27

Wednesday, April 13, 2016

3.3.1. Part 1
The readInput method uses the scanner to read the line of string that is keyed in.
This is then converted to uppercase.
A two dimensional array is created read[][]. And the alphabet is created.
The function of the four separate for loops is to convert keyed in string to integers.
The main method begins by reading user input of the plaintext and ciphertext. Then the readInput method is called, which is explained above.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 20 of 27

Wednesday, April 13, 2016

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 21 of 27

Wednesday, April 13, 2016

3.3.2. Part 2
Step 2 finds the determinant of the plaintext P[] using the ad-bc formula.
The getInverse method is called which is to be explained in 3.3.4
The adjudicate is formed using the method {d,-b,-c,a} in the matrix.
The inverse of the plaintext P_i[][] is found by multiplying the inverse of the determninant into each matric quadrant of the adjudicate matrix Pa[].
The multiply matrix is called which takes in the paramneters inverse of plaintext matrix to be multiplied by the ciphertext matrix. The method is explained in 3.3.5
A for loop is used to print out the plaintext matrix to the user so they see how it looks.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 22 of 27

Wednesday, April 13, 2016

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 23 of 27

Wednesday, April 13, 2016

3.3.3. Part 3
A for loop is used to print out the ciphertext matrix also to the user so they see how it looks. As well as the determiniant, inverse matrix, adjudicate matrix which were all used to calculate the key matrix.
Finally the key matrix is printed out to the user.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 24 of 27

Wednesday, April 13, 2016

3.3.4. Part 4
The mod26 method which starts at the bottom of 3.3.3 is used to calculate mod, this is done as simply using %26 in java has the possibility of returning a – negative, but since we are using the alphabet, we want our results to be between positive 1 to 26.
The getInverse method uses the switch statement to create a table of all the multiplicative inverses available in modular 26. If a match is found then the answer is returned else an error message will be printed to the screen notifying the user that a multiplicative inverse cannot be found.
In the case that the user has an alternative pair of 2 plaintext characters that match 2 ciphertext characters, these can be used in place of the pair that causes an error.
The multiply method is explained in the following part 3.3.5

3.3.5. Part 5
The multiply method takes in the parameters of the matrices that it is to multiply. That is the inverse of the plaintext by the ciphertext.
The rows and column sizes of the matrices are declared, to be used in the subsequent for loops.
The first for loops initializes that K [][] array which will hold the values of the key matrix.

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 25 of 27

Wednesday, April 13, 2016
After that follows the nested for loop of three. Working inwards out. The inner for loop executes twice then breaks out to the middle for loop then the inner for loop executes twice again then finally breaks out to the outer for loop and executes… this happens until it has executed a total number of 8 times since this is a 2x2 matrix where the results of multiplication are grouped in 2’s where they summed so as to form four results which fill the four quadrant matrix of the key.

3.4. Known plain text attack using matrix reduction
This method I have only explored mathematically and have not implemented on java. Here is an example of it using question 3 from ISS 334 test 2.

Continue to next page…

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 26 of 27

Wednesday, April 13, 2016

Ndlovu.I

ISS 334 Lab 2 Assignment

Page 27 of 27