Cryptography Reference
In-Depth Information
To make the task easier, we sort these frequencies in decreasing order:
> sort([freq], (u, v) -> evalb(rhs(u) >= rhs(v)));
[" " = 97, "G" = 56, "F" = 40, "I" = 33, "Z" = 31, "X" = 27, "O" = 24, "W" = 24,
"P" = 21, "U" = 20, "Y" = 19, "A" = 17, "B" = 17, "M" = 14, "L" = 12, "K" = 8,
"E" = 6, "S" = 6, "," = 5, "J" = 5, "N" = 5, "V" = 5, "." = 4, "D" = 4, "R" = 2]
Having these frequencies at our disposal we can compare them with the known
frequency distribution of the English language. This distribution is available from
many sources (e.g., from [130]; see next section for a list of these frequencies) and
can also be approximated by using a sufficiently long English text. We see that the
three most frequent characters in the above ciphertext are, in decreasing order,
G
,
F
,
and
I
.We can start by replacing these characters by the threemost frequent characters
in English texts, which are
e
,
t
, and
a
. We use Maple's function
CharacterMap
,
from the
StringTools
package for this purpose and we obtain:
> CharacterMap("GFI", "eta", c);
"Z MPLAO XaDe tPAO XeW tXe tWLtX,tXat tXe BaYe MaAMLAatZPU SXZMX XaO BeWDeO Ye KPW
OeMZEXeWZUJ tXe YaULBMWZEt XaO eUaNAeO Ye tP AeaWU tXe SPWO, NLt PU a MaEWZMe Zt
BtWLMR Ye tP teAA XeW tXat a JeUZe XaO WeDeaAeO Zt tP Ye. tXZB KaABe OZBMAPBLWe
KetteWeO YaOaYe OLWKe tP Ye. tXat OaV Z NeMaYe tXe YaBteW PK XeW BPLA, aUO Z
aNLBeO YV EPSeW. eDeWV tZYe Z tXZUR PK Zt, Z aY OZBtWeBBeO aUO aBXaYeO, aUO Z OP
EeUaUMe UPS ZU tXe PNAZJatZPU LUOeW SXZMX Z EAaMe YVBeAK PK teAAZUJ tXe tWLtX ZU
SWZtZUJ YV YeYPZWB."
We have to bear in mind that it is possible that the three most frequent letters
in the plaintext are not
e
,
t
, and
a
and, as we have mentioned, this is a trial-
and-error process. However, once some letters are fitted into their correct place,
the task becomes easier. In this case we see that, for example, the trigram
tXe
appears several times, from which it is easy to conjecture that the ciphertext char-
acter
X
corresponds to the plaintext character
h
. Other short words are also easy
to guess. In this particular case the task is very easy—we leave it as an exercise—
because we kept the spaces but even without this help the ciphertext would not be
too difficult to decrypt. We refer to [189] for a detailed example of cryptanalysis of
the substitution cipher.
Exercise 1.7
Decrypt the following ciphertext, obtained by encrypting an English
plaintext with the substitution cipher:
"DSSDNUJLQQVNUYVRNOMNWMSLPVFMPLPKFDMNPHNPNDONBFMJJFUIPFGLOKHLXFQKJSXNSPOSPPNUISDWN
DONDSPMSLMMLOTUYISDJFUJSDSYPLDWPNIYMLMFSDNGNPKSDNJLUMJNPFEJMMSMJNIPSMNOMFSDSHMJNQL
BLELFDUMUYOJFDMNPHNPNDONSPLMMLOTU"
1.3 The Vigenère Cipher
The substitution ciphers we considered in the preceding section are also known as
monoalphabetic substitution ciphers
because they use only a substitution (a permu-
tation of the alphabet) to encrypt the whole message. As we have just seen, their
vulnerability comes from the fact that the substitution preserves the frequency dis-
tribution (with changed characters). To remedy this fact, the idea arose of using
