Cryptography Reference
In-Depth Information
AARDVARKSEATANTS
DI GDI GDI GDI GDI GD
DI XGDGUSYHI ZDVZV
Figure 2.5.
Example of encryption using the Vigenère Cipher
determines whether we use D, G or I to encrypt a particular occurrence of A in
the plaintext is the
position
of A in the plaintext. When A occurs in positions 1
and 13 we use D, when A occurs at position 6 we use G, and when A occurs at
positions 2 and 11 we use I. Note also that the ciphertext letter V occurs twice in
our example ciphertext, but that each occurrence represents a different plaintext
letter. This is because V is the encryption of plaintext letter N using key I, and is
also the encryption of plaintext letter D using key D.
These properties both make basic single letter frequency analysis of the
Vigenère Cipher apparently ineffective. Into the bargain, unlike for homophonic
encoding, there is no message expansion. This all helped to establish the Vigenère
Cipher's historical reputation of being practical and 'indecipherable'.
CRYPTANALYSIS OF THE VIGENÈRE CIPHER
The key in the Vigenère Cipher is the keyword. This means that the size of
the keyspace can be adjusted by choosing different lengths of keyword. A short
keyword does not offer much security since an exhaustive keyword search could
then be used to break the Vigenère Cipher. However, a keyword of length 13
already offers 26
13
keywords, which is approximately 2
10
18
possible keys (a
larger keyspace than that of DES), and a keyword of length 28 offers 26
28
, which
is approximately 4
.
5
×
10
39
possible keys (a larger keyspace than that of 128-bit
AES). Thus the size of the keyspace is not an issue for the Vigenère Cipher if a
reasonably long keyword is used.
Unfortunately, despite its promise and rather illustrious history of application,
the Vigenère Cipher is easily broken. The critical observation is that the Vigenère
Cipher can be viewed as a sequence of Caesar Ciphers employed in strict rotation.
To see this, consider the example in Figure 2.5. We can consider this example
as a rotation of three Caesar Ciphers. The first Caesar Cipher has key D (a shift
of 3). We use this Caesar Cipher to encrypt the first plaintext letter, and then use
it again for the plaintext letters in positions 4, 7, 10, 13 and 16. The second Caesar
Cipher has key I and we use it to encrypt the first plaintext letter, and then use it
again for the plaintext letters in positions 5, 8, 11 and 14. Finally, the third Caesar
Cipher has key G and we use it to encrypt the third plaintext letter, and then use
it again for the plaintext letters in positions 6, 9, 12 and 15.
.
2
×
