Cryptography Reference
In-Depth Information
1
.
25
4
.
7
≈
R
L
≈
1
−
0
.
75
.
This suggests that we are theoretically able to losslessly compress an English
text to one fourth its size. This means that a 10-MB file can be compressed to 2.5
MB. Note that redundancy in a natural language occurs because there are known and
frequently appearing letter sequences and that these letter sequences are the major
starting point for cryptanalysis.
5.4
KEY EQUIVOCATION AND UNICITY DISTANCE
In addition to the notion of redundancy, Shannon introduced and formalized a
couple of other concepts that can be used to analyze the security of deterministic
(symmetric) encryption systems. Let
M
n
and
C
n
be random variables that denote
the first
n
plaintext message and ciphertext bits, and
K
be a random variable that
denotes the key that is in use. An interesting question one may ask is how much
information about
K
is leaked as
n
increases. This brings us to the notion of the key
equivocation formally introduced in Definition 5.1.
C
n
)
(i.e., the entropy of the key as a function of the number of observed ciphertext bits).
Definition 5.1 (Key equivocation)
The
key equivocation
is the function
H
(
K
|
We generally assume that the plaintext and the key are statistically indepen-
dent, meaning that
H
(
M
|
K
)=
H
(
M
). We can show that
C
n
)=
H
(
K
)+
H
(
M
n
)
H
(
C
n
)
H
(
K
|
−
for a deterministic cipher. This is because
H
(
K
)+
H
(
M
n
)=
H
(
KM
n
)
=
H
(
KM
n
C
n
)
H
(
KC
n
)
=
H
(
C
n
)+
H
(
K
C
n
)
.
=
|
In the first line, we exploit the fact that
K
and
M
n
are statistically indepen-
dent. In the second and third line, we exploit the fact that
H
(
C
n
KM
n
)=0and
|
H
(
M
n
KC
n
)=0.
|
