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
Search WWH ::




Custom Search