Objectives

• Implement the Hill cipher in Java using arrays
• Implement a matrix-vector multiplication, which is a part of the Hill cipher algorithm

Setup

First, create a lab04 directory:

$ cd cs190m
$ mkdir lab04
$ cd lab04

Then, download Lab04.java into the folder you just created.

The Hill Cipher

The Hill cipher is a cipher invented in 1929 which uses matrix multiplication to encrypt a message. From here on out, we'll assume that we're only using lowercase letters, spaces, periods, and commas for everything, to simplify things a bit. Given a message of length N, you must have a key that is of size NxN to use in the Hill cipher. For example, if you wanted to encrypt the word "arc", we would need a 9-letter key, such as "foobarbaz," to encrypt it. However, we need to transform the key into a matrix in order to use it. Our matrix will simply be a N x N sized matrix. For example, "foobarbaz" becomes something like this:

Of course, since we know that we'll be using this matrix for multiplication, we can't just leave it like that. We have to convert the letters to numbers. Since we're restricted to lowercase letters, the best way to do this is to have a=0, b=1, c=2 ... z=25 space=26, period=27, comma=28. If we use this transformation, the key matrix becomes:

This same numeric transformation must be applied to the text that we want to encrypt. In our example, "arc" becomes a vector (or a 3 x 1 matrix, if you will):

Once you've transformed the key and text into matrices, encryption using the Hill cipher is easy. Simply multiply the key matrix by the text vector and take the result modulo 29:

Note: Modulo, or simply "mod," is related to division. However, a modulo operation returns the remainder, rather than the quotient. For example, 5 divided by 3 is 1 (in integer arithmetic), but 5 modulo 3 is 2. In Java, this is simply written as 5 % 3, where the percent sign is the modulo operator.

Decryption is a similar process. Instead of multiplying the key matrix and the plain text, instead you must multiply the inverse of the key matrix with the encrypted text, or ciphertext. We won't be going into the math behind inverting the matrix (the key is "aoq.geasl"), but the decryption is:

In general, the encryption is simply:

Where A is the encryption matrix, x is the message, and b is the encrypted message. Decryption works because multiply b by the inverse of A is essentially cancelling the A out:

Exercise: Implement the Hill Cipher

We'll be implementing the Hill cipher within several methods, which are explained below.

TODO 1: Multiply

The multiply method simply performs a matrix-vector multiplication. We know that the matrix is of size N x N (the example uses a 3 x 3 matrix) and the vector is of size N as well. This means that the result will also be a vector of size N. To calculate what the result in each row will be, you should do the following:

1. For each current row, multiply the ith column by the ith row in the rotated vector
2. Add the results of all of the multiplications together. The result of the addition modulo 29 is the number that belongs in the current row in the solution vector.

TODO 2: stringToArray

This method converts a string to an integer array. Obviously, the integer array will be the same length as the string; For the ith character in the String, simply convert it using the charToNumber method and store it in the ith location of the array.

TODO 3: arrayToString

This method reverses the effects of stringToArray. You should be able to figure out this method based on what you did in the previous method.

TODO 4: transform

The transform method is the method that handles the transformation of a message. Since encryption and decryption are the same (matrix multiplication), there is no real need to have a separate method for encryption and decryption. The transform method serves to split up a string into blocks of size N (remember, N is the size of the matrix dimension). For each block of the original text, it should call:

1. Convert the block into an integer array by using stringToArray.
2. Multiply the matrix by the integer array by calling multiply.
3. Convert the result into a String by calling arrayToString.
4. Add the String you just created to the result variable.

TODO 5: keyToMatrix

The keyToMatrix method is similar to the stringToArray method that you should have programmed by now. However, instead of returning a 1-D array, you are creating the key matrix, which means it should be a 2-D array. The conversion for each character is the same as in stringToArray, but instead of converting a String of length 9 to an integer array of length 9, you're now converting it to a 2-D array of size 3 x 3.

Testing Your Lab

You'll notice that your skeleton code came with a main file. Simply compile and run it, and it will try a given set of keys along with a plain text. The expected output is in the comments for you to see.

Turning In Your Lab

To turn in your lab:

$ cd ~/cs190m/lab04
$ turnin -v -c cs190m -p lab04 *.java

Getting Help

Many of you will probably run across problems while programming at some point during a lab. If that's the case, here are the resources you should use, in order:

1. Your textbook
2. Lecture notes
3. Java API documentation
4. Your lab TA

Lab created by: Daniel Tang