To my main page
To my projects page
The applet at the bottom of this page uses the notion of a Hill cipher of dimension n to encrypt and decrypt a message.
To encrypt more than just lower case letters, change the lower bound to 32, which in ascii represents a space. After that change the encryption array to whatever you want and then press the button with the ">>" on it. This will cause the decryption array to be calculated. If an error dialog appears, the encryption matrix does not have an appropriate inverse. Just try some other numbers. You can also start with a decryption matrix, press the "<<" button, and have the encryption matrix calculated.
Once you have the appropriate matrices, type in the message you want to encrypt under plaintext and press encrypt. The encrypted ciphertext appears on the right. You can go backwards as well. Type in the encrypted cipher text and press the decrypt button to see what the original message was.
You can also use the "crack" button to type in a message and its encrypted form to find out what the encryption and decryption arrays are. If an error comes up saying the message was not long enough then there were not enough characters in the text within the specified bounds. There should be at least (CipherSize*CipherSize) letters. If there's an error saying that the data is not linearly independent, the program cannot find the arrays because the text is in an arrangement such that parts of the text do not provide new information and are mathematically equivalent to the combinations of other parts of the text (I'm sorry, I don't know if that makes any sense, but I can't think of another way to explain what linear independence is in terms of text). Please note that finding the right combination of texts is not very easy. Please feel free to experiment with all of the variables as well.
The applet takes a two dimensional encryption or decryption matrix with "Cipher Size" rows and "Cipher Size" columns. The two matrices are just inverses of each other modulo some modulus and one can be calculated from the other one using the ">>" and "<<" buttons. The matrices have all of their math performed modulo a modulus. The specific modulus is equal to the upper bound ascii value minus the lower bound ascii value plus one (i.e. the modulus is the number of different ascii characters that can be encoded). The lower and upper bounds are the smallest and largest ascii characters that will be recognized by the program. They must be between the numbers 0 and 126, although if the lower bound is below 32, the resulting text may be incorrect. Also note that the upper bound must be at least one number higher than the lower bound. Any ascii characters outside of the specified bounds will be discarded before any encryption/decryption occurs. The "First Value" is the integer that the lowest recognizable ascii character will receive. All the other ascii characters will receive values that are incremented by one, modulo the appropriate modulus.
For encryption, all of the ascii characters in the plain text are converted to appropriate integers. These integers are then divided into vectors of size "Cipher Size". The encryption matrix is multiplied by each vector and the resulting vectors are turned back into a string that serves as the cipher text. Decryption is just the reverse of encryption. The decryption matrix is multiplied by the vectors from the cipher text and the result is turned into the plain text.
A person can also determine the original matrices from the plain text
and the cipher text. This can be performed by pressing the "Crack"
button. The ability to crack the cipher is based upon the idea that
given plaintext converted into vectors p1,p2,etc. and ciphertext
converted into vectors c1,c2,etc. so that P and C be defined such
that
P = [transpose(p1)] C = [transpose(c1)]
[transpose(p2)] [transpose(c2)]
{... ] {... }
then the augmented matrix [C | P] can be reduced by elementary row
operations to [I | transpose(decryption_matrix)].
An augmented matrix is reduced to [I | whatever] row by row. The basic idea is to go through each column starting from the left and finding the first row that can have a 1 in that column. That row is then swapped with whatever row has the same index as the column being examined. All the other rows are then manipulated so that they have a 0 entry in that column. This procedure is repeated for every column until the left side of the augmented matrix is an identity matrix or until the program determines that the left side cannot become an identity matrix.
The inverse of the matrices modulo some modulus is found in
exactly the same fashion. The determinant modulo m for the matrices
is found by reducing the specified matrix to row reduced echelon form
and then having the diagonal entries multiplied together and then
multiplied by the appropriate constant. Since all the entries in
the matrices are integers the program must be able to find an inverse
of a number modulo some modulus to have 1's in the right place in
the identity matrix. The inverse exists only if gcd(modulus,number)=1.
The remainder of the discussion assumes that gcd(modulus,number)=1.
The inverse can be found by keeping track of the values used in the
Euclidean algorithm for the greatest common divisor and then working
backwards. The Euclidean algorithm generates the following equations
(where the original number is r[1], and the modulus is r[0]:
r[0]=r[1]*k[1]+r[2] and r[2]=r[0] mod r[1]
r[1]=r[2]*k[2]+r[3] and r[3]=r[1] mod r[2]
...
r[n-3]=r[n-2]*k[n-2]+r[n-1] and r[n]=r[n-2] mod r[n-1]
r[n-2]=r[n-1]*k[n-1]+1 and 1=r[n-2] mod r[n-1] (note r[n]=1)
r[n-1]=1*k[n]+0
The value of n is at most 2(1+ceil(ln(modulus)/ln(2)))
and is usually less than that.
The function that satisfies the equation f[i]*r[i]=1 mod r[i-1]
for i between 1 and n is defined as:
f[i]=
if i=n then f[i]=1
else if i=n-1 then f[i]=-k[i]
else f[i]=f[i+2]-f[i+1]*k[i] (for i between 1 and n-2)
f[1] is the inverse of the originally specifed number modulo the
initial modulus, since f[1]*r[1]=1 mod r[0] which is just
f[1]*number=1 mod modulus.
That pretty much covers all of the math in the applet. And now, after all of this text, here's the applet.
This web page is maintained by Borys
Bradel. Last update: Sep. 24, 2001
Address:
http://www.eecg.utoronto.ca/~bradel/projects/cryptography/index.html