Cryptography Reference
In-Depth Information
6.1.2 Merkle's Riddle
The key distribution method discussed below is presumably not used in practice,
but it is interesting for several reasons. It is a method that Ralph Merkle, famous
for the knapsack algorithm (Section 4.5.4), among other things, invented in
1974. Back then, the method obviously did not mean anything to anybody —
public cryptological research was still in its infancy (as you know from Section
4.3.1 in connection with the DES design).
So Merkle's method is of historical interest. Moreover, it is easy to understand,
and it uses symmetric encryption only:
1. Alice tells Bob that she wants to send him an encrypted message. Bob
creates 2
20
(approximately one million) messages in the form: 'The key
with identifier
x
is called
y
.' The values for both
x
and
y
have to
be different in each message. Bob uses a known symmetric method to
encrypt these messages individually, and he also uses 2
20
20-bit keys, a
different one for each message.
2. Alice uses brute force to cryptanalyze a message picked out randomly
(this won't generally take long for 2
20
keys). She obtains a value pair
(
x
,
y
).
3. Alice uses key
y
to encrypt her message, and sends the cipher together
with
x
to Bob.
4. Bob can easily determine the correct
y
from the value
x
sent, and decrypt
Alice's message.
An eavesdropper who wants to find
y
has to decrypt 2
19
messages on average
to find the one that contains the
x
sent. Using brute force, the eavesdropper
needs 2
19
ciphers, i.e., a total of 2
38
, for each decryption, while Alice has to
run only 2
19
ciphers on average. This means that an attacker would require a
computing technology that is about one million times faster than Alice's to be
able to listen in on the data communication.
Even though the method is probably not used in this form (there are thought
to be more effective variants), it is worth noting because its security is based
on one single encryption algorithm, and the cost for breaking the protocol can
be sized up.
