GS 2003/Math - Collins
Lab 5
Patterns in Letters: Ciphers

Preliminaries

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

Mod Arithmetic

In MATLAB you can do modular arithmetic by using the mod command.
Type  help mod to learn more about this command.

Suppose you want to compute various things mod 26, then you would compute

    4928   as mod(4928,26)
    22+19  as mod(22+19,26)
    4*16   as mod(4*16,26)
    86-123 as mod(86-123,26)
    -12    as mod(-12,26)

Modular Inverses

To compute additive inverses, there are two obvious methods.  First,
since 0=26 (mod 26), the additive inverse of a number x is
the number y such that x + y = 26.  Thus y = 26 - x.
The second way is to use mod(-x,26).  The second way works
even if x is not in the range 0-25.

Computing multiplicative inverses is more challenging.  There is an algorithm
that can be used to find the multiplicative inverse, but it is pretty
complicated (It is based on the Euclid's Algorithm, which is a way
of finding the GCD of 2 numbers).  The easiest way (in MATLAB) to find
multiplicative inverses is by exhaustion.  Try the following:
    x = 4   the number you want to find the inverse of
    num = [1:25]   all the numbers from 1 to 25
    res = mod(x*num,26)   result of x*(1,...,25) mod 26
    find(res==1)  this finds which value gives an answer of 1
           find will either produce a number (the inverse) or will
           result in  "ans = []" meaning there is no inverse.

Alpha -> Numeric -> Alpha

To convert from letters to numbers and back we need to use 3 different
commands upper, real and char.  Try the following:

     P = 'your name'
     P = upper(P)
     cP = real(P)

Note how the result is a list of numbers between 65 and 90, with 32s for
the spaces.  If you then subtract 65, the result is only numbers in the
range 0-25, plus negative numbers for the spaces (and punctuation).
Try the following:

     cP = cP - 65
     ind = find(cP<0)  this finds where non-letters were
     cP(ind) = [] and removes them

Now to convert back, try the following:

     xP = [2 7 20 2 10 2 14 11 11 8 13 18];
     xP = xP + 65;
     
     char(xP)

Now convert the coded version of your name (in cP) back to text.

Automating the Process

You can put all the commands to go from text to numbers and from
numbers back to text into a script or function and then run
it from MATLAB.

Write this program and call it "code1.m"

If you want, a copy of this program is at the end of this file.
To run it set P to the string you want to convert and then
type code1
It will then convert P to a list of numbers.

Repeat this process with the commands to convert from numbers back
to text and call this file "decode1.m"

For example, try this
   P = 'I like math more than food'
   code1
   decode1
   

Try converting messages back and forth from text to numbers and back.

Additive and Multiplicative Ciphers

For an additive cipher, take the result of code1 (cP)
and add the shift x to each value (mod 26) and then
convert back to text, i.e.
   x = 11;
   cP = mod(cP+x,26)
   decode1

To decode a message, set P to the encoded message
and use the inverse shift in the addition above.

For a multiplicative cipher, just switch the
addition to a multiplication.
   x =5;
   cP = mod(cP*5,26)
   decode1

Assignment

  1. Write or copy the programs 'code1.m' and 'decode1.m'
  2. Decode the following messages (note each is encoded by
     either an additive or multiplicative cipher)

     Hint: (a) Create a new M-file which does the basic steps
               so you can try different ciphers
           (b) Add semi-colons to keep the clutter down
           (c) You can work with part of the message to
               figure out the code and then convert the
               entire message with the code you found

  3. Turn in the decoded messages.

  Msg1:

  XYGSCDRODSWOPYBKVVQYYNWOXDYMYWODYDROKSNYPDROSBMYEXDBIGKV
  UCYPDVIKXNMKBBIKLSQCDSMUNYXYDKCUGRKDIYEBMYEXDBIMKXNYPYBI
  YELEDGRKDIYEMKXNYPYBIYEBMYEXDBI

  Msg2:

  YNSYDBZSJZKRYQYJZKWARUMSQBKYNQKNCABZSCABKWQKQBZSUMSQBKYN
  YDIZSBZSFCABZSCABKWARHKQWYXSFKSQAFSWFSABSHYFHKQWYXSFSH

  Msg3:

  CLAQOYYAIOFAYNKNYONYOMKBRYTCWOJKWRCAYRNRKBTAYRWCOCRCNCVK
  BTKVYKLQCYYYYHOTTTCNIYVFONCVCYQSUFKFABROBVKROUKRO


  4. (Challenge) Take a message and encode it by some type of
  substitution cipher.  Make it a long message, make the code
  tough and send it to me.  If I can't break it and it is invertible,
  you get points.


Decoding Tricks

Substitution codes don't change the distribution of the
letters in a message, i.e. every E is converted to the
same letter.  Thus if the original message has a typical
English letter distribution (as given in the handout)
then the encoded message's distribution will indicate
what letter is what.  For example, if the most common
letter in the encoded message is 'X' then it is probably
the encode of 'E'

To find the distribution, convert the message to numbers (code1)
and then use the hist command (it produces
a histogram of the data), like this
   hist(cP,26)
   or
   val = hist(cP,26)
Use the first to get a graph, the second to get the count for each letter.

For a more sophisticated analysis, you can use the frequency for
pairs of letters.  I'll leave it you to figure out how to
compute that frequency.


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


SCRIPT 1  code1.m

% code1.m  by Dr. Collins 6/19/03 for GSS:Math
% assumes P contains the message to be converted

P = upper(P);
cP = real(P);
cP = cP - 65;
ind = find(cP<0);
cp(ind) = [];
disp(cP)


SCRIPT 2  decode1.m

% decode1.m  by Dr. Collins 6/19/01 for GSS:Math
% assumes cP contains the message as numbers

cP = cP + 65;
P = char(cP);
disp(P)

Mail: ccollins@math.utk.edu