GS 2003/Math - Collins
Lab 6
Hill Ciphers

Jefferson's Cipher

Ideas for Jefferson's Cipher:
   1.  You can use code1 from Lab 5 to convert the
       key word to numbers (in range 0-25)
   2.  If N is the number of letters in the key word, then
       the ith letter of the message is encoded using
       the jth letter of the key word as the additive
       shift, where j = mod(i,N); if (j==0), j=N; end
       I.e. if cP is my message converted to numbers
       and kW is my key word converted to numbers,
       then the encoded message is generated by 
           cP(i) = mod(cP(i)+kW(j),26);
       as i goes from 1 to the length of the message
   3.  To decode, use the same process, but subtract kW(j)

Assignment I


   Using the key work MATH, decode the following message:

        AFTSXTALFHBUSSMOUSBZANX

   Hint: You might want to write a pair of programs to cipher and 
         decipher messages using Jefferson's Cipher.  

Hill Ciphers

Background

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)
     det(A)*inv(A)

Recall that if A is a matrix with integer entries 
then det(A)*inv(A) also has integer entries, 
no matter how big A is.

Encoding

Let E be our 2x2 encoding matrix.  And let P be
our message.  The first step is to use code1 to get the
matrix of numbers for P:
    code1

Check the length of cP, (length(cP).  If it is
odd, add another value to the end cP(end+1) = 0
else, leave it alone.

To put our message in the right 'shape' for the matrix 
multiplication (it must by 2xM), we use reshape
    cP = reshape(cP,2,length(cP)/2)

Now we can encode our message (mod 26)
    cP = mod(E*cP,26);

Before we can use decode1 to turn this back into text, we
need to 'unfold' it (the result is 2xM).  So we finish our
encoding by
    cP = cP(:)';
    decode1    

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

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

Decoding

Decoding is just like encoding, except that we need to use the inverse
of our encoding matrix. Since we are using mod 26 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 26) of the determinant.  And instead
of using -b and -c, we use their additive inverses.
In the case when E = [1 2; 3 5]; we have det(E) = -1 = 25.
The inverse of 25 is 25, so the inverse of E (mod 26) is

         ( 5   24 )    (125  600)   (21   2)
      25 (        ) =  (        ) = (      )   (mod 26)
         (23    1 )    (575   25)   ( 3  25)

Let D = [21 2; 3 25]; and repeat the steps above
that we used to encode the message, replacing E by D and
starting with the encoded message. That would look like
    P = 'DVDIAZKWRWUHCFAZAHPIOY'
    code1;                     % convert to numbers
    cP = reshape(cP,2,11);     % changes cP into 2xM
    cP = mod(D*cP,26);         % decode message
    cP = cP(:)';               % make it a row vector
    decode1                    % convert to characters

Assignment II

   Practice the steps above and get ready for the Code Maze Challenge!

Code Maze

   1. Work in teams of 2 or 3.
   2. Will have to decode messages using additive and multiplicative
      ciphers, Jefferson ciphers and Hill ciphers.
   3. Top finishing teams earn points.
   4. Keep track of the places you go.

Challenge (after the Code Maze)

   Decode the following message

      TXPTPGLNWXVGPYFDFXZEXDQSEYFXXGLCPYXDCLSWLNOTT
      YPWUXQYPWSFAGVQDRCLXDPEPWYKNARFGLSGWEJRTQBLAK
      WGBEPGHXFNPGTXVXOIFAGUOAKADNVXQEYAMRZLDQLBYE

   It was encoded using a 2x2 matrix in the Hill Cipher.

Mail: ccollins@math.utk.edu