Cryptography Reference
In-Depth Information
In Section 3.1.4 (and Definition 3.23), we introduced the notion of a permuta-
tion. In short, we said that a permutation on set
S
is a bijective function
f
:
S
→
S
.
In the case of block ciphers, the set is Σ
n
,and
E
=
{
E
k
:
k
∈K}
is a family
of bijective encryption functions
E
k
:Σ
n
Σ
n
. This means that the encryption
functions of a block cipher actually represent permutations of Σ
n
(or that a block
cipher is a family of permutations, respectively). If we fix the block length
n
and
work with the plaintext message and ciphertext spaces
→
=Σ
n
, then the key
M
=
C
space potentially comprises all permutations over Σ
n
(i.e.,
K
=
P
(Σ
n
)). For every
key
π
∈
P
(Σ
n
), the encryption and decryption functions are defined as follows:
E
π
:Σ
n
Σ
n
−→
w
−→
π
(
w
)
D
π
:Σ
n
Σ
n
−→
π
−
1
(
w
)
w
−→
=(Σ
n
)! possible permutations that can be used as block
ciphers with block length
n
. If, for example, Σ=
P
(Σ
n
)
There are
|
|
, then there are (2
n
)!
possible permutations. The function
f
(
n
)=(2
n
)! grows tremendously (see Table
10.1 for the first 10 values). For a typical block length
n
of 64 bits,
f
(
n
) returns
{
0
,
1
}
2
64
!=18
,
446
,
744
,
073
,
709
,
551
,
616!
This number is so huge that it requires more than 2
69
bits only to encode it.
Consequently, if we wanted to specify a particular permutation, then we would have
to introduce a numbering and use an index number that is approximately of that
size. This 2
69
-bit number would then serve as a secret key for the communicating
entities. It is, however, doubtful whether the entities would be able to manage such
a long key. Instead, symmetric encryption systems are usually designed to take
a reasonably long key
6
and generate a one-to-one mapping that looks random to
someone who does not know the secret key. So it is reasonable to use only some
possible permutations of Σ
n
(out of
P
(Σ
n
)) as encryption and decryption functions
and to use comparably small keys to refer to them. To analyze the security of
such a block cipher, one has to study the algebraic properties of the underlying
permutations. If, for example, the order of such a permutation is small, then one
can easily decrypt a ciphertext by encrypting it multiple times.
A reasonably long key has more like 69 bits than 2
69
bits.
6