Secret Santa, Gucci Gang, and Monoalphabetic Ciphers
We finally got started with our first cipher in our last post over here (https://bit.ly/2WtGSxI). We looked at a Caesar cipher and saw that it is pretty weak. Now we try to improve upon the Caesar cipher to get something better.
What went wrong with the Caesar cipher?
For one, you didn’t have to analyse too many letters in the plaintext to find the shift.Since the shift is the key, you’ve successfully decrypted the text.
Another problem was that brute-force attacks take barely any time to execute on computer, and combining this with the previous flaw would shorten the running time even further.
So when we construct our next cipher we have to make sure we mitigate these flaws.
Well, a one-line description of the Caesar cipher would be that every plaintext letter is shifted by the same amount. So the logical improvement we would make is to shift every letter by different amounts.
So that’s what we do. We make a list of shifts, one for each letter in the plaintext. To explain this, let’s look at the following situation.
It’s holiday season and Alice, Bob, and their friends are playing Secret Santa. Let’s name their group for convenience… I don’t know, Gucci Gang? Let’s stick with that. So Gucci Gang is going to play Secret Santa. And this time Eve is in the holiday mood too so she isn’t going to play spoilsport.
If you don’t know about that game, basically a group of people come together and decide to anonymously send each other gifts. Though usually this doesn’t happen in practice, ideally only person is supposed to be another’s Secret Santa, and hence only one person gets a gift from someone else. Another unfortunate thing I’ve seen is that sometimes someone gives another person an iPhone only to get a 10 rupees pen back. It’s a really heartbreaking situation :P
So what Alice decides is that everybody sends each other hand-written greeting cards only. That way the focus is more on making loving gifts, not expensive ones.
Which is where Paul the highly efficient postman comes in.
What this guy does is deliver everyone’s greeting cards on December 25 and bring joy to them.
But the thing is, Paul doesn’t really have any relation to the Gucci Gang. So he doesn’t know any of them, and that means they’re going to have to be really clear in how they are going to send it. No nonsense of trying to hide identities by dropping a gift near a lake and giving cryptic hints to find it before a crocodile devours it- Paul’s the man, he gets to know everything.
So each card is stamped correctly so that Paul can deliver correctly. Because if they make a mistake, Paul can’t deliver it correctly- because Paul’s the man, he never messes up. He has nothing to do with mistakes- neither does he make them, nor does he bother to fix it if someone else does. That’s literally his tagline by the way — GIGO. Paul, GIGO. Not GiGi, GIGO. Basically, Garbage In Garbage Out. If you mess up, Paul isn’t going to fix it for you. But the good thing about Paul is he’s reliable, so hey, he still gets a lot of traction.
So anyways, Gucci Gang has to be careful before delivering to Paul because they know that if they make a mistake, their entire game is ruined. They realize 2 important things:
(i) No two people should deliver to the same address. The idea is that if someone gets a gift they should know there is ONE Secret Santa out there who did it. But the fun of guessing whom the gift has come from is lost when you get more than one gift.
(ii) Nobody should be delivering to more than one address . Because if someone does that they effectively ruin the game. Moreover, if one guy delivers to 2 addresses, that means he has decreased the number of possible addresses for other people to deliver to. This would eventually contradict the rule we have already established. Like if there were 5 people and one guy delivers to 2, that means the remaining 4 have only 3 left. So because of the previous condition, one person is going to have to send it to themselves. That’s sweet for them, but kind of misses the point of Secret Santa.
(Highly recommend to check this out to understand the rest of the article and the previous paragraph better -https://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/)
So they have to make an arrangement such that Paul delivers everyone’s letter to a unique address. That way everybody gives only one gift and gets back only one.
Let’s end story time here and figure out how to apply this to our ciphers.
So let the alphabet be the Gucci Gang described here. The greeting cards are the shifts. Each letter is going to be shifted by some amount to become another letter.
However, we need to make sure that two letters don’t get encrypted to be the same letter- like how in the Secret Santa case it ruined the game, here it would ruin the cipher. That’s because we are using unique shifts as key, so when the receiver sees the letter, he has to be able to decrypt it, right? If for example both ‘b’ and ‘d’ are encrypted to ‘c’, then when the receiver sees ‘c’ how are they going to know when the original is ‘b’ or ‘d’? They can’t. So we need to be careful with that.
It is technically not as big a problem to let one letter correspond to multiple. As I mentioned about the pigeonhole principle, all that happens is that some letters get encrypted to themselves. Which means that the plaintext character is the same as the ciphertext one. However, in practice we don’t do this much except for one or two letters, because the more letters you keep the same, the more readable your ciphertext becomes. For this article, we assume that every letter is mapped to another.
What about Paul the man? What does he become in this cipher then?
It’s something called a bijective function or bijection. To put it simply, every element of some collection (we use the word set from now), say A, is mapped to a unique element of another set B. Every element of B has some element of A mapped to it- there’s no “free” element. Such a mapping is called a bijective function. In our example, the addresses, or shifts, are the addresses of the people. Paul the man is the bijection.
The only extra condition in the Secret Santa game and this cipher is that we are mapping from a set back to itself — or you could say that in the definition of bijection we have B=A.
The way I think of this new cipher we’ve constructed is not in terms of shifts though- it’s in terms of mappings like this. Rather than saying that each letter has been shifted to another, I would say that each letter is mapped to another. The reason for this is that once you accept this definition, you see that all you are doing is corresponding the alphabet to some shuffling of it.
Think about it, if you had only 4 letters, A,B,C,D you could say that A is shifted by 1, B is shifted by 2, C shifted by 2 and D shifted by 3, or directly say that A corresponds to B, B corresponds to D, C corresponds to A, and D corresponds to C. In effect, ABCD corresponds to BDAC. That means all you are doing is mapping the alphabet to some shuffling of it!
Now we decide to give this new cipher a name. It’s standard name is ‘monoalphabetic cipher’- because each letter corresponds to a unique letter only. And now that we have named it, let’s describe it formally-
Monoalphabetic Cipher
For a list s, plaintext p, an alphabet Σ with length λ, ciphertext alphabet is Σ’ . relation between Σ and Σ’ being given by a bijective function f: Σ -> Σ’ (meaning that f maps from Σ to Σ’). Then the ciphertext c corresponding to p is constructed by replacing each plaintext letter by the corresponding ciphertext letter.
Fine, that’s not the most formal I could’ve been, but that’s good enough. What is interesting is that this definition includes Caesar cipher too- with a shift s, if every letter is mapped to the letter+s, that is a Caesar cipher.
We mentioned two big problems with Caesar cipher. One of them was cleared in the beginning- that’s how we got the idea of constructing the cipher like this after all. But the other, about brute force attacks, let’s see that.
Last time we saw that λ computations at best were needed, because there are effectively only λ possible shifts(another notation — this ‘at best’ thing is clumsy, so we just say ‘O(λ)’. ). But here the number of bijective functions from the alphabet to itself is the number of possible shifts, right? So the maximum number of computations needed is O(number of bijective functions from Σ to Σ).
But what is the number of bijective functions from Σ to Σ? I’m leaving the explanation as an exercise for the reader, but it is λ!. You’re going to have to find out what that means too.
This is a really huge number. For λ=26 itself, the number is 26! or in the order of 4* 10^(26). This is way, way bigger than 10^(9), or the number of computations a standard computer can perform in a second. Dividing gives us 4*10^(17) seconds to attack with brute force, which is like 10 billion years! To put that into perspective, the age of the universe itself is 13.8 billion years! So nobody is going to live that long, and so we don’t need to worry about brute force attacks.
So yippee! We got somewhere at last. But that doesn’t mean we are done- turns out monoalphabetic ciphers can be broken by one standard method. That method is pretty big and important- so we are going to look at that in further posts.
Note- Monoalphabetic ciphers is actually a type of ciphers, of which there are many. Rather than explaining them all I have just explained the basic class. Because the basic concept used is the same in all of them so as this publication focuses on a conceptual understanding, we are only looking at that idea behind them.
