MA301, Hill Cipher Example and Some Useful Commands
Lisa Oberbroeckling, Spring 2011
Contents
NOTE: m-files don't view well in Internet Explorer. Use Mozilla Firefox or Safari instead to view these pages.
You should always have the following commands at the top to "start fresh"
clc % clears the command window clear % clears ALL variables format % resets the format to the default format
Introduction to some commands
In computers, ASCII codes represent text. For the upper-case English alphabet, the codes are from 65-90. Thus the ASCII code for A is 65 and the ASCII code for Z is 90. You can look up ASCII codes for other text and symbols but these are the only ones we're using for this project. We are going to use the following commands to convert between letters and numbers. There are also some useful commands to convert vectors to matrices, etc. that will be useful to us that I discuss below.
NOTE: I'm not going into all of the details of these commands. I'm only explaining what we need to know about the commands for our use for this project.
Command DOUBLE
The command we need to convert our strings to ASCII codes is DOUBLE. Here's an example:
x = 'ABCD'
y = double(x)
x =
ABCD
y =
65 66 67 68
Command CHAR
The command to convert numbers that are ASCII codes to text is CHAR. Here's an example.
x = 0:25; % creates a vector of the numbers from 0 to 25, respectively. Output is suppressed. y=x+65 % adds 65 to every element in the vector so the numbers in y now to from 65 to 90. alphabet = char(y) % alphabet is now a string that should be the alphabet in uppercase.
y =
Columns 1 through 14
65 66 67 68 69 70 71 72 73 74 75 76 77 78
Columns 15 through 26
79 80 81 82 83 84 85 86 87 88 89 90
alphabet =
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Command RESHAPE
We want to "reshape" a vector X to a matrix if size m x n. Then we use the command reshape(X,m,n):
ex1 = reshape(alphabet,2,13) A=[1 2 3 4] reshape(A,2,2)
ex1 =
ACEGIKMOQSUWY
BDFHJLNPRTVXZ
A =
1 2 3 4
ans =
1 3
2 4
Using MATLAB for the example on the handout
What follows is an explanation of how to use MATLAB to do the work for us on the first page of the Hill Cipher handout.
Our key is the following matrix:
K = [2 3;1 4]
K =
2 3
1 4
The numbers for our message are LINEARALGEBRA = 11 8 13 4 0 17 0 11 6 4 1 17 0. We could have figured this out on paper (which is error-prone) or we can use MATLAB. For the project, I'm requiring you to use MATLAB only.
msg='LINEARALGEBRA'
msgnum = double(msg)
msg =
LINEARALGEBRA
msgnum =
76 73 78 69 65 82 65 76 71 69 66 82 65
Notice that msgnum is now a vector of the ASCII codes for our message. For the Hill Cipher we want the numbers to be from 0 to 25 instead of 65 to 90. Thus we'll subtract 65 from our msgnum.
msgnum = msgnum-65
msgnum =
11 8 13 4 0 17 0 11 6 4 1 17 0
Now we need to get these numbers into the correct format. Notice that there are 13 letters in this message, we want 2 rows so we'd have 7 columns and thus we need one "dummy letter" of Z=25 at the end. I could add this at the end of my msgnum vector (if you know how to do this) or now that I've figured it out, I just redo the above commands (in your file you'd just change the original commands you had).
msg='LINEARALGEBRAZ'
msgnum = double(msg)-65
msg =
LINEARALGEBRAZ
msgnum =
11 8 13 4 0 17 0 11 6 4 1 17 0 25
Notice that these numbers are the same as on the handout. But from these numbers we need to create the 2x7 matrix M. Thus we use the RESHAPE command:
M=reshape(msgnum,2,7)
M =
11 13 0 0 6 1 0
8 4 17 11 4 17 25
Now we do the encoding. When we do the matrix multiplcation we see that we don't get numbers between 0 and 25 so we use the MOD command. Then we transfer back the matrix back to a vector and then letters. Notice that the encoded message is the same as on the handout. I did not suppress any output so you could see what each command does. You may want to suppress the output from the intermediate steps so that you only see the end result.
E=K*M E=mod(E,26) numcode=reshape(E,1,14) numcode=numcode+65 examplecode=char(numcode)
E =
46 38 51 33 24 53 75
43 29 68 44 22 69 100
E =
20 12 25 7 24 1 23
17 3 16 18 22 17 22
numcode =
20 17 12 3 25 16 7 18 24 22 1 17 23 22
numcode =
85 82 77 68 90 81 72 83 89 87 66 82 88 87
examplecode =
URMDZQHSYWBRXW
Finding the inverse: There are several ways one can find an inverse of a matrix in matlab. We could do it in matlab the way we do it my hand or by using the command INV.
D=inv(K) rats(D)
D =
0.8000 -0.6000
-0.2000 0.4000
ans =
4/5 -3/5
-1/5 2/5
Now we need to figure out what these fractions are modulo 26
a=26/5; % I just didn't want to type 26/5 over and over D(1,1)+a % D(1,1) is the 1,1 entry of D. I ran this once, saw it was an integer between 0 and 26 so done D(1,1)=ans % here I'm reassigning the 1,1 entry of D to be the above answer
ans =
6
D =
6.0000 -0.6000
-0.2000 0.4000
D(1,2) + a + a + a % I re-ran this several times, adding another "a" each time until I got an integer between 0 and 26 D(1,2)= ans % reassigning the 1,2 entry of D to be the previous answer
ans =
15
D =
6.0000 15.0000
-0.2000 0.4000
D(2,1)+a D(2,1)=ans
ans =
5
D =
6.0000 15.0000
5.0000 0.4000
D(2,2)+a+a+a D(2,2)=ans
ans =
16
D =
6 15
5 16
Now we have the inverse matrix, modulo 26 as in the handout. Let's check against our encoded message. Output of intermediate steps are suppressed.
examplecode numcode2=double(examplecode); numcode2=numcode2-65; % convert to numbers from 0 to 25 E2=reshape(numcode2,2,7) % reshape to 2x7 matrix
examplecode =
URMDZQHSYWBRXW
E2 =
20 12 25 7 24 1 23
17 3 16 18 22 17 22
Notice E2 is the same as E above. Now decode and then convert to letters:
chkmsg=D*E2; chkmsg=mod(chkmsg,26); chkmsg=reshape(chkmsg,1,14); chkmsg=chkmsg+65; char(chkmsg)
ans = LINEARALGEBRAZ