Have you ever heard of Ceasar's Cipher? Allegedly Julius Ceasar used this very simple encryption scheme to protect his private messages.
The algorithm is very easy: It changes every letter in a message by substituting it with the character 3 places to the right of in the alphabet. At the end of the alphabet it wraps around and starts at the beginning.
For example , , .., , , , and the message is turned into .
To decrypt a message, all you have to do is count backwards in the alphabet so , , ..., .
This algorithm can easily be changed by changing the number of steps you move to the left or right in the alphabet for each character. If you use do 13 steps instead of just 3 you end up with ROT13 - you might have heard of that too - which has the very nice property that you can use the same method to encrypt and decrypt you message (in our common 26-character alphabet).
So you can parametrize this little algorithm by this step and get a bunch of algorithms - nice huh?
Demo
If you want you can try out the algorithm here:
some math
So why has ROT13 this nice property? The magic is in the way the algorithm wraps inputs. If you number the letters to with to you might notice that the operation here is really just an addition: , , ...
But at the end there is something curious happening: ?, and ?
It's almost as if we want and to be the same?
And indeed mathematician have a way to express exactly that idea by working with quotient sets/groups.
The idea behind that is: Given an equivalence relation \(\sim\) on some set \(S\) you can define a new set \(S/\sim\) that consists of all the equivalence classes of \(\sim\).
These are subsets of \(S\) so that for two elements \(a,b \in S\) you always have \(a \sim b\)).
Here we are interested in integers and the relation is
$$ a \sim b \Leftrightarrow 26 \ divides \ (a-b) $$
It's easy to extent addition to that set which usually is written as \(\mathbb{Z}_{26}\).
But don't fear: You probably already know this - all you have to do is everything:
...
And that is why there are really only different algorithms (think about it). It even get's better: decrypting with key is the same as encrypting with key . The nice property of ROT13 is a small corollary from the fact that
$$ 26 - k \equiv -k \ (mod \ 26) $$
which shows, that \( -13 \equiv 13 \ (mod \ 26) \).
first approach
It's not to hard to use this exact idea - Mapping a character into a number, adding the key to this number modulo 26 and then translating the resulting number back into a character - in an imperative language.
Here is a basic version in C#:
Please note that this will not change characters outside the range.
a more functional solution
Of course you could do the same in pretty much every language out there but for my taste that all is just a bit to much bound to low-level implementation details.
For example the solution above would not work if the character-values for to were not direct successor of each other.
In the end is just a function with a very limited domain (if you don't count all the characters it keeps constant).
On the letters - it's indeed a bijection and a very simple one.
So simple that there used to be toys that helped kids encrypt their messages just like Ceasar but without knowing anything about quotient groups or modulo arithmetic - all you had to do was find the character on a toy like this:
and look bellow the character to find it's encrypted form.
To decrypt a character back you could either flip the ring or - if it was a fancy one - rotate it in the other direction.
So instead of that arithmetic imagine a approach like that toy.
modelling in Haskell
First let's simplify things a bit: Instead of being able to move left and right on a ring it's enough to only move right because sooner or later (see the math section) it get's to the same state moving left would have.
As Haskell is lazy the top-section of the ring - if we start at is just
which is the same for the bottom section if it was not twisted ():
Rotating the bottom ring left is easy too:
Now once the ring is setup correctly encoding a character works just like you would with that toy - you look up the character on the top and give back the character on the bottom.
The naive version of this would be
But caution is needed: will keep looking forever if it cannot find the character (try it! and ask yourself: why?).
To fix that it's enough to only look at only as much pairs as there are characters in the :
Composing all these parts together we already have a working algorithm:
performance or don't use in production
Of course the performance is a bit shitty. The reason is that is not really up to where the arithmetic solution is, it stupidly moves along the list and will take 13 operations on average with this . So it's \(O(n)\) for a alphabet of length \(n\).
You can improve this by translating the zipped pairs into a / of some sorts.
This is the version I used for the small demo above in Elm:
This should be fast enough for a algorithm you should never use in a real scenario ;)