** Next:** 3.2.14 Does RSA help
** Up:** 3.2 RSA
** Previous:** 3.2.12 How is RSA

Suppose Alice wishes to send a signed message to Bob. She uses a hash
function on the message (see Question 3.8.2) to create a message
digest, which serves as a ``digital fingerprint'' of the message. She then
encrypts the message digest with her RSA private key; this is the digital
signature, which she sends to Bob along with the message itself. Bob, upon
receiving the message and signature, decrypts the signature with lice's
public key to recover the message digest. He then hashes the message with
the same hash function Alice used and compares the result to the message
digest decrypted from the signature. If they are exactly equal, the
signature has been successfully verified and he can be confident that the
message did indeed come from Alice. If, however, they are not equal, then
the message either originated elsewhere or was altered after it was signed,
and he rejects the message. Note that for authentication, the roles of the
public and private keys are converse to their roles in encryption, where
the public key is used to encrypt and the private key to decrypt.

In practice, the public exponent is usually much smaller than the
private exponent; this means that the verification of a signature is
faster than the signing. This is desirable because a message or
document will only be signed by an individual once, but the signature
may be verified many times.

It must be infeasible for anyone to either find a message that hashes to a
given value or to find two messages that hash to the same value. If either
were feasible, an intruder could attach a false message onto Alice's
signature. Hash functions such as MD4 and MD5 (see Question 3.8.3)
have been designed specifically to have the property that finding a match
is infeasible, and are therefore considered suitable for use in
cryptography.

One or more certificates (see Question 3.3.5) may accompany a
digital signature. A certificate is a signed document attesting to the
identity and public key of the person signing the message. Its purpose is
to prevent someone from impersonating someone else, using a phony key pair.
If a certificate is present, the recipient (or a third party) can check the
authenticity of the public key, assuming the certifier's public key is
itself trusted.

** Next:** 3.2.14 Does RSA help
** Up:** 3.2 RSA
** Previous:** 3.2.12 How is RSA
*Denis Arnaud*

*12/19/1997*