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]*b[j]+a[i]*b[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:
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!