Cryptography Reference
In-Depth Information
We make the realistic assumption that the entropy of the plaintext grows
approximately proportional to its length. That is,
H
(
M
n
)
≈
(1
−
R
L
)
n,
where
R
L
is the redundancy of the plaintext language.
Against this background, it is interesting to analyze the key equivocation when
n
grows. For every
n
, there are possible keys (and it is hoped that the size of the set
of possible keys decreases as
n
increases). More specifically, there is one correct
key and a set of spurious keys (a spurious key is defined as a possible but not correct
key). The most interesting question is how large
n
must be in order to be theoretically
able to uniquely determine the key. This is where the notion of the unicity distance
as introduced in Definition 5.2 comes into play.
Definition 5.2 (Unicity distance)
The
unicity distance
n
u
is the approximate value
of
n
for which the key is uniquely determined by the ciphertext (i.e.,
H
(
K
C
n
)
|
≈
0
).
In other words, the unicity distance
n
u
is the minimum value for
n
so that
the expected number of spurious keys equals zero. This is the average amount of
ciphertext that is needed before an adversary can determine the correct key (again,
assuming the adversary has infinite computing power). The unicity distance can be
approximately determined as follows:
H
(
K
)
R
L
n
u
≈
n
u
ciphertext bits are given, it is then theoretically possible to uniquely
determine the key. For many practically relevant ciphers,
n
u
is surprisingly small.
If
n
≥
5.5
FINAL REMARKS
In this chapter, we overviewed and briefly discussed the basic principles and results
from information theory as far as they are relevant for contemporary cryptography.
Most importantly, we introduced and put into perspective the entropy of a probability
distribution or a random variable. The entropy is a fundamental measure of informa-
tion, and almost all information-theoretic security proofs make use of it in one way
or another. For example, in Section 10.4 we elaborate on perfectly secure encryption
systems, and we use information-theoretic arguments to prove security properties.
