### What is
RSA?

RSA is a public-key cryptosystem for
both encryption and authentication; it was invented in 1977
by Ron Rivest, Adi Shamir, and Leonard Adleman [RSA78]. It works as follows: take two large primes, p
and q, and find their product n = pq ; n is called the
modulus. Choose a number, e, less than n and relatively prime
to (p-1)(q-1), which means that e and (p-1)(q-1) have no
common factors except 1. Find another number d such that (ed
- 1) is divisible by (p-1)(q-1). The values e and d are
called the public and private exponents, respectively. The
public key is the pair (n,e); the private key is (n,d). The
factors p and q maybe kept with the private key, or
destroyed.

It is difficult (presumably) to obtain
the private key d from the public key (n,^{e}). If
one could factor n into p and q, however, then one could
obtain the private key d. Thus the security of RSA is related
to the assumption that factoring is difficult. An easy
factoring method or some other feasible attack would
"break" RSA (see Question 10 and Question 46).

Here is how RSA can be used for privacy
and authentication (in practice, the actual use is slightly
different; see Question
16 and Question 17):

**RSA privacy (encryption):**
Suppose Alice wants to send a message m to Bob. Alice creates
the ciphertext c by exponentiating: c = m^{e} mod n,
where e and n are Bob's public key. She sends c to Bob. To
decrypt, Bob also exponentiates: m = c^{d} mod n; the
relationship between e and d ensures that Bob correctly
recovers m. Since only Bob knows d, only Bob can decrypt.

**RSA authentication:**
Suppose Alice wants to send a message m to Bob in such a way
that Bob is assured that the message is authentic and is from
Alice. Alice creates a digital signature s by exponentiating:
s = m^{d} mod n, where d and n are Alice's private
key. She sends m and s to Bob. To verify the signature, Bob
exponentiates and checks that the message m is recovered: m =
s^{e} mod n, where e and n are Alice's
public key.

Thus encryption and authentication take
place without any sharing of private keys: each person uses
only other people's public keys and his or her own private
key. Anyone can send an encrypted message or verify a signed
message, using only public keys, but only someone in
possession of the correct private key can decrypt or sign a
message.