Cryptography
Hill-ciphers
an application of Linear Algebra
by: Paal Schiefloe
3 December 2001
[top]
This project for my Linear Algebra class is about cryptography. I will discuss a simple method of enciphering and deciphering a message using matrix transformations and modular arithmetic, and show how elementary row operations can sometimes be used to break an opponent's code.
The ciphers I will discuss are called Hill ciphers after Lester S. Hill who introduced them in two papers: "Cryptography in an Algebraic Alphabet," American Mathematical Monthly, 36, June-July 1929, pp. 306-312; and "Concerning Certain Linear Transformation Apparatus of Cryptography," American Mathematical Monthly, 38, March 1931, pp. 135-154.
I will show an example of how a message is enciphered and deciphered using Hill ciphers, I will also briefly discuss how to break a Hill cipher using elementary row operations by giving an example from "Elementary Linear Algebra, Applications version, edition 6".
[top]
Cryptography has for long been an important issue in the realm of computers. It was mainly used for the security needed for passwords but now cryptography is very important due to the Internet's flow of sensitive information such as credit card information and other sensitive information which is fairly easy to monitor by unintended third hand parties.
The idea behind enciphering a message is to make it worthless to everyone except for the party with the deciphering "key".
[top]
For Hill ciphers I assign numerical values to each plaintext and ciphertext letter so that A=1, B=2, C=2 and so on. If I wanted to I could have assigned numerical values for all the other characters on a keyboard, but for simplicity I will only assign numerical values to the letters in the alphabet in this project.
The following procedure shows the simplest Hill ciphers (Hill 2-cipher), successive pairs of plaintext that are transformed into ciphertext by a 2 x 2 matrix A.
NOTE: I will impose an additional condition on matrix A later. Here I have assigned numerical values to the alphabet:
Choose a 2 x 2 matrix A with integer entries to perform the encoding.
(The matrix has to be invertible modulo m, but I will discuss this later)
Group successive plaintext letters into pairs. If we end up with one single letter at the end, simply add an arbitrary "dummy" letter to fill out the last pair of letters.
Enciphering Step 3.
Convert each plaintext pair p1p2 into a column vector p.
Then form the plaintext matrix P of all our plaintext column vectors.
To encipher the message we multiply our plaintext matrix P by our transformation matrix A to form the product AP.
The product of our matrix multiplication is the ciphertext matrix C.
Enciphering Step 4.
Now we convert each ciphertext vector into its alphabetical equivalent and write out our enciphered message.
This was the encoding procedure, pretty simple, huh:) Let's see how we decipher our enciphered message.
Deciphering Step 1. Now we group the successive ciphertext letters into pairs and convert each ciphertext pair c1c2 into a column vector c. Then form the ciphertext matrix C of all our ciphertext column vectors.
Deciphering Step 2.
Multiply the ciphertext matrix C with the inverse of our enciphering matrix A to obtain the deciphered message. Not too difficult, huh:)
NOTE: To use this procedure we have to understand the concept of modular arithmetic. In the 6 steps I showed you above, I chose not to include the modular arithmetic in the steps for simplicity. However, modular arithmetic is important for this procedure to work. Keep reading and I'll show you why this is so important:)
[top]
We have the transformation matrix A
When we multiply this vector by our transformation matrix A, we get the enciphered column vector
Uh...hmmm, what letters correspond to the integers 148 and 64? This is where Modular Arithmetic comes in handy.
Our alphabet is given by non negative integers from 1, 2, , ..., m, where m is the length of our alphabet (in this case m = 26).
What we do when we have over 26, is simply "wrapping around" the numbers from 27 to 52 to represent the 26 letters again, then we do the same thing from 53 to 78 etc. We can do the same with negative integers (in this case Z=0, Y=-1, X=-2 etc.).
The procedure of "wrapping" is quite general. It is the same procedure we use every noon and midnight when we begin again to number the hours 1, 2, etc. In a 24 hour system, 18:00 is the same as 6:00 (pm) and 13:00 is 1:00 (pm).
How we do this mathematically is as follows: When we have integers greater than 26, we replace it by the remainder that results when this integer is divided by 26. So if we have the number 148 from the example above, we divide 148 by 26 and the remainder is 18.
148 - (5 * 26) = 18
Here are a couple examples for some different modulus:
7 = 2 (mod 5) because the remainder is 2 after dividing 7 by 5
19 = 3 (mod 2) because the remainder is 3 after dividing 19 by 2
-1 = 25 (mod 26) because the remainder is 25 after dividing -1 by 26
The formal definitions:
If m is a positive integer and a and b are any integers, then we say that a is equivalent to b modulo m, written
a = b (mod m)
if a-b is an integer multiple of m.
Now to the most important part of the concept of Modular Arithmetic for Hill ciphers. As mentioned in the procedure for enciphering and deciphering plaintext using a simple Hill-cipher above, we have to impose an additional condition for our transformation matrix A:
The transformation matrix A must be invertible modulo m for this procedure to work.
So when finding the inverse of our transformation matrix A we have to take (mod m) into consideration.
However, since this project is about Linear Algebra, I chose to skip the details about the modular arithmetic here, and provide a table of the reciprocols of modulo 26 instead. The inmportant thing is to keep in mind when checking our transformation matrix to see if it is invertile it ha to be invertible modulo m, you see how this is done in the example provided below the table of reciprocals modulo 26:.
[top]
Let's say we want to encipher the following sentence,"THE PROFESSOR IS EVIL", into ciphertext.
The first thing we do is to group the letters into pairs of 2 letters. If we would do a Hill 3-cipher, we would group the letters in groups of 3 letters and use a 3 x 3 transformation matrix, but in this example we're using a Hill 2-cipher.
For a Hill n-cipher, use n x n transformation matrix.
So, I have grouped the letters like this:
This leads us to step 3 of the procedure, convert each pair into a column to form the plaintext matrix P.
Oooops, most of these numbers in E are over 26, but by using the trick we learned from modular arithmetic we easily convert into nicer numbers, remember this is in modulo 26.
Then we assign letters to the numerical values by using our table and this is what we get:
RLQFXCHAAQAFCWAXMB
Yeah, we enciphered the message, let's hope the professor can't break it. I'll show you later how Hill-ciphers can be broken by using row reduction.
All right, time to decipher the messages.
Let's imagine we just received this message from one of our classmates, we know the matrix A he/she used to encipher the message with, so what do we do?
Now we work backwards, once again grouping the ciphertext into pairs of 2 letters and assigning numerical values for the letters. We make each pair into a column vector in a matrix E.
Then we simply multiply the matrix E by the inverse of A, but we have to remember our modular arithmetic from the example above.
"THE PROFESSOR IS EVIL"
Nice, we just deciphered the message.
[top]
If we are able to obtain a small amount of corresponding plaintext and ciphertext from a secret message, it is possible to determine the deciphering matrix A and then again decipher the entire message. We have learned in class that a linear transformation is determined by its values at a basis. This means that if we have a Hill n-cipher, and if
p1, p2, ... , pn
are linear independent plaintext vectors whose corresponding ciphertext vectors
Ap1, Ap2, ..., Apn
are known, then we have enough information to determine the matrix A and later A-1 (mod m).
To illustrate this I found an example from "Elementary Linear Algebra, Applications version, edition 6".
Let's say that we obtain an enciphered message and we are able to deduce that it is a letter starting with "DEAR". With a small amount of such data it may be possible to determine the deciphering matrix of a Hill-cipher and consequently get access to the rest of the message.
...Bibliography/References... [top]
Howard Anton and Christ Rorres. Elementary Linear Algebra Application Version. 6th edition. John Wiley & Sons, INC.
Eisenberg, Murray. Hill Ciphers and Modular Linear Algebra. 3 Nov 1999 (accessed 26 November - 2 December 2001) <http://www.math.umass.edu/~murray/Hillciph.pdf>
Goulet, John. Project #6 Cryptography. (accessed 26 November - 2 December 2001) <http://www.prenhall.com/divisions/esm/app/ph-linear/kolman/html/proj6.html>
More:
Cryptography - University of Washington
