Cryptography Reference
In-Depth Information
If we apply this function to the ciphertext previously obtained, we have:
> CaesarCryptanalysis(c);
table([1 = "lzwvawakuskl", 2 = "kyvuzvzjtrjk", 3 = "jxutyuyisqij",
5 = "hvsrwswgqogh", 4 = "iwtsxtxhrphi", 7 = "ftqpuqueomef",6 = "gurqvrvfpnfg",
10 = "cqnmrnrbljbc", 11 = "bpmlqmqakiab", 8 = "espotptdnlde", 9 = "dronsoscmkcd",
15 = "xlihmimwgewx", 14 = "ymjinjnxhfxy", 13 = "znkjokoyigyz", 12 = "aolkplpzjhza",
21 = "rfcbgcgqayqr", 20 = "sgdchdhrbzrs", 23 = "pdazeaeoywop", 22 = "qebafbfpzxpq",
16 = "wkhglhlvfdvw", 17 = "vjgfkgkuecuv", 18 = "uifejfjtdbtu", 19 = "thedieiscast",
26 = "maxwbxblvtlm", 24 = "oczydzdnxvno", 25 = "nbyxcycmwumn"])
A quick glance at this table shows that the only meaningful text is item number
19, which also reveals the key.
Exercise 1.5
Decrypt the ciphertext
"tnlxptdlhtnzybfpcpo"
, encryptedwith
the Caesar cipher. If you only had the sub-ciphertext
tdlh
would you still be able
to decrypt it?
1.2 Substitution Ciphers
The Caesar cipher is an example of a
substitution cipher
, namely a cipher that acts by
replacing each letter in the alphabet by another (possibly the same) one fixed by the
key. In this case, the substitutions used (which correspond to certain permutations
of the alphabet) are shifts, and the reason for the extreme weakness of the cipher
is the fact that the number of shifts, and hence of possible keys, is just the same as
the number of symbols (26 in the case of the English alphabet). The fact that this
number is very small is what makes the brute-force attack successful against shift
ciphers and so an obvious idea to increase security is to keep the substitutions but
do not restrict them to being shifts, in order to have a much larger key space. If the
substitution cipher acts upon single letters as is usual (there are variants in which
what one replaces are not single letters but words or, perhaps,
n
-grams for a certain
fixed value of
n
) and if the same alphabet is used for both plaintext and ciphertext,
then the encryption functions must be permutations of the alphabet. This is because,
in order to allow unique decryption, these functions must be injective and, since the
alphabet
Σ
Σ
to itself or, in
other words, permutations of the alphabet. Therefore, the size of the key space (and
the difficulty of a brute-force attack) is maximized by taking all the permutations of
the alphabet as encryption functions as follows.
is a finite set, they must necessarily be bijections from
Definition 1.1
Let
Σ
be an
n
-letter alphabet (in particular,
Σ
can be the 26-letter
English alphabet which can also be identified with
Z
26
in the standard way). The
(most general) substitution cipher over
Σ
is defined as follows:
•
M
=
C
=
Σ
.
•
K
=
S
n
(where
S
n
denotes, as usual, the set of permutations of a set of
n
letters
which we may identify with
Σ
).
,
Dec
σ
:=
σ
−
1
.
•
For each
σ
∈
S
n
,
Enc
σ
:=
σ
