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