Chapter 3 – Linear Cipher
In this chapter we will combine the previous two ciphers into one super cipher, the Linear Cipher. We first multiply a plain letter value and afterwards perform an additional Caesar shift. This allows more encryptions thus hampering an eavesdropper’s job. We will be able to use our knowledge of the two previous chapters to discover the number of possible unique encryptions for the Linear Cipher. The Linear Cipher turns out to be an insecure cipher as well. However, it offers the opportunity to study the “Euclidean Algorithm” to find the good encoding keys and the “Extended Euclidean Algorithm” to find the corresponding decoding keys. Furthermore, we will learn a very important aspect of cryptography: How to use letter frequency analysis in order to crack ciphers. After learning how to crack the Linear Cipher we will extend this technique to crack any Monoalphabetic Cipher, even the Random Substitution Cipher.
3.1 Encryption using the Linear Cipher
The Caesar and the Multiplication Cipher are not secure ciphers. To improve the security of an encrypted document we combine the Caesar and the Multiplication Cipher: we first multiply each plain letter by an integer a as done in the Multiplication Cipher and consequently shift it by b positions. We therefore obtain the following
Definition of the Linear Cipher:
The Linear Cipher encodes each plain letter P to a cipher letter C using the following encoding function:
C = a*P + b MOD M
where the encoding key consists of the pair of integers (a,b).
We call a the factor key and b the shift key.
Let us first investigate how many possible encryptions the Linear Cipher offers. Certainly more than the two previous ciphers, but how many exactly? Therefore, we have to first answer the following question: Does the Linear Cipher yield unique encryptions for any key pair (a,b)? Take a moment and come up with your guess.
Let’s start by checking the factor key a=2 and the shift key b=4. Thus, we use the encryption function C= 2*P + 4 MOD 26 to encode the virus carrier message as follows:
PLAIN TEXT /A
/ N / T / I / S / T / H / E / C / A / R / R / I / E / RP / 0 / 13 / 19 / 8 / 18 / 19 / 7 / 4 / 2 / 0 / 17 / 17 / 8 / 4 / 17
2*P / 0 / 0 / 12 / 16 / 10 / 12 / 14 / 8 / 4 / 0 / 8 / 8 / 16 / 8 / 8
C=2*P+4 MOD 26 / 4 / 4 / 16 / 20 / 14 / 16 / 18 / 12 / 8 / 4 / 12 / 12 / 20 / 12 / 12
Cipher text
/ e / e /q
/ u / o / q / s / m / i / e / m / m / u / m / mWe observe that this encryption does not produce the desired unique encryption. I.e. both the A and the N encode to the cipher letter e, also both R and E encode to m. The recipient does not know for sure how to decode the cipher letters e and m resulting in ambiguous messages. What causes the ambiguity? Is it the factor key a=2? Or the shift b=4?
The answer is easy. Shifting each letter never causes ambiguity. However, the factor key a=2 turns A = 0 and N = 13 into a = 0 making the cipher code not unique. The same will happen for any other factor key that was a bad key in the Multiplication Cipher. Vice versa, a good key in the Multiplication Cipher must be a good factor key here since the final shift does not change the uniqueness of the encryption. Thus, the uniqueness solely depends on the chosen factor key a and not at all on the shift. This becomes even more evident if we choose the bad factor key a=13 and the shift key b=4. The corresponding encoding function is C= 13*P + 4 MOD 26.
PLAIN TEXT /A
/ N / T / I / S / T / H / E / C / A / R / R / I / E / R0 / 13 / 19 / 8 / 18 / 19 / 7 / 4 / 2 / 0 / 17 / 17 / 8 / 4 / 17
13*P / 0 / 13 / 13 / 0 / 0 / 13 / 13 / 0 / 0 / 0 / 13 / 13 / 0 / 0 / 13
C=13*P + 4
/ 4 / 17 /17
/ 4 / 4 / 17 / 17 / 4 / 4 / 4 / 17 / 17 / 4 / 4 / 17Cipher text
/ e / r /r
/ e / e / r / r / e / e / e / r / r / e / e / rThe multiplication with the factor key a=13 only yields 0 and 13. The final shift of 4 then produces the two cipher letters 4=e and the 17=r which makes the Cipher Code impossible to decode.
Recall that a=3 was a good key for the Multiplication Cipher MOD 26, so that we now encode the virus message using the good factor key a=3 and the final shift b=4. Thus, using the encoding function C= 3*P + 4 MOD 26 we obtain the following:
PLAIN TEXT /A
/ N / T / I / S / T / H / E / C / A / R / R / I / E / R0 / 13 / 19 / 8 / 18 / 19 / 7 / 4 / 2 / 0 / 17 / 17 / 8 / 4 / 17
3*P / 0 / 13 / 5 / 24 / 2 / 5 / 21 / 12 / 6 / 0 / 25 / 25 / 24 / 12 / 25
C=3*P+4
/ 4 / 17 / 9 / 2 / 6 / 9 / 25 / 16 / 10 / 4 / 3 / 3 / 2 / 16 / 3Cipher text
/ e / r / j / c / g / j / z / q / k / e / d / d / c / q / dExercise1: Identify the key pairs (a,b) that produce unique encryptions.
Exercise2: Can you guess a decoding function for any encoding function? Hint: it will be again a Linear Cipher.
Further questions to investigate:
1. The good keys of the Multiplication Cipher serve as good factor keys for the Linear Cipher. Does this implies that there are again j(M) good factor keys for a given alphabet length M?
2. How many encryptions does the Linear Cipher therefore allow? Do they make the Linear Cipher a secure cipher?
3. We have to set up the decoding function so that the recipient can decode the encrypted message.
4. How could an eavesdropper possibly crack Linear Cipher-encoded message?
We will answer these questions in the following sections.
3.1.1 The Linear Cipher offers 12 Good Factor Keys and 26 Good Shift Keys for M=26
To validate his conjecture that there are again j(M) good factor keys for a given alphabet length M recall the multiplication table of the Multiplication Cipher for an alphabet of length M=26:
PLAIN LETTER
0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0a / A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / Z
0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0
1 / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15 / 16 / 17 / 18 / 19 / 20 / 21 / 22 / 23 / 24 / 25
2 / 0 / 2 / 4 / 6 / 8 / 10 / 12 / 14 / 16 / 18 / 20 / 22 / 24 / 0 / 2 / 4 / 6 / 8 / 10 / 12 / 14 / 16 / 18 / 20 / 22 / 24
3 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23
4 / 0 / 4 / 8 / 12 / 16 / 20 / 24 / 2 / 6 / 10 / 14 / 18 / 22 / 0 / 4 / 8 / 12 / 16 / 20 / 24 / 2 / 6 / 10 / 14 / 18 / 22
5 / 0 / 5 / 10 / 15 / 20 / 25 / 4 / 9 / 14 / 19 / 24 / 3 / 8 / 13 / 18 / 23 / 2 / 7 / 12 / 17 / 22 / 1 / 6 / 11 / 16 / 21
6 / 0 / 6 / 12 / 18 / 24 / 4 / 10 / 16 / 22 / 2 / 8 / 14 / 20 / 0 / 6 / 12 / 18 / 24 / 4 / 10 / 16 / 22 / 2 / 8 / 14 / 20
7 / 0 / 7 / 14 / 21 / 2 / 9 / 16 / 23 / 4 / 11 / 18 / 25 / 6 / 13 / 20 / 1 / 8 / 15 / 22 / 3 / 10 / 17 / 24 / 5 / 12 / 19
8 / 0 / 8 / 16 / 24 / 6 / 14 / 22 / 4 / 12 / 20 / 2 / 10 / 18 / 0 / 8 / 16 / 24 / 6 / 14 / 22 / 4 / 12 / 20 / 2 / 10 / 18
9 / 0 / 9 / 18 / 1 / 10 / 19 / 2 / 11 / 20 / 3 / 12 / 21 / 4 / 13 / 22 / 5 / 14 / 23 / 6 / 15 / 24 / 7 / 16 / 25 / 8 / 17
10 / 0 / 10 / 20 / 4 / 14 / 24 / 8 / 18 / 2 / 12 / 22 / 6 / 16 / 0 / 10 / 20 / 4 / 14 / 24 / 8 / 18 / 2 / 12 / 22 / 6 / 16
11 / 0 / 11 / 22 / 7 / 18 / 3 / 14 / 25 / 10 / 21 / 6 / 17 / 2 / 13 / 24 / 9 / 20 / 5 / 16 / 1 / 12 / 23 / 8 / 19 / 4 / 15
12 / 0 / 12 / 24 / 10 / 22 / 8 / 20 / 6 / 18 / 4 / 16 / 2 / 14 / 0 / 12 / 24 / 10 / 22 / 8 / 20 / 6 / 18 / 4 / 16 / 2 / 14
13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13 / 0 / 13
14 / 0 / 14 / 2 / 16 / 4 / 18 / 6 / 20 / 8 / 22 / 10 / 24 / 12 / 0 / 14 / 2 / 16 / 4 / 18 / 6 / 20 / 8 / 22 / 10 / 24 / 12
15 / 0 / 15 / 4 / 19 / 8 / 23 / 12 / 1 / 16 / 5 / 20 / 9 / 24 / 13 / 2 / 17 / 6 / 21 / 10 / 25 / 14 / 3 / 18 / 7 / 22 / 11
16 / 0 / 16 / 6 / 22 / 12 / 2 / 18 / 8 / 24 / 14 / 4 / 20 / 10 / 0 / 16 / 6 / 22 / 12 / 2 / 18 / 8 / 24 / 14 / 4 / 20 / 10
17 / 0 / 17 / 8 / 25 / 16 / 7 / 24 / 15 / 6 / 23 / 14 / 5 / 22 / 13 / 4 / 21 / 12 / 3 / 20 / 11 / 2 / 19 / 10 / 1 / 18 / 9
18 / 0 / 18 / 10 / 2 / 20 / 12 / 4 / 22 / 14 / 6 / 24 / 16 / 8 / 0 / 18 / 10 / 2 / 20 / 12 / 4 / 22 / 14 / 6 / 24 / 16 / 8
19 / 0 / 19 / 12 / 5 / 24 / 17 / 10 / 3 / 22 / 15 / 8 / 1 / 20 / 13 / 6 / 25 / 18 / 11 / 4 / 23 / 16 / 9 / 2 / 21 / 14 / 7
20 / 0 / 20 / 14 / 8 / 2 / 22 / 16 / 10 / 4 / 24 / 18 / 12 / 6 / 0 / 20 / 14 / 8 / 2 / 22 / 16 / 10 / 4 / 24 / 18 / 12 / 6
21 / 0 / 21 / 16 / 11 / 6 / 1 / 22 / 17 / 12 / 7 / 2 / 23 / 18 / 13 / 8 / 3 / 24 / 19 / 14 / 9 / 4 / 25 / 20 / 15 / 10 / 5
22 / 0 / 22 / 18 / 14 / 10 / 6 / 2 / 24 / 20 / 16 / 12 / 8 / 4 / 0 / 22 / 18 / 14 / 10 / 6 / 2 / 24 / 20 / 16 / 12 / 8 / 4
23 / 0 / 23 / 20 / 17 / 14 / 11 / 8 / 5 / 2 / 25 / 22 / 19 / 16 / 13 / 10 / 7 / 4 / 1 / 24 / 21 / 18 / 15 / 12 / 9 / 6 / 3
24 / 0 / 24 / 22 / 20 / 18 / 16 / 14 / 12 / 10 / 8 / 6 / 4 / 2 / 0 / 24 / 22 / 20 / 18 / 16 / 14 / 12 / 10 / 8 / 6 / 4 / 2
25 / 0 / 25 / 24 / 23 / 22 / 21 / 20 / 19 / 18 / 17 / 16 / 15 / 14 / 13 / 12 / 11 / 10 / 9 / 8 / 7 / 6 / 5 / 4 / 3 / 2 / 1
The bold rows display the factor keys that produce unique encryptions as every row contains every integer from 0 to 25 exactly once. If we consider the factor key a=3 for a moment and varying the key shifts between b=0 and b=25 we obtain the following encryption table:
PLAIN LETTERS
A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / ZKey pairs / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15 / 16 / 17 / 18 / 19 / 20 / 21 / 22 / 23 / 24 / 25
a=3 , b=0 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23
a=3 , b=1 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24
a=3 , b=2 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25
a=3 , b=3 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0
a=3 , b=4 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1
a=3 , b=5 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2
a=3 , b=6 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3
a=3 , b=7 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4
a=3 , b=8 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5
a=3 , b=10 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6
a=3 , b=11 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7
a=3 , b=12 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8
a=3 , b=13 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9
a=3 , b=14 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10
a=3 , b=15 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11
a=3 , b=16 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12
a=3 , b=17 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13
a=3 , b=18 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14
a=3 , b=19 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15
a=3 , b=20 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16
a=3 , b=21 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17
a=3 , b=22 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18
a=3 , b=23 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19
a=3 , b=24 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20
a=3 , b=25 / 24 / 1 / 4 / 7 / 10 / 13 / 16 / 19 / 22 / 25 / 2 / 5 / 8 / 11 / 14 / 17 / 20 / 23 / 0 / 3 / 6 / 9 / 12 / 15 / 18 / 21
This table shows that each row shows contains each integer between 0 and 25 exactly once thus yielding 26 unique encryptions for the factor key a=3. The 26 shifts don’t spoil the uniqueness, they rather offer 26 different ways to uniquely encode our message. Certainly, tables holding this uniqueness property can be generated for the 12 good key factors a=1,3,5,7,9,11,15,17,19,21,23,25 yielding a total of 12*26=312 unique encryptions for the Linear Cipher.
There are two special cases to consider:
1. If we choose a=1 and vary b the resulting encryption is just the familiar Caesar Shift. The factor key a=1 has no effect, it leaves each plain letter unchanged. Nevertheless, for completeness, we count it as a good factor key.