Cryptography Reference
In-Depth Information
This can be easily seen with an example. Suppose the letter appearing most frequently
in a large amount of ciphertext is “V,” followed by “E.” Then “E”(= 4) probably maps to
“V”(= 21), and “T”(= 19) probably maps to “E”(= 4). We can then form the two congruences
21
4
a
+
b
(mod 26)
(*)
4
19
a
+
b
(mod 26).
Now, subtract the first congruence in (*) from the second (we can do this by proposition
20) to obtain
17
9
15
a
(mod 26)
Solving this congruence (for
a
) yields:
a
11 (mod 26).
We can then replace
a
with 11 in one of the congruences in (*), then calculate the value
for
b
. For example, solving 21
4(11) +
b
(mod 26) for
b
yields
b
21
44 =
23
3 (mod 26).
We can then calculate 11
, an inverse of 11 modulo
m
. This we determine quickly to be
11
19 (mod 26)
to decrypt a message. If it works, congratulations! If
not, then our guesses for the mappings of “E” and “T” were incorrect.
We can use this value along with
b
Exhaustive Key Search.
Note that using ciphers which map single characters to char-
acters in this way are simply not practical. If we are using a Caesar cipher with the ordinary
alphabet, there are only 25 choices for the shift value
and if we know that an affine cipher
with the ordinary alphabet is being used, there are only 12 choices for the multiplier and 25
choices for the shift. A computer could test all of the possible combinations very quickly.
Monoalphabetic substitution ciphers should never be used. Even if we allow every pos-
sible character to character mapping in the ordinary alphabet, there are 25! =
15,511,210,043,330,985,984,000,000 such mappings. (To see this, note that when we map
the letter “A” to another letter, we have 25 choices, assuming we want to map no letter to
itself). When we map “B” we have 24 choices remaining (the mapping must be one-to-one;
no two letters may map to the same letter), and so on. This makes a total of 25
b,
24 . . . 2
1 = 25! mappings. (See Table 5.4.)
TABLE 5.4
Choices for:
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
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
9
8
7
6
5
4
3
2
1
0
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
Search WWH ::
Custom Search