Affine enciphering

We have just examined a trivial encryption scheme, the Caesar cipher, which can be described as applying x $\mapsto$ x + b (mod p) to each of the characters x in a message. As we have seen, this provides no security at all (a message encoded in this way can be cracked in a short while by a third grader), but minor modifications such as those in §5 greatly improve the security.

We now return to trivialities, but make it one step harder. Instead of encoding each character by just adding a constant, we can multiply by a constant as well. That is, we can use x $\mapsto$ ax + b (mod p)to encode each character. This not only helps a tiny bit (to crack it, you need to find out two characters instead of just one, and the encoded message looks a little more ``mixed up'', since letters adjacent in the alphabet no longer encode to adjacent letters), it helps us set up a little more conceptual machinery.

When do affine encodings fail?

You might be wondering if this will work. Certainly when we were just shifting the letters by a fixed amount, there was no chance that the enciphering transformation f could fail to be invertible. Does the same hold true if we multiply the numeric codes for the letters? That is, do different letters always encode to different letters?

The answer is, unfortunately, not always. For example, suppose we use a 27 character alphabet (A-Z and blank). Then if we encode using the transformation x $\mapsto$ 6x + 2 (mod 27), both ``A''(0) and ``J''(9) encode to the character ``C''(2). What went wrong? Recall that when we work modulo 27, any numbers that differ by a multiple of 27 are equivalent. Since 27 has nontrivial factors, several characters will collide whenever the multiplicand (6) shares a common divisor with 27. This will never happen if gcd(a, p) = 1.

Let's make that precise:

Proposition 3.7.1   Let a, b, x, and y be integers in the set {0, 1,..., p - 1}, with gcd(a, p) = 1. Then

ax + b $$\equiv$$ ay + b (mod p)    $$\iff$$    x $$\equiv$$ y (mod p)

Proof.  Suppose ax + b $\equiv$ ay + b (mod p). We want to show that x $\equiv$ y (mod p). Certainly we have ax $\equiv$ ay (mod p), so there must be integers k and m so that kp + ax = mp + ay. But we can then rewrite this as

a(x - y) = (k - m)p

that is, a(x - y) is a multiple of p. If a and p share no common divisors, then x - y must be a multiple of p, so x $\equiv$ y (mod p).

If x $\equiv$ y (mod p), then certainly ax + b $\equiv$ ay + b (mod p). $\mbox{\rlap{$\sqcup$ }\raise .2ex\hbox{$\sqcap$ }}$

Thus, by the above, we can see that the affine encoding scheme will be just fine if the multiplicand a is relatively prime to the length of our alphabet (p). Henceforth, we will always take an alphabet whose length is a prime number, so we need not worry about this issue. An alphabet of length 97 works quite well, because we can include all the usual printable ASCII characters (see §2.2, especially the table on page ). The keyboard I am typing this on produces 96 distinct characters (including space, tab, and newline), without resorting to control keys. If you plan to use the full ASCII or extended ASCII character set (including the null character), then you will need to make sure you choose a to be an odd number (since the length of the alphabet will be a power of 2).

Implementing and using an affine encoding

Implementing this scheme is a trivial modification to the Caesar2 procedure we wrote in §4. We only need add another parameter a, and change the encoding calculation. (We also renamed shift as b to correspond to our discussion here).

> AffineCode:= proc(plaintext, a, b)
    local textnum,codenum,i,p;
    global Alphabet;
      
    p       := length(Alphabet);
    textnum := ToNum(plaintext);
    codenum := [seq( modp(a*textnum[i]+b, p), i=1..length(plaintext)) ];
    FromNum(codenum);
  end:

What about decoding a message encoded by an affine cipher? If we know the original a and b, we could either write AffineDecode, which calculates modp( (textnum[i]-b)/a, p) instead, or, we could use AffineCode(1/a, -b/a), which is really the same thing.

If you think about it for a second, you may wonder whether 1/a mod p makes any sense at all. It does, but only if we interpret division in the right way. We should not divide by a in the ``ordinary way'' and then reduce modulo p, but instead interpret it to mean the solution x to the equation ax $\equiv$ 1 (mod p). That is, 1/a mod p is the multiplicative inverse of a in the group 0, 1,..., p-1. (As before, we can run into trouble here if a and p are not relatively prime.) Fortunately for us, maple knows about division modulo p:

> 1/6 mod 97;

   
Breaking an affine cipher

Suppose we have a message that was encrypted with an affine cipher on an alphabet we also know. Suppose also that we know (or manage to guess) the encoding of two letters. How do we then decipher the message? It is quite straightforward: since we know the message was enciphered with x $\mapsto$ y = (ax + b) mod p, and we know two examples of x and y, we need only solve a pair of linear equations  mod p. This is quite straightforward to do by hand, but maple will also do it for us.

For example, suppose we receive the message

which we know is encoded in the 53 letter alphabet consisting of the letters A-Z, a blank, then a-z. Suppose we also guess that the letter b (28) is the encoding for a space (26), and that U (20) is an encoded s (45) . We can figure out the encoding transformation by solving the pair of equations

26a + b $$\equiv$$ 28 (mod 53)        45a + b $$\equiv$$ 20 (mod 53).

We can ask maple to do this for us using msolve:

> msolve({a*26 + b = 28, a*45 +b = 20},53);

but, it will be more convenient to solve the deciphering transformation instead:

> msolve({A*28 + B = 26, A*20 +B = 45},53);

> AffineCode(`nrIbQyxEbkrI bwr EUbJaPybL abpyJJy UbUlrrxU`,44,13);