Cryptography Reference
In-Depth Information
Perfect Secrecy
A cipher has
perfect secrecy
when
H
(
M
|
C
)=
H
(
M
).
The above is tantamount to saying that
H
(
C
|
M
)=
H
(
C
)
(see the role of independence on page 432). Basically, in a cryptosystem with
perfect secrecy, Eve gains no information from the ciphertext about the plain-
text that was not alreadyknown previousl. Earlier, we talked about uniform
distribution of the keyspace with reference to unicity distance. Now we show
how this is intertwined with criteria for perfect secrecy.
Theorem 11.1
If
C
=
{
M
,
C
,
K
,E
}
is a cipher such that
1. Everykey
k
∈
K
has probability1
/
|
K
|
;
and
2. For each
m
∈
M
and
c
∈
C
, there exists exactlyone
k
∈
K
such that
E
k
(
m
)=
c
both hold, then
C
has perfect secrecy.
Corollary 11.1
(Shannon)
The One-Time Pad has perfect secrecy.
Shannon's Main Theorem (1949)
For a cryptosystem
C
=
{
M
,
C
,
K
,E
}
, anytwo of the following implythe
third.
1.
H
(
M
|
C
)=
H
(
M
).
2.
H
(
K
)=
H
(
M
).
3.
I
(
M
,
K
) = 0 (see page 432).
It should be noted that entropydoes not take into account the amount of
computing time necessaryto carryout an action. For instance, it might take
the life of the known universe to carryout a computation, but entropydoes not
cover this. An example is the RSA cipher (see Section 4.2), for which
H
(
)=0,
since the keymayalways be determined from public data. The computational
time to factor the modulus, which we have seen to be computationallyinfeasible,
is not taken into account bythe entropyviewpoint. Hence, the latter (the com-
putational complexityof RSA), is the more accurate assessment of RSA rather
than anyinterpretation via entrop. This is also true of other ciphers based
upon the intractabilityof solving some hard number-theoretic problem. For
these cryptosystems, the ciphertext is formed, as with RSA, via some function
computed modulo
n
, and the latter is roughlythe size of the ke. It follows that
the setup of such ciphers forces the cryptanalyst launching a ciphertext-only
attack, to tryall keys, in other words, a brute-force attack.
K
Search WWH ::
Custom Search