Cryptography Reference
In-Depth Information
that the task cannot be carried out in reasonable computational time. As DiQe
and Hellman put it in [69], a computationally infeasible task is one whose “cost
as measured by either the amount of memory used or the runtime is finite but
impossibly large.” (Typically, this means that it would take hundreds, if not
millions, of years on the fastest computer known.) However, if you burn the
paper, how does the intended recipient read the message? Youneed additional
information built into your one-way function so that the intended recipient can
recover the message. This additional information is called a
trapdoor
. Mathe-
matically speaking, a
trapdoor
in a one-way function is additional information
that makes the finding of the inverse a feasible task, but without the trapdoor
information, the task is computationally infeasible (see Chapter 4). For now,
think of a trapdoor as information that allows youto invert the fnction (de-
crypt the message), but if you do not know it, you cannot invert the function. It
is easy enough, as our paper-burning example indicated, to find one-way func-
tions, but getting those with trapdoors requires a bit more effort. So now let us
see how the DiQe-Hellman idea works.
Alice and Bob have never met, but want to establish a secret means of
communicating with one another. Bob and Alice both have unique public keys,
which we may envision as long strings of bits, published in some public data base
of keys that anyone can look up. Both Alice and Bob also have private keys that
they keep secure and known only to themselves, namely,
only
Bob knows his
private key
2.23
and
only
Alice knows her private key. Now, Alice takes a message
and uses Bob's public key via a one-way function to encipher the message in
a manner that
only
Bob's private key can decipher. So when Alice sends the
cryptogram, the only person in the world who can decipher it is Bob, with his
private key. Now suppose that another of our cast of characters, eavesdropping
adversary
Eve
, intercepts the message. Without Bob's private key, she has
only trial and error at her disposal to try to cryptanalyze it, probably taking
millions of years, so her interception is useless. Thus, since Bob is the only
person who has
both
elements of the key pair, he can decipher the message
instantly. The message might contain the symmetric-key
k
, say, and a reference
to the symmetric-key algorithm, such as DES, say. Similarly, Bob uses Alice's
public key and a one way function to encrypt a response, which would say
that he agrees to use DES with symmetric-key
k
for their correspondence, and
sends this to Alice, who uses her private key to decrypt, and she is the
only
one who can do so. In the DiQe-Hellman scheme,
k
is the shared secret key
independently generated by both Alice and Bob. The key exchange is complete
since Alice and Bob are in agreement on
k
. Hence, over an unsecured channel,
they have established a secure means of communicating.
The observant reader may wonder why they do not just use this key pair for
2.23
We use the convention that the term
private
key is reserved for use in association with
public-key cryptography, also called
asymmetric-key
cryptography, whereas the term
secret
key is reserved for symmetric-key cryptography. The cryptographic community has adopted
this convention since it takes two or more entities to share a secret (such as the
symmetric
secret key), whereas it is truly
private
when only
one
entity knows about it (such as with the
asymmetric private key).
Search WWH ::
Custom Search