GS 2001/Math - Collins
Lab 4
Hill Ciphers

Preliminaries

Start MATLAB (from Start Menu).
Arrange your windows so you can see MATLAB and this webpage.

Review Inverses and Mod Arithmetic

In MATLAB you can compute the determinant of a matrix by using
det and the inverse using inv.  For example, try
     A = [1 2; 3 4];
     det(A)
     inv(A)

For the 2x2 case we know that we can construct the inverse by
rearranging the entries of the matrix and dividing by the determinant.
This is similar to what happens in general.  If A is a 
matrix with integer entries then det(A)*inv(A) also has
integer entries, no matter how big A is.

In MATLAB we perform mod-arithmetic (mod-27) by using regular arithmetic
but then using mod on the result.  The only thing we have to
remember is that instead of dividing, we multiply by the inverse.
To find the multiplicative inverse of a number x (mod-27)
we can use the following steps:
    x = number   the number you want to find the inverse of
    num = [1:26]   all the numbers from 1 to 26
    res = mod(x*num,27)   result of x*(1,...,26) mod 27
    find(res==1)  this finds which value gives a result of 1
           find will either produce a number (the inverse) or will 
           result in  "ans = []" meaning there is no inverse.

This is from the previous lab, and you should have used this method or
something similar to fill in the multiplicative inverses in the HW.

MATLAB functions (vs. scripts)

Last lab you created two programs "code1.m" and "decode1.m".  These
are what are called scripts.  When you run them it works just
like you had typed in those commands in the command window.  The only
problem with scripts (as some of you found out) is that they can change
the values of variables that you don't want changed.  A way to fix
this is to convert these scripts into functions.

In a function all the work and variables are done in their own
workspace.  This means that you must give the function all the
information it needs and have it pass back everything that you want
passed back.  To tell MATLAB that the file is a function and what
the input and output variables are you put a line like this at
the top of the file:
    function output = functionname(input)
For example, we want the function version of code1.m to take a message
as input and return the number values according to Cipher 1.  Calling
this version "code2.m" it might look like this:
    
    function cP = code2(P)
    %  code2:  converts a message to numbers
    P = upper(P);
    cP = real(P);
    cP = cP - 64;
    ind = find(cP<0);
    cP(ind) = 0;

Copy this to a file and save as "code2.m".  To use it, you type
    code2('my name is bob') or
    M = 'now is the time for all good mathematicians';
    res = code2(M);

You do not have to use the same variable names (P and cP) as the ones
in the function when you call the function.

Now, create a function from decode1.m and call it "decode2.m".  The input
should be the matrix of number values and the output should be the 
message.  Make sure you put semi-colons (;) at the end of the lines so
that no extra stuff gets displayed.  If you aren't sure what to do,
there's a copy of this function at the end of this file.

When you have it done you can test it by
     decode2(code2('enter any thing here'))
and you should get back the uppercase version of what you put in.

Note: a function or a script can use a function, so if you find yourself
running the same commands over and over, think about putting them into
a script or a function.

Hill Ciphers

For the Hill Cipher we use an NxN matrix to encode our message.
First we need to know how to do the transformation and then
how to decode the message.

Encoding

Let E be our 2x2 encoding matrix.  And let P be
our message.  The first step is to use code2 to get the
matrix of numbers for P:
    cP = code2(P);
Now we need to put this row matrix into the proper shape for
our encoding matrix; it needs to be 2xM.  That means it must
have an even number of characters.
    l = length(cP);   % number of characters
    if (mod(l,2)==1)  % l is odd
       cP(l+1)=0;     % add a 0 to the end
       l = l + 1;     % increase length by one
    end
    cP = reshape(cP,2,l/2);    % changes cP into 2xM

If E was 3x3 we would have to see if we needed to add 1 or 2 
extra spaces to the message to make the length a multiple of 3.

Now we can encode our message (mod-27)
    eP = mod(E*cP,27);
Before we can use decode2 to turn this back into text, we
need to 'unfold' it (the result is 2xM).  So we finish our
encoding by
    eP = eP(:)';    % makes eP 1x(2M)
    C = decode2(eP);     % transforms it back to text

Use the following matrix E and message P and see what you get:
    E = [1 2; 3 4];      
    P = 'Bobby builds baby bottles';
You should get:
    ELFNYUQIFUOGDHEKYUELFEVBSC

Note that the 7 Bs in the original message get transformed into EFNQHKE
thus the character frequencies get all messed up.

I put a script "hill.m" at the bottom of this message for this process.

Challenge: write a function which takes a message and a 2x2 matrix
           and produces the encoded message.

Decoding

Decoding is just like encoding, except that we need to use the inverse
of our encoding matrix. Since we are using mod-27 arithmetic we
can't just use inv(E).  Remember the formula for the inverse:

                     1    (  d  -b )             ( a   b )
   inverse of E =  -----  (        ), where  E = (       ).
                   det E  ( -c   a )             ( c   d )

We can use this same formula, but instead of dividing by the determinant,
we multiply by the inverse (mod-27) of the determinant.  And instead
of using -b and -c, we use their additive inverses.
In the case when E = [1 2; 3 4]; we have det(E) = -2 = 25.
The inverse of 25 is 13, so the inverse of E (mod-27) is

         ( 4   25 )    ( 52  325)   (25   1)
      13 (        ) =  (        ) = (      )   (mod-27)
         (24    1 )    (312   13)   (15  13)

Let D = [25 1; 15 13]; and repeat the steps above 
that we used to encode the message, replacing E by D and
starting with the coded message C instead of P.  That
would look like
    cP = code2(C);
    l = length(cP);   % number of characters
    if (mod(l,2)==1)  % l is odd
       cP(l+1)=0;     % add a 0 to the end
       l = l + 1;     % increase length by one
    end
    cP = reshape(cP,2,l/2);    % changes cP into 2xM

    eP = mod(D*cP,27);         % decode message
    eP = eP(:)';               % make it a row vector
    M = decode2(eP);           % convert to characters

After performing these steps the message M should be the
same as the upper case version of the original message P.

Exercise

Pick an encoding matrix E (different from above) and a message P.
Encode the message.
Find the decoding matrix D and decode the message.

Print out or send me:
    Your matrices E and D
    Your messages: original and encoded

Challenge: Try a matrix bigger than 2x2

Extra Stuff

Computing frequencies:  Suppose we have the numbers from an encoded message
in a matrix cP.  How can we figure out the frequencies?
Since we know the values must be between 0 and 26, we can just set up
27 'counters' and increment the appropriate counter when we see the
corresponding value.  It might look like this:

   counter = zeros(1,27);     % row matrix of 27 zeros
   l = length(cP);            % number of values to look at
   for i = 1:l                % loop through all the values
      index = cP(i)+1;        % value (+1 so in the range 1-27)
      counter(index) = counter(index) + 1;   % increment counter
   end

Now for further processing we might want to see these frequencies in
order, with their appropriate percentages

   [x,order] = sort(-counter);   % sorts from largest to smallest and
                                 % gives the order they are in
   for i = 1:27
      index = order(i);          % index of i-th most common
      perc = counter(index)/l*100; % frequency percent
      disp([index, perc])        % display results
   end

Challenge: write this as a function which takes cP as input
   and prints out the results not by number but by letter.
   You might need the command num2str


---------------------------------SOLUTIONS-------------------------------
To use these, select all the lines in green, copy them, and paste them
into the M-file editor window.  Save and run.


decode2.m

function M = decode2(cP)
% decode2.m  by Dr. Collins 6/19/01 for GSS:Math

ind = find(cP==0);
cP = cP + 64;
cP(ind) = 32;
M = char(cP);


hill.m

% script to encode a message P with matrix E

cP = code2(P);
l = length(cP);   % number of characters
if (mod(l,2)==1)  % l is odd
   cP(l+1)=0;     % add a 0 to the end
   l = l + 1;     % increase length by one
end
cP = reshape(cP,2,l/2);    % changes cP into 2xM

eP = mod(E*cP,27);         % peforms the encoding (mod-27)
eP = eP(:)';               % converts back to a row matrix
C = decode2(eP);           % converts to text

Mail: ccollins@math.utk.edu