## 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!