Section 2.7 Affine Ciphers
Investigation Time!
Time for you to explore the ideas of affine ciphers with a new cipher wheel and Investigation: A new cipher wheel.
As you discovered in Investigation: A new cipher wheel the new cipher wheel could be represented as a combination of both a multiplicative and shift cipher. This is called an affine cipher.
Definition 2.7.1.
An affine cipher is an encryption of the form \(CT \equiv a PT + b \pmod{26}\) where \(0 \leq b \leq 25\) and \(a \in \{ 1,3,5,7,9,11,15,17,19,21,23,25 \}\text{.}\)
Remember that the restriction on the values for \(a\) is necessary for the ciphertext to be decryptable. We saw in Section 2.4 that these are the values of \(a\) that have a multiplicative inverse mod 26.
If we know the encryption formula, it is easy to encrypt a message.
Example 2.7.2.
Encrypt plaintext CAT with the formula \(CT \equiv 5 PT + 3 \pmod{26}\text{.}\) Translating CAT to numbers gives \([2,0,19]\text{.}\) Applying the encryption formula gives
Thus the ciphertext would be NDU.
But what do we need to do to decrypt a message? We need to solve for the PT in the above equation. We now know that we can add, subtract and multiply with modular arithmetic, but we cannot generally divide. However, often we can use the multiplicative inverse instead. To solve
for PT, we first substract \(b\) from both sides. This gives us
Let \(d\) be the multiplicative inverse of \(a\) mod 26, so that \(ad \equiv 1 \pmod{26}\text{.}\) Multiplying both sides by \(d\) gives
Thus, the decryption formula is
Example 2.7.3.
Decrypt SVH which was encrypted with \(CT \equiv 5 PT + 3 \pmod{26}\text{.}\) We first solve for the decryption formula.
The multiplicative inverse of 5 is 21 mod 26.
Now that we have the decryption formula, we first convert the ciphertext letters to numbers.
Then we apply the decryption formula.
We need to reduce mod 26.
Thus the plaintext is DOG.
Suppose, however, that we do not know the values of \(a\) and \(b\text{?}\) How can we perform cryptanalysis on an affine cipher? Could we use brute force? How many affine ciphers are there? We need to count the number of valid multipliers for \(a\) and valid shifts for \(b\text{.}\) The number of multipliers mod \(26\) is the number of elements with a multiplicative inverse mod \(26\) which by previous work is the just the numbers \(1,3,5,7,9,11,15,17,19,21,23,25\text{.}\) There are \(12\) good multipliers. All shifts are possible mod \(26\) so the number of shifts mod \(26\) is equal to \(26\text{.}\) Since each multiplier can be combined with each shift independently this gives us \(12\times 26=312\) possibilities. However, the affine cipher with a shift of zero and a multiplier of 1 is not an encryption, so we remove that one to get 311 possible affine ciphers.
Could we try 311 different values of \((a,b)\text{?}\) Probably, but its not so appealing. How else can we break affine ciphers? How can we solve them if we don't know \(a\) and \(b\text{.}\) Let's try to adapt some of our previous strategies. Suppose we intercept the encrypted message below.
Cipher Text: RXBDSYZYHFJDQPGHJFZKFMXSFGAFHSDRGNDCYFDGA
We saw previously that we could use letter frequency to help us. The most frequently occurring letters in the ciphertext are F (6 occurances), D (5 occurrances), and G (4 occurrances). Since the most common letters in the English language are E, T, A, O, I, N, S, R, H, we guess that F might correspond to E and D might correspond to T. This gives us the equations:
Subtracting the second equation from the first gives:
However this is a problem because for all \(a\text{,}\) \(2a\) mod \(26\) will be even, so we will never get an odd number and in particular will never get \(-15\text{.}\) Thus, this equation has no solution and we must have guessed the wrong correspondence. Note this even/odd issue will always cause a problem.
Theorem 2.7.4.
If the pair of equations
has a solution that corresponds to a valid affine cipher (can encrypt and decrypt messages) then \(PT_1-PT_2\) and \(CT_1-CT_2\) must either be both odd or both even.
Proof.
You will work on this proof in the exercises.
We now guess that F might correspond to E and D might correspond to A. This gives us the equations:
Subtracting the second equation from the first gives:
The theorem indicates that there is a solution this time since both \(PT_1-PT_2\) and \(CT_1-CT_2\) are even. An obvious solution is \(a=2\text{.}\) However, we remember that \(a=2\) is not a valid multiplier since 2 does not have a multiplicative inverse mod 26 so we hope there is another solution. We convert the congruence into equality using definition 4 so we have
for some integer \(k\text{.}\) This is equality rather than congruence so it is ok to divide here. We can divide by 2 and get
Note this gives us a congruence mod 13 rather than mod 26. So we see that \(a \equiv 2 \pmod{13}\text{.}\) This gives us TWO solutions mod 26. Both 2 and 15 are congruent to 2 mod 13 but are different mod 26. So we have either \(a \equiv 2 \pmod{13}\) OR \(a \equiv 15 \pmod{13}\text{.}\) Since we need \(a\) to correspond to a valid encryption and decryption formula we know \(a\) must be invertible mod 26. Therefore we must have \(a \equiv 15 \pmod{26}\text{.}\) We can use this to solve for \(b\text{.}\) Plugging \(a\) into the second equation gives
so \(b=0-45=-19=7\text{.}\) So we can now decrypt this affine cipher using the formula
Investigation Time!
Time for you to see what this ciphertext says and explore breaking affine ciphers in Investigation: Breaking Affine Ciphers.