Cryptography Reference
In-Depth Information
since the reverse inequality clearly holds, we actually have an equality. Therefore
|{
Enc
k
(
m
)
}
k
∈
K
|=|
C
|=|
K
|
,
so that there is a unique key
k
satisfying
Enc
k
(
m
)
=
c
and condition (ii) is proved.
Now, to prove (i) observe that, if we fix
c
∈
C
then, by (ii), for any
m
∈
M
there
exists a unique key
k
such that
Enc
k
(
m
)
=
c
. Calling this key
k
(
m
)
and using Bayes'
formula and the perfect secrecy of the scheme we have that:
Pr
(
K
=
k
(
m
))
Pr
(
M
=
m
)
Pr
(
C
=
c
|
M
=
m
)
Pr
(
M
=
m
)
=
Pr
(
C
=
c
)
Pr
(
C
=
c
)
=
Pr
(
M
=
m
|
C
=
c
)
=
Pr
(
M
=
m
).
Thus we see that Pr
(
K
=
k
(
m
))
=
Pr
(
C
=
c
)
, which is independent of
m
and
m
∈
M
m
))
shows that, for
m
,
,Pr
(
K
=
k
(
m
))
=
Pr
(
K
=
k
(
. Since all keys are of
1
|
K
|
this form, we see that all of them have the same probability
and (i) is proved.
For the converse implication, assume now that both (i) and (ii) hold. For
m
∈
M
and
c
∈
C
,let
k
∈
K
be the unique key such that
Enc
k
(
m
)
=
c
. Then Pr
(
C
=
1
|
K
|
c
|
M
=
m
)
=
Pr
(
K
=
k
)
=
no matter what the probability distribution on
M
)
=
m
∈
M
is. Now, if
c
∈
C
we have that Pr
(
C
=
c
Pr
(
C
=
c
|
M
=
m
)
Pr
(
M
=
|
K
|
·
m
∈
M
1
1
|
K
|
m
)
=
Pr
(
M
=
m
)
=
. Thus we see that, for
m
∈
M
and
c
∈
C
,
Pr
(
C
=
c
|
M
=
m
)
=
Pr
(
C
=
c
)
which, as we have seen, is equivalent to the perfect
secrecy of the system.
Exercise 3.1
Prove that none of the ciphers considered in Chap.
1
(Caesar, substi-
tution, Vigenère and Hill) has perfect secrecy when used to encrypt messages of
arbitrary length and indicate how imposing restrictions on the plaintext space used
(and not reusing keys) produces variants of these ciphers which are perfectly secret.
3.2 The One-Time Pad
We have seen that the Vigenère cipher can be easily broken with a ciphertext-only
attack, if the attacker is given a sufficient amount of ciphertext. Moreover, one also
sees that a longer key (or, to be more precise, a small ratio between the ciphertext
length and the key length) makes the attack more difficult. In other words, using a
longer key will make the unicity distance greater, and if the unicity distance is greater
than the length of the available ciphertext, then the system will be very difficult to
break. So the idea arises of using an
infinite
key length, a sort of limit of the (finite)
Vigenère cipher. In practice, since all the encrypted messages will be finite, this
amounts to using a key which has at least the same length as the message, with the
