Cryptography Reference
In-Depth Information
for the messages and so on). Thus one might be tempted to think that this scheme is
all that a cryptographer needs or, borrowing a term from [183], that it is something
like the Holy Grail of cryptography . But this is not the case for the one-time pad
has some drawbacks. A relatively minor one is that it is not easy to generate truly
random keys or, in this case, truly random sequences of bits, a process that requires
access to a physical source of entropy.
There is another, more important, problem that prevents widespread use of the
one-time pad: the fact that, as already mentioned, the key must be as long as the
message. In symmetric cryptography, Alice and Bob need a secure channel for key
exchange and, if the key has the same length as the message, this is asking toomuch in
most situations. Indeed, if Alice and Bob have such a secure channel at their disposal
to exchange the key, then why not use it to send the plaintext without encryption?
Of course, there are situations in which this remark does not apply. For example,
Alice and Bob might have a secure channel available today but they might not have
it available tomorrow, which is when they would like to exchange the information.
In this case the one-time pad can be useful and, in fact, it is said that this situation
arose when the one-time pad was used by Soviet spies during the cold war. These
agents were sent to other countries with their pads containing the key which would
be used when needed, perhaps many years later. It is also rumored that the one-time
pad is used in the red telephone between Washington and Moscow. However, it is
clear that its use is not viable for many of the current applications of cryptography
such as, for example, electronic commerce and, for this reason, its practical interest
is rather limited.
Observe that, to obtain perfect secrecy in the one-time pad, we have assumed that
all the messages (and also the keys and the ciphertexts) have the same length. In
practice, one may work with messages of variable length n
l , where l is a suitable
large integer. Each time a message is sent, a key is chosen at random among all the
possible keys with the same length as the message, which amounts to using one-time
pads of different lengths n
l . When several messages are sent in succession, the
problem the adversary faces is to obtain information about the concatenation of these
messages from the observation of the concatenation of the corresponding ciphertexts.
Here the condition that a new random key be used for each new message is crucial
for, otherwise, the adversary would observe a ciphertext obtained by using a key
that contains a concatenation of a smaller key with itself and is, therefore, far from
random.
Exercise 3.2 Prove that the one-time pad is perfectly secret by showing that Pr
(
C
=
c
|
M
=
m
) =
Pr
(
C
=
c
)
without using Shannon's theorem. To do so, prove that:
1
2 n
(i) For all c
C
and all m
M
,Pr
(
C
=
c
|
M
=
m
) =
Pr
(
K
=
m
c
) =
(where n is, as above, the length of the messages).
(ii) For all c
1
2 n .
Exercise 3.3 Show that if the one-time pad is modified to make
C
,Pr
(
C
=
c
) =
n
0 n
}
then the resulting encryption scheme is no longer perfectly secure. Explain what
happens if we do this when n
K ={
0
,
1
}
−{
=
1.
 
Search WWH ::




Custom Search