|From RSA laboratories FAQ, this
short description of RSA cryptosystem:
is the RSA cryptosystem?
The RSA cryptosystem is a public-key cryptosystem that offers both
digital signatures (authentication). Ronald Rivest, Adi Shamir, and
Leonard Adleman developed the RSA system in 1977; RSA
stands for the first letter in each of its inventors' last names.
The RSA algorithm works as follows: take two large primes, p and
q, and compute 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 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 may be destroyed or
kept with the private key.
It is currently difficult to obtain the private key d from the
public key (n, e). However if one could factor n into p and
q, then one could obtain the private key d. Thus the security of
the RSA system is based on the assumption that factoring is difficult. The
discovery of an easy method of factoring would ``break'' RSA.
Here is how the RSA system can be used for encryption and digital
Suppose Alice wants to send a message m to Bob. Alice creates the
ciphertext c by exponentiating: c = me mod n, where e and n
are Bob's public key. She sends c to Bob. To decrypt, Bob also
exponentiates: m = cd mod n; the relationship between e and d
ensures that Bob correctly recovers m. Since only Bob knows d,
only Bob can decrypt this message.
Suppose Alice wants to send a message m to Bob in such a way that
Bob is assured the message is both authentic, has not been tampered
with, and from Alice. Alice creates a digital signature s by
exponentiating: s = md 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 = se 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 another's public key or their own
private key. Anyone can send an encrypted message or verify a signed
message, but only someone in possession of the correct private key can
decrypt or sign a message.