Cryptography Reference
In-Depth Information
P
M
(0)
·
P
K
(
A
)=1
/
4
·
1
/
4=1
/
16. Furthermore, the encryption function works
as follows
E
A
(0)
=
a
E
A
(1)
=
b
E
B
(0)
=
b
E
B
(1)
=
a
In this example, the probability that ciphertext
a
occurs is
P
C
(
a
)=Pr[0
,A
]+
Pr[1
,B
]=1
/
4
3
/
4=1
/
16 + 9
/
16 = 10
/
16 = 5
/
8,
and the probability that ciphertext
b
occurs is
P
C
(
b
)=Pr[1
,A
]+Pr[0
,B
]=
3
/
4
·
1
/
4+3
/
4
·
3
/
4=3
/
16 + 3
/
16 = 6
/
16 = 3
/
8. Furthermore, the following
conditional probabilities can be computed for all
m
·
1
/
4+1
/
4
·
∈M
and
c
∈C
:
Pr[0
|
a
]=1
/
10
Pr[1
|
a
]=9
/
10
Pr[0
|
b
]=1
/
2
Pr[1
|
b
]=1
/
2
These numbers show that the encryption is not perfectly secure. For example,
if the adversary observes the ciphertext
a
, he or she can be pretty sure (with a
probability of 9
/
10) that the corresponding plaintext is 1 (he or she cannot be
similarly sure if the ciphertext
b
is observed). The encryption system can be made
perfectly secure if
P
K
(
A
)=
P
K
(
B
)=1
/
2.
In his seminal work, Shannon showed for nonrandomized symmetric encryp-
tion systems that a necessary (but usually not sufficient) condition for such a system
to be perfectly secure is that the entropy of
K
is at least as large as the entropy of
M
(this means that the secret key must be at least as long as the total amount of
plaintext that must be transmitted). This important result is formally expressed in
Theorem 10.1.
Theorem 10.1 (Shannon's Theorem)
In a perfectly secure symmetric encryption
system
H
(
K
)
≥
H
(
M
)
.
Proof.
H
(
M
)=
H
(
M
|
C
)
≤
H
(
MK
|
C
)
