RSA Security 5.2.2 manual RSA Algorithm, 9Public-Key Cryptography

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 = xy. 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.

Input

Message

Encrypted Message

Public Key

Public Key

Cryptosystem

Encryption Operation

Private Key

Public Key

Cryptosystem

Encrypted Message

Decrypted

Message

Decryption Operation

The decrypted message is equal to the input message if the public and private keys form a key pair.

Figure 3-9Public-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

C h a p t e r 3 C r y p t o g r a p h y 5 1