6 Modern Times ¹⁰

Having squeezed all of the juice out of the idea of adding letters to others, we go back and look again at other ways to proceed. It seems like it should work to multiply the numeric codes for the letters in the plaintext instead of adding them, so let's try that. Just as before, we'll begin with something analogous to the Caesar cipher: our key is a single number between 1 and 25, and we multiply each letter by that number and reduce modulo 26.

Since the Caesar cipher added 3, let's try multiplying by 3. Suppose our plaintext is blue. Representing this as numbers, we have the sequence 1,11,20,4 (refer to the chart on page if you like). Now we multiply each one by 3 and reduce modulo 26. For the first letter of the ciphertext, we get the numeric value 3, or D. The second letter is $33 \mbox{mod} 26$ , or 7, which we can write as H. The third is $60 \mbox{mod} 26$ , which is 8 (or I), since 60 = 8 + 2 x 26. And our final letter encrypts to M, so the ciphertext is DHIM.

One thing to notice here is that we get a different class of substitution ciphers out of this process. The Caesar ciphers gave us one set, and these multiplicative ones give us another set. These seem to mix things up a little more (for example, although l and u start out far apart in the alphabet, they encrypt to the adjacent letters H and I.

Now that we see how to encrypt, let's try to decrypt this enciphered message, assuming we know that the encryption key was 3. That is, we are given the ciphertext DHIM as well as the fact that the encryption key was 3, and we want to recover the plaintext. Writing the ciphertext as numbers, we have 3,7,8,12 and we want to divide each by 3. The first is easy: 3/3 = 1, and sure enough, D corresponds to b. But $7/3 = 2\frac{1}{3}$ , and we don't have a letter for that. Is all lost?

We just have to make sense of what we mean by division. Remember, we are working modulo 26, so we want to solve the equation

$\begin{displaymath}7 = 3x (\mbox{mod} 26).\end{displaymath}$

This means we get to add multiples of 26 to get things to work out; the above equation is the same as saying

$\begin{displaymath}7 = 3x \quad\mbox{or}\quad 7+26 = 3x \quad\mbox{or}\quad 7+52 = 3x \quad\mbox{or}\quad \ldots\end{displaymath}$

Since 7+26=33, we see that x=11 works, and our plaintext letter was indeed the letter l.

Deciphering I works the same way: 8/3 isn't a whole number, and neither is 34/3, but 60/3=20, so our plaintext is just the letter with character code 20, or u.

We could have saved a little work by changing division into an appropriate multiplication. Just as with real numbers, to divide by 3 we can multiply by $\frac{1}{3}$ , as long as we interpret $\frac{1}{3}$ correctly. As above, we have to find a number x so that

$\begin{displaymath}3x = 1 (\mbox{mod} 26).\end{displaymath}$

This number is 9, since 3 x 9 = 27 = 1 + 26. 9 is called the multiplicative inverse of 1, modulo 26. When we are working modulo 26, division by 3 is the same as multiplication by 9.

Now suppose we had tried a key of 4, and wanted to encrypt the name of our friend bob. This has the numeric sequence 1,14,1, and after multiplying by 4, we have 4,56,4. Since we are working mod 26, we must reduce 56 to 4, giving the ciphertext EEE. Something is fishy here-- there is no way to know whether the E came from b or o. Why is 4 different from 3?

The issue is 4 and 26 share a common divisor, 2, while 3 and 26 are relatively prime. When the key (4) and the size of the alphabet (26) are not relatively prime, there will be different plaintext letters which correspond to the same ciphertext. In the example above, we have

$\begin{displaymath}4\times 1 = 4 \qquad\mbox{and}\qquad 4\times 14 = 56 = 4 + (2\times 26) .\end{displaymath}$

If any time we use key which is an even number, any two plaintext letters which have character codes differing by 13 will encrypt to the same ciphertext, and so can't be deciphered again.

Notice also that 4 does not have a multiplicative inverse mod 26, because the equation $4x = 1 (\mbox{mod} 26)$ has no solution. To see this, notice that 4x must be an even number, but if we add 1 to any multiple of 26, we get an odd number. So there can be no number x so that 4x is of the form 1 + 26k.

There are two obvious ways to avoid this collision problem: don't use keys which share a common divisor with the length of the alphabet, or change the the alphabet so that its length is a prime number. In our case, this is easily accomplished by adding some punctuation to the alphabet (for example, adding a period, a comma, and and exclamation mark), which would give us a 29-character alphabet. Or we could include the digits 0-9, and a period. In order to be consistent with the what we've done before, however, we'll just avoid using even keys (or 13).

We can combine the cipher above with a Caesar cipher to get an affine cipher. That is, our key consists of two numbers m and b, where m is relatively prime to the length of the alphabet. Then to get the ciphertext for the letter with character code x, we compute mx + b and reduce modulo the length of the alphabet (26 in our case).

As an example of an affine cipher, let's encrypt the work blue using m=3 and b=20. As before, we note that blue has character codes 1,11,20,4, which becomes 3,7,8,12 after multiplying by 3 (and reducing/ mod 26). Now we add 20 to each one to get 23,27,28,32, which reduces to 23,1,2,6 modulo 26. This gives the ciphertext XBCG.

To decrypt, we just reverse the process: subtract 20 from each, then multiply by 9 (the inverse of 3), reducing modulo 26.

An affine cipher is just a specific case of the general substitution cipher we discussed in section 2, and so it is readily broken using frequency analysis. Indeed, if you know a message is encrypted with an affine cipher, you only need to determine what two letters are to crack the encryption.

Footnotes

... Times ⁹: Because of time limitations, this and following sections were not covered in the professional development workshop.
... Times ¹⁰: Because of time limitations, this and following sections were not covered in the professional development workshop.

5 An Unbreakable Cipher

V'ir Tbg n Frperg

This document as PDF

7 Twins and Triplets

Scott Sutherland
2005-10-26

6 Modern Times 10

Footnotes

6 Modern Times ¹⁰