Permutations are interesting mathematical objects, with many different applications. One use of permutations is as a tool for encrypting secret messages so that spies can’t read them. If Alice and Bob share a secret permutation, then they can use a little bit of maths to send encrypted messages to each other that no one else will be able to understand.

Permutations are a type of mathematical object that really interest me, and getting to play around with permutations was one of my favourite things about my summer research project. In this post, I’ll explain what a permutation is, and give one interesting application of permutations as a tool for encrypting secret messages so that spies can’t read them.

A permutation is basically a rearrangement of some set of objects. We might consider the set of objects {1, 2, 3, 4, 5}. Then, (5, 3, 1, 4, 2) is a permutation of this set, since it is some reordering of the elements. We can think of a permutation as a function that sends each element of our set to a unique position. The above permutation can be thought of as the function that sends 5 to position 1, 3 to position 2, 1 to position 3, 4 to position 4 and 2 to position 5. But how can we use this permutation to encrypt a message?

Well, suppose that two friends, Alice and Bob, agree on a secret permutation that no one else knows. For example, they might agree on the permutation given as an example above. Now, let’s say that Alice had a secret message (the word ‘MATHS’) and wanted to send the message to Bob so that no one who might be spying would be able to read it. Then, Alice can encrypt the message by using the permutation to jumble up the word in a specific way: we move each letter in our message from its current position into the new position specified by the permutation. ‘M’ is currently in position 1, and our permutation sends position 1 to position 3. So, in our jumbled up message, ‘M’ is in position 3: _ _ M _ _. ‘A’ is currently in position 2, and our permutation sends 2 to 5, so ‘A’ will appear in the 5th position in our jumbled up message: _ _ M _ A. By applying the permutation to each letter, we get a complete jumbling of our message: S T M H A. Now, no spies will be able to read the message.

But how will Bob be able to read the message? Well, Bob also knows our secret permutation, and he can use the inverse permutation to decrypt the message. The inverse permutation is simply the function that sends each number back where it came from in the original permutation. So, the inverse of our permutation sends 1 back to 5, 2 back to 3, 3 back to 1, 4 back to 4 and 5 back to 2. By jumbling the message ‘STMHA’ according to this inverse permutation, we undo the original jumbling and get back the original message. So, by using the permutation jumbling, Alice has succeeded in sending a message that Bob can read but spies cannot.

Steven Condell
The University of Sydney  View Steven Condell
Profile