Cryptography Reference
In-Depth Information
Corollary 1.4.
If X is an m-bit string and if we want to achieve perfect secrecy for any
distribution of X, then the key must at least be represented with m bits.
Proof.
If we want to achieve perfect secrecy for any
a priori
distribution of
X
,we
need to have
H
(
K
)
H
(
X
) for any distribution of
X
of
m
-bit strings. For the uniform
distribution we obtain
H
(
K
)
≥
m
.Nowif
k
is the key length, we know that for any
distribution of
K
,wehave
H
(
K
)
≥
≤
k
. Thus we have
k
≥
m
.
The corollary and the following result show that we cannot achieve perfect secrecy
in a cheaper way than the Vernam cipher.
Theorem 1.5.
The Vernam cipher provides perfect secrecy for any distribution of the
plaintext.
=
⊕
Proof.
Let
Y
K
be the ciphertext where
X
and
K
are independent bit strings
of length
n
, and
K
is uniformly distributed. For any
x
and
y
,wehave
X
Pr[
X
=
x
,
Y
=
y
]
=
Pr[
X
=
x
,
K
=
x
⊕
y
]
=
Pr[
X
=
x
]
×
Pr[
K
=
x
⊕
y
]
2
−
n
=
Pr[
X
=
x
]
×
.
2
−
n
. We deduce that Pr[
X
By adding over all
x
we obtain that Pr[
Y
=
y
]
=
=
x
|
Y
=
y
]
=
Pr[
X
=
x
] for any
x
and
y
.
1.3.4
Product Ciphers
Given two ciphers
C
and
C
defined by two secret key distributions
K
and
K
, we define
the product cipher
C
◦
K
).
C
with the product distribution on the secret key (
K
,
1.4
Exercises
Exercise 1.1.
Propose a way in order to break simple substitution ciphers.
Exercise 1.2.
Friedrich Kasiski, a Prussian military officer, worked on the Vigenere
cipher in the early nineteenth century and developed a famous test. The Kasiski Test
consists of counting the number of occurrences of multigrams. (Multigrams are sub-
words of the cryptogram. Example: digrams are multigrams of length two, trigrams are
multigrams of length three, etc.) Explain how we can use the Kasiski Test in order to
break the Vigenere cipher.
Exercise 1.3.
Compute themutual index of coincidence between two streams of English
text transformed with the same random substitution.
Compute the mutual index of coincidence between two streams of English text
transformed with two independent random substitutions.
Search WWH ::
Custom Search