Coding for Encoding and Decoding

  • 0

Coding for Encoding and Decoding

Category : Uncategorized

I read a quora answer from a grown up who learned about matrices years ago and even though he got through it he still doesn’t know what matrices are used for. In one word: Transformation. I’ve done videos on using matrices to transform points into other points and create 2D and 3D animations:

There’s another important field that concerns transforming letters into numbers and then transforming them back: cryptography (or is it cryptology? Or cryptanalysis?) You know: writing secret codes so others can’t read your message. The “Caesar Cipher” is the one we learned as kids: changing every letter to the letter before or after it, or if you’re really fancy, the letter 3 letters before it:

Cryptography has advanced somewhat in 2,000 years, and breaking the “replace every S with a Q and every E with an X” code has become a popular pastime in the puzzle section of the newspaper.

There’s a way to replace every letter with a corresponding number, but that doesn’t make the code any more complicated to break than the cryptoquote above.

That’s where matrices come in. You can put the numbers into a matrix and transform them into other numbers by multiplying them by a transformation matrix. Here’s how you multiply two 2×2 matrices together. The rows in the first matrix are multiplied by the columns in the second:

The first matrix can have as many rows as you want:

Here’s how to multiply two matrices, where the first one has two columns and the second one is a 2×2 matrix:

def multMatrix(a,b):
    '''Multiplies two matrices.
    b is a 2x2 matrix'''
    newmatrix = []
    for i in range(len(a)): # repeat for every row in matrix a
        for j in range(2): #because b only has two columns
    return newmatrix

The new numbers won’t make any sense until the designated recipient undoes the transformation with the inverse of your transformation matrix.

First we define our alphabet with a string.

alpha = ' abcdefghijklmnopqrstuvwxyz'

Every element in a string has an index, so that’s how we’ll replace a letter with a number:

nummat = []
msg = 'the kids are alright'
for n in msg: #go through every letter
    numlet = alpha.index(n) #replace the letter with its index
    nummat.append(numlet) #put the numbers in a list
    print(nummat) #print the list

It prints out a list of numbers:

[20, 8, 5, 0, 11, 9, 4, 19, 0, 1, 18, 5, 0, 1, 12, 18, 9, 7, 8, 20]

We want there to be only two columns, so if the length of the message is an odd number of letters, we’ll add a zero on the end (which is a space in our code). We can find the number of rows by dividing by 2, and fill that many rows with two numbers:

if len(nummat) % 2 != 0:
rows = len(nummat) / 2
letter_count = 0 #which letter are we on?
x = []
for i in range(int(rows)):
    for j in range(2):
        letter_count += 1

Finally, we multiply by our transformation matrix, which we’ll call ‘y.’

y = [[1,2],[-3,4]]
z = multMatrix(x,y)

This is the matrix we get out:

[[-4, 72],
[5, 10],
[-16, 58],
[-53, 84],
[-3, 4],
[3, 56],
[-3, 4],
[-42, 96],
[-12, 46],
[-52, 96]]

But we don’t want our enemies to suspect we’re using matrices, so we’ll “flatten” the list and print it all on one line:

output_list = []
for row in z:
    for thing in row:

Now it prints out our list of numbers:

[-4, 72, 5, 10, -16, 58, -53, 84, -3, 4, 3, 56, -3, 4, -42, 96, -12, 46, -52, 96]

The numbers look pretty random: some negative, some positive, and not many repeated numbers. To show you how well this mixes letters up, let’s encrypt the message “blah blah blah blah blah blah blah”

[-34, 52, -23, 34, -6, 8, 9, 28, 8, 16, -34, 52, -23, 34, -6, 8, 9, 28, 8, 16, -34, 52, -23, 34, -6, 8, 9, 28, 8, 16, -34, 52, -23, 34]

Interesting! A repetition of a 5-character word (including the space) seven times is transformed into a 10-character “word” repeated three and a half times.

A similar function decrypts the message:

>> decryptMat()
Enter the numeric message separated by commas:-4, 72, 5, 10, -16, 58, -53, 84, -3, 4, 3, 56, -3, 4, -42, 96, -12, 46, -52, 96
the kids are alright

Ramping up the Mystery (even without Matrices!)

A few years ago a student of mine suggested we really hide the numbers by converting them to binary:


Your enemies would easily guess you were using binary. So my student suggested we convert every 1 into a random odd number, and every zero into a random even number:


Now this looks mysterious! The enemy will never suspect that “76908” is really just “10100” which is 20, and the 20th letter in the alphabet is “T.”

Cryptography is a great way to teach string manipulation in any programming language, not to mention matrix multiplication and binary numbers!


Leave a Reply

Recent Posts