Cryptography Reference
In-Depth Information
several substitutions—thus obtaining what is often called a
polyalphabetic substitu-
tion cipher
—to encrypt a given message, in such a way that different characters can
be encrypted as the same character because different substitutions are used and also,
conversely, different occurrences of the same character can be encrypted differently
for the same reason. This setup destroys the one-to-one correspondence between
plaintext characters and ciphertext characters and so it seems that it renders fre-
quency analysis useless. However, things are not so simple, as we are going to see
by looking at perhaps the most famous polyalphabetic cipher, which was used for
several centuries and eventually became regarded as
'le chiffre indéchiffrable'
.This
is the Vigenère cipher, which was introduced by Blaise de Vigenère in the sixteenth
century and reigned supreme in the crypto world until it was cryptanalyzed, in the
nineteenth century, by Babbage and Kasiski. The Vigenère cipher can be described
as follows. Suppose that we have an alphabet
Σ
, with
|
Σ
|=
n
. Then we identify
Σ
with
Z
n
and we set:
l
n
•
M
=
C
=
K
= Z
for some positive integer
l
.
•
If
k
=
(
k
1
,...
k
l
)
∈
K
then
Enc
k
((
i
1
,...
i
l
))
:=
(
i
1
+
k
1
,...,
i
l
+
k
l
)
mod
n
and
Dec
k
((
i
1
,...
i
l
))
:=
(
i
1
−
k
1
,...,
i
l
−
k
l
)
mod
n
.
(here we denote by
). Thus,
to use this cipher we divide the plaintext into blocks of length
l
and each character
in each block is encrypted with the shift given by the corresponding character of the
key. The key is usually presented as the word of length
l
over
(
x
1
,...,
x
l
)
mod
n
the
l
-tuple
(
x
1
mod
n
,...,
x
l
mod
n
)
Σ
whose characters
correspond to
k
1
,...,
k
l
(frequently, as is the case with natural language alphabets,
the alphabet has a standard ordering which is used to identify it with
Z
n
as we have
done before by means of the inverse bijections
code
and
char
). It is also customary
to use a so-called
Vigenère table
, which is nothing more that the operation table
corresponding to the sum in
Z
n
given in terms of the characters of
Σ
. In this way,
the first plaintext character, together with those in positions
l
1, ... (i.e., the
characters whose position in the plaintext is congruent to 1 modulo
l
) are encrypted
with the shift corresponding to the first character of the key. Similarly, the characters
whose position is congruent to 2 modulo
l
are encrypted with the shift corresponding
to the second letter of the key, and so on.
+
1, 2
l
+
Example 1.4
Let us give an example of a Vigenère encryption using the Eng-
lish alphabet. Suppose the plaintext is the text string
vigenereexample
and
the key is
word
(the key should be a random string over the English alphabet
but never mind as we shall see that the scheme is easy to break anyway). Then
we encrypt the first plaintext character,
v
, by adding it to the first key character
w
, where both letters are regarded as elements of
Z
26
as we saw when dealing
with the Caesar cipher (identifying letters with elements of
Z
26
by means of the
mutually inverse bijections
code
and
char
). Since
v
corresponds to 21 and
w
to 22, the result of adding them is
(
+
)
=
=
21
22
mod 26
43mod 26
17. The
character that corresponds to 17 is
char
(
)
=
r
and so
r
is the first ciphertext
letter. Then we would add the second letters, i.e.,
i
to
o
, and so on. When the
fifth plaintext letter,
n
, is reached, there are no key letters left since the key has
17
