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
, or 7, which we can
write as
H. The third is
, 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
, 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
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
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
Notice also that 4 does not have a multiplicative inverse mod 26,
because the equation
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.