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
        newmatrix.append([])
        for j in range(2): #because b only has two columns
            newmatrix[i].append(a[i][0]*b[0][j]+a[i][1]*b[1][j])
    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:
    nummat.append(0)
rows = len(nummat) / 2
letter_count = 0 #which letter are we on?
x = []
for i in range(int(rows)):
    x.append([])
    for j in range(2):
        x[i].append(nummat[letter_count])
        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:
        output_list.append(thing)
print(output_list)

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:

1010001000001010000001011010010010010011000000000110010001010000000001011001001001001001110100010100

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:

7690829846223890060687071234476610416219820420808390252623234862864607637207407087283641336366634580

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