Cryptography Reference
In-Depth Information
Now, the ciphertext is decrypted as follows:
> Vigenere("word", %, dec);
"vigenereexample"
Exercise 1.9
Modify the previous functions so that any text over the ASCII-8 char-
acter set (excepting the null character) may be encrypted/decrypted (the alphabet
would be the string
convert([$1..255],bytes)
).
Exercise 1.10
Consider the encryption algorithm obtained by first encrypting the
message using the Vigenère cipher with a key
k
1
of length
l
1
and then encrypting
the resulting ciphertext again with the Vigenère cipher using a key
k
2
of length
l
2
.
Show that this is equivalent to a Vigenère encryption with a key
k
3
. Explain how
k
3
is obtained from
k
1
and
k
2
and determine its length in terms of
l
1
and
l
2
.Findthe
key word that corresponds to encryption with key 'key' followed by encryption with
key 'word'.
1.3.2 Cryptanalysis of the Vigenère Cipher
The size of the key space of the Vigenère cipher is 26
l
, where
l
is the length of the
key, assuming that a 26-letter alphabet is used. Thus an exhaustive key search is
not viable if a sufficiently long key—say, 20 characters or more—is used. However,
we are going to see that this cipher is also easy to cryptanalyze given a sufficient
amount of ciphertext, even if longer keys are used. The basic idea to cryptanalyze the
Vigenère cipher is that it is enough to determine the length of the key. Once this is
done, the rest is easy. Indeed, if the key length is
l
, then the characters whose position
in the plaintext is congruent to 1 modulo
l
are encrypted with the same shift (the one
corresponding to the first letter in the key). Similarly, the characters whose position
is congruent to 2 modulo
l
are encrypted with the second shift, and so on. Thus, after
determining the key length, the ciphertext can be decomposed into
l
sub-ciphertexts,
each one consisting of the characters whose position belongs to the same congruence
class modulo
l
, and then one breaks the cipher by carrying out frequency analysis on
each of these sub-ciphertexts separately.
The first idea to determine the key length was due to Babbage and Kasiski and
is nowadays known as the
Kasiski test
. If the same sequence of three or more
letters appears in different places of the ciphertext, it is very likely (the more
likely the longer the sequence) that the cause is the fact that a certain repeated
substring in the plaintext has been encrypted repeatedly with the same part of
the key. Thus, if this happens, the attacker measures the distances between the
different appearances of each of these repeated substrings in the ciphertext and
expects that the key length is a divisor of all these distances. If the attacker has
a sufficient quantity of ciphertext at her disposal she can determine the key length
by this method.
