Cryptography Reference
In-Depth Information
from a more general point of view in Chap.
4
but for now we restrict ourselves to the
situation that arises when we consider an encryption scheme that acts on blocks of
alphabet symbols. Such an encryption scheme is often also called a block cipher and
is characterized by the fact that both the plaintext space
M
and the ciphertext space
n
of fixed length
n
over an alphabet
C
are the set of words
Σ
Σ
. The positive integer
n
is called the
block length
or the
block size
.
Observe that this concept is very general and includes, for example, monoalpha-
betic substitution ciphers, which are just block ciphers of length 1. However, the
preceding remarks about resistance to statistical cryptanalysis apply only to block
ciphers with larger block sizes. Similarly, the Vigenère cipher may be regarded as
a block cipher with block size equal to the key length but the fact that it is built
from Caesar ciphers makes it vulnerable to statistical cryptanalysis even if the block
length is large.
In order to make statistical cryptanalysis hard, one may try to consider a cipher
in which each block is potentially encrypted in as many ways as possible, so that the
key space is also as large as possible. Observe now that, since encryption functions
must be injective, they must also be permutations of
n
. Thus, in a similar way to
the case of monoalphabetic substitution ciphers, we can easily describe the more
general block cipher of block length
n
, which is obtained by taking as encryption
functions all the possible permutations of
Σ
n
:
Σ
n
.
•
M
=
C
=
Σ
n
n
).
•
K
=
(Σ
)
Σ
S
(the set of all permutations of
,
Dec
σ
:=
σ
−
1
.
This encryption scheme has a very large key space since there are
t
n
n
),
Enc
σ
:=
σ
•
σ
∈
(Σ
For each
S
possible keys
if the alphabet has
t
symbols. It is not commonly used, however, for efficiency reasons,
as it is not clear how to represent and evaluate efficiently an arbitrary permutation
of
!
n
. For this reason, in practice block ciphers only use a subset of the set of
all possible permutations. However, one must be very careful with the way these
permutations are chosen. They should look like “random permutations” (as we will
could conceivably be exploited by an attacker.
To get a feeling of what may happen if the encryption functions for a block cipher
have a nice structure, we will look at the Hill cipher, invented by L. Hill in 1929. The
Hill cipher is obtained from the general block cipher described above by restricting
the encryption functions to be linear. This makes sense because of the fact that, if
the alphabet
Σ
Σ
has
t
symbols, then it may be identified with
Z
t
which, as explained
n
t
Z
={
(
x
1
,
x
2
,...,
x
n
)
|
x
i
∈ Z
t
}
then con-
sists of the
n
-component vectors over
Z
t
-module (it is
actually a 'free module', the exact analogue over a ring of the concept of vector space
over a field, cf. [45, 5.2]) and the maps that preserve this structure are called linear
(or module homomorphisms). The linear maps from
Z
t
and has the structure of a
n
t
Z
to itself are given by
n
×
n
n
t
square matrices with coefficients in
Z
t
(the image of a (row) vector of
Z
is obtained
