Chapter 3 Cryptography 51
Cryptography Overview
her message using that public key. Unlike symmetric-key cryptography, the key used
for encryption will not decrypt the message. That is, knowledge of Bob’s public key
will not help an attacker. To decrypt a message, Bob uses his private key. If Bob wants
to respond to Alice, he can encrypt his message using her public key.
To understand this idea, think of taking a number to a power. For instance, given
values x and y, compute z=x
y. To recover x, you would not compute zy, but rather
z1/y. You end up with the original x, because z1/y =(xy)1/y=xy·1/y=x1=x. You need
two values to perform this exercise: a “public key,” y, to compute the encrypted value,
and the inverse of the public key, or a “private key,” 1/y, to recover the original value.
This example, of course, is not practical because if you made y public, anyone could
easily compute 1/y and know your private key. Therefore, a good public-key
cryptosystem relies on a key pair for which it is impossible (or at least intractable) to
derive the private key from the public key.
Figure 3-9 Public-Key Cryptography
In practice, public-key algorithms are slow compared to symmetric-key algorithms.
Therefore, they are more often used for shorter messages, such as encrypting the
symmetric key for a message encrypted with a symmetric cipher, or for encrypting a
digest.
The RSA Algorithm
The RSA algorithm is a public-key cryptosystem for both encryption and
Input
Message
Public Key
Cryptosystem
Encrypted
Message
Public Key
Encryption Operation
Encrypted
Message
Public Key
Cryptosystem
Decrypted
Message
Private Key
Decryption Operation
The decrypted message is equal to the input message
if the public and private keys form a key pair.