Cryptography Reference
In-Depth Information
Principles of Asymmetric Cryptography
In order to overcome these drawbacks, Diffie, Hellman and Merkle had a revolution-
ary proposal based on the following idea: It is not necessary that the key possessed
by the person who
encrypts
the message (that's Alice in our example) is secret. The
crucial part is that Bob, the receiver, can only
decrypt
using a secret key. In order
to realize such a system, Bob publishes a public encryption key which is known to
everyone. Bob also has a matching secret key, which is used for decryption. Thus,
Bob's key
k
consists of two parts, a public part,
k
pub
, and a private one,
k
pr
.
A simple analogy of such a system is shown in Fig. 6.3. This systems works quite
similarly to the good old mailbox on the corner of a street: Everyone can put a letter
in the box, i.e., encrypt, but only a person with a private (secret) key can retrieve
letters, i.e., decrypt. If we assume we have cryptosystems with such a functionality,
a basic protocol for public-key encryption looks as shown in Fig. 6.4.
Alice
Bob
k
pub
←−−−−−−−−−−−−
(
k
pub
,
k
pr
)=
k
y
=
e
k
pub
(
x
)
y
−−−−−−−−−−−−→
x
=
d
k
pr
(
y
)
Fig. 6.4
Basic protocol for public-key encryption
By looking at that protocol you might argue that even though we can encrypt a
message without a secret channel for key establishment, we still cannot exchange a
key if we want to encrypt with, say, AES. However, the protocol can easily be mod-
ified for this use. What we have to do is to
encrypt a symmetric key
, e.g., an AES
key, using the public-key algorithm. Once the symmetric key has been decrypted
by Bob, both parties can use it to encrypt and decrypt messages using symmetric
ciphers. Figure 6.5 shows a basic key transport protocol where we use AES as the
symmetric cipher for illustration purposes (of course, one can use any other sym-
metric algorithm in such a protocol). The main advantage of the protocol in Fig. 6.5
over the protocol in Fig. 6.4 is that the payload is encrypted with a symmetric cipher,
which tends to be much faster than an asymmetric algorithm.
From the discussion so far, it looks as though asymmetric cryptography is a
desirable tool for security applications. The question remains how one can build
public-key algorithms. In Chaps. 7, 8 and 9 we introduce most asymmetric schemes
of practical relevance. They are all built from one common principle, the one-way
function. The informal definition of it is as follows:
