Next: 3.2.2 Why use RSA
Up: 3.2 RSA
Previous: 3.2 RSA
RSA is a publickey cryptosystem for both encryption and
authentication; it was invented in 1977 by Ron Rivest, Adi Shamir, and
Leonard Adleman. 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 (p1)(q1), and find its
inverse, d, mod (p1)(q1), which means that ed = 1 mod (p1)(q1); e
and d are called the public and private exponents, respectively. The
public key is the pair (n,e); the private key is d. The factors p and q
must be kept secret, 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 entire security of RSA is predicated on
the assumption that factoring is difficult; an easy factoring method would
``break'' RSA (see Questions 3.2.5 and
3.4.4).
Here is how RSA can be used for privacy and authentication (in practice,
actual use is slightly different; see Questions 3.2.12 and
3.2.13):

RSA privacy (encryption):
 suppose Alice wants to send a private 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. To decrypt, Bob also exponentiates:
m=c^{d} mod n, and recovers the original message m; 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 signed document m to Bob. Alice creates
a digital signature s by exponentiating: s = m^{d} mod n, where d and
n belong to Alice's key pair. She sends s and m 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 belong to 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.
Next: 3.2.2 Why use RSA
Up: 3.2 RSA
Previous: 3.2 RSA
Denis Arnaud
12/19/1997