6

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

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

Since 7+26=33, we see that

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 , as long as we interpret correctly. As above, we have to find a number

This number is 9, since 3 x 9 = 27 = 1 + 26. 9 is called the

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

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
has no solution. To see this,
notice that 4*x* 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 4*x* is of the form 1 + 26*k*.

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

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.

- ... Times
^{9} - Because of time limitations, this and following sections were not covered in the professional development workshop.
- ... Times
^{10} - Because of time limitations, this and following sections were not covered in the professional development workshop.

Scott Sutherland

2005-10-26

2005-10-26