Cryptography Reference
In-Depth Information
Now that we have developed the above, we mayreturn to unicitydistance.
It can be shown that the it maybe approximated bythe following.
Unicity Distance Approximation
log
2
(
|
K
|
)
n
≈
,
D
(
L
)
where
D
(
L
) is the redundancyof the underling plaintext language
and
|
K
|
is the cardinalityof the keyspace
K
.
Note that if there is a uniform probabilitydistribution associated with
K
,
then
H
(
K
) = log
2
(
|
K
|
).
Example 11.9
Let us revisit the Caesar cipher discussed on page 11. Then
|
K
|
=26
, and since we are using English,
D
(
L
)
≈
3
.
5
. Thus, the unicity
distance is given by
log
2
(26)
/
3
.
5
≈
1
.
34
letters.
If we take the substitution cipher defined on page 8 on the English alphabet,
then
log
2
(
|
K
|
) = log
2
(26!)
≈
88
.
4
and since
D
(
L
)
≈
3
.
5
, then the unicity distance is
n
≈
88
.
4
/
3
.
5
≈
25
,
meaning that for ciphertexts of length about 25, there should exist a unique
decryption. because the unicity distance is effectively the smallest length of text
that has probability near
1
for one of the possible decryptions and probability
near
0
for all other possible decryptions.
The above tells us that the unicitydistance maybe viewed as the average
ciphertext length needed for a cryptanalyst to uniquely compute the key, given
enough computing time. Often the unicitydistance is defined in terms of what
are called
spurious keys
, which are those keys that Eve will rule out leaving
only“possible keys”, assuming she knows that the plaintext is a language such
as English, and she is engaged in a ciphertext-onlyattack. Then the unicity
distance is the value of
n
at which the number of spurious keys has an expected
value of 0. That value is exactlythe unicitydistance we have defined above.
Now we would like to delve into the world of Shannon's perfect secrecy, the
land of the one-time pad discussed on page 83.
Perfect Secrecy
A cryptosystem is deemed to be
perfect
when the plaintext and ciphertext
are mutuallyindependent. In other words, in terms of entropywe have the
following.
Search WWH ::
Custom Search