Math 696 -- Application: a simple cipher using matrices

Introduction to the linear algebra package

Application: a simple cipher using matrices

Application: a simple cipher using matrices

For practice in working with matrices in Maple, we will implement a simple cipher.

Reinitialize your Maple session by executing the command restart;, reload the linear algebra package via with(linalg):, and load the StringTools module via with(StringTools): (the StringTools module is new in Maple 7).

The idea behind the cipher is first to translate letters into numbers using the standard ASCII code (for instance, A->65 and q->113). After translating an alphabetic message into a string of numbers, encode the message in the following way. Break the string of numbers into blocks of five, view these blocks as the rows of a matrix, and multiply this matrix on the right by a specified 5×5 matrix. Then translate the numbers back into letters. The message is now unintelligible, but if the recipient of the message knows the matrix (and hence the inverse matrix), then the recipient can recover the original plain text.

There is a little technical complication, because the standard printable keyboard characters are numbers 32 to 127 in the decimal ASCII encoding. To make sure we stay within that range of characters, we will initially subtract 32 from all the numbers, perform all arithmetic modulo 96, and add 32 to all the numbers at the end.

Here is the 5×5 matrix we will use.

      [11    41    59    61     1]
      [                          ]
      [50    79    56    49    63]
      [                          ]
      [57    37    45    88     3]
      [                          ]
      [92    43    34    77    66]
      [                          ]
      [54    91     3    35    46]

This random matrix modulo 96 arose from the Maple command

     map(x->modp(x,96), randmatrix(5,5));

You will probably get a different random matrix if you execute this command. Instead, copy the following form of the matrix with the mouse to get the matrix into your Maple session.

Mtrx:=matrix([[11, 41, 59, 61, 1], 
              [50, 79, 56, 49, 63], 
              [57, 37, 45, 88, 3],
              [92, 43, 34, 77, 66], 
              [54, 91, 3, 35, 46]]);

The command convert(%,listlist); generated this expression for the matrix.

Your task is to follow the hints to decode this message:

+v_TW.vr#V'6%X1wywO<\\k25n\"z1ISYsJ-Hug#[zqaedSN~MI9yDMJmN'o+vS]%8~!cd1yD*)YY*\")6PZ\"( =Ih\"'~d3g?p(Y4XAiw$v*

To avoid typing mistakes, you had better copy the cipher text into your Maple session with the mouse. Watch out for the one blank space in the cipher text between the left parenthesis and the equals sign! The matrix form of the message looks like this:

        [+    v    _    T    W]
        [                     ]
        [.    v    r    #    V]
        [                     ]
        ['    6    %    X    1]
        [                     ]
        [w    y    w    O    <]
        [                     ]
        [\    k    2    5    n]
        [                     ]
        [%    z    1    I    S]
        [                     ]
        [Y    s    J    -    H]
        [                     ]
        [u    g    #    [    z]
        [                     ]
        [q    a    e    d    S]
        [                     ]
        [N    ~    M    I    9]
        [                     ]
        [y    D    M    J    m]
        [                     ]
        [N    '    o    +    v]
        [                     ]
        [S    ]    %    8    ~]
        [                     ]
        [!    c    d    1    y]
        [                     ]
        [D    *    )    Y    Y]
        [                     ]
        [*    %    )    6    P]
        [                     ]
        [Z    %    (         =]
        [                     ]
        [I    h    %    '    ~]
        [                     ]
        [d    3    g    ?    p]
        [                     ]
        [(    Y    4    X    A]
        [                     ]
        [i    w    $    v    *]

In order to decode the secret message, you can make use of some of the following commands from the StringTools module. (Read in the Maple Help browser for details about the syntax of the commands.)

Char converts a number to the corresponding ASCII character. For example, Char(78); is N. The inverse operator is Ord.
The function Explode converts a string into a list of individual characters. The inverse operator is Implode. See also the Join operator.

To decode the secret message, you need to convert the message into numeric form, shift the numbers by 32, change the list of numbers into a matrix, multiply the matrix on the right by the inverse of Mtrx (modulo 96), shift the numbers back by 32, and then reconvert to a string of alphabetic characters. Note that you can convert a list of lists into a simple list via map(op, ListOfLists);.

Exercise

Decode the secret message. Then try using Mtrx to encipher your own message. Send your message by e-mail to another member of the class for decoding.

Exercise on the Caesar cipher

A so-called Caesar cipher is a simple coding scheme that shifts all the letters of the alphabet by a fixed amount. For example, a Caesar cipher with shift 3 is defined by A->D, B->E, and so on. The end of the alphabet is wrapped around to the beginning, so the word SYZYGY would be transformed to VBCBJB.

Write a Maple procedure Caesar(String, Shift) with two arguments that implements a Caesar cipher with an arbitrary shift. That is, the output of the procedure should be the string String shifted by the amount Shift. For example, Caesar(SYZYGY, 3) should return VBCBJB.

For simplicity, you may use an alphabet consisting of all capital letters, and you may ignore punctuation. Illustrate your procedure by encoding a sample message and then decoding it again.

Application: a simple cipher using matrices