eli5: why 3 pairs (or maybe 2?) of cleartext and ciphertext letters are needed to determine an affine cipher?
In: 0
Suppose we just have a shift cipher, where every letter of the alphabet is shifted by a fixed amount. In that case, you obviously just need one pair of cleartext and ciphertext letters. For instance, if I tell you that cleartext ‘e’ maps onto ciphertext ‘g’, then you know that, since those letters are 2 apart in the alphabet, that means *every* letter in the ciphertext will be shifted up by 2 compared to the cleartext.
In this example, there is one unknown variable: the amount of shift. Breaking the cipher therefore amounts to solving an equation with one unknown:
cipher_letter = (cleartext_letter + b) % 26
where b is the amount of shift, and ‘%’ means the modulus. That is, divide the result by 26 and take the remainder. This is just a mathematical way of writing that we will “wrap around” the alphabet when we reach numbers greater than (or equal to) 26. For instance, if our cleartext letter is y, and we want to shift it up by 2, then after ‘z’ we loop back to ‘a’. Also, we assign a=0, not a=1.
In our example from before, if we know that e -> g (letter 4 gets mapped to letter 6), the equation looks like this:
6 = (4 + b) % 26
And so we can see that the equation will be satisfied if b=2,.
Affine ciphers add one additional unknown:
cipher_letter = (a*cleartext_letter + b) % 26
That is, we now first multiply the alphabet index of our cleartext letter by ‘a’, before shifting it and taking the modulus. To decrypt this cipher, we need to find the values of two unknowns: ‘a’ and ‘b’. And it turns out that there is a mathematical rule that you always need at least as many data points as you have unknowns, in order to be able to solve such a problem. Which means, in this case, that we need two data points (two pairs of cleartext/ciphertext letters).
Graphically, you can think of it this way: the affine cipher remaps letters along a line. You’re trying to find the *slope* (a) and *intercept* (b) of this line. And for any line, if you know two distinct points that are on that line, then you can draw the whole line. Therefore, two points are enough to figure out the two unknowns that define the line.
(Incidentally, while it’s easiest if you simply are given two pairs of correct values, a cipher like this can be broken quite easily, even by hand, by trying educated guesses of ciphertext/cleartext letter pairs, and trying to solve the equation with those guesses. An educated guess can be made, for instance, by looking at letter frequencies, if you know the language of the cleartext. E.g. in English, ‘e’ is the most common letter, and so whichever is the most common letter in your ciphertext is likely going to map to ‘e’. Of course this is more reliable if you have a longer text to work with, as in short texts it’s statistically less certain that the letter frequencies will match their overall averages.)
Latest Answers