The RSA system, named after the authors of a paper that introduced it (Ron Rivest, Adi Shamir and Leonard Adelman), is a public-key cipher.
For any public-key cipher, you must select two keys, a public key and a private key, where the public key is used for enciphering and the private key is used for deciphering. For RSA, that is done as follows.
Select two different large prime numbers p and q independently at random.
Let n = pq and compute φ = (p − 1)(q − 1).
Select a small number e > 2 that is relatively prime to φ.
Let d by the inverse of e (mod φ).
The public key set is the pair (n, e) and the private key set is the pair (n, d).
You can tell everybody your public key set if desired, but you keep the number d hidden. (Keep p and q hidden too, since anyone can compute d if he/she has p, q and e.)
A "message" to be enciphered is an integer x where 0 < x < n. The encipher function is
E(x) = xe mod n
Notice that anybody who knows the public key (n, e) can encipher a number x.
The decipher function is defined by
D(x) = xd mod n
For this example, we choose small prime numbers p = 7 and q = 13. (Obviously, this offers no security, but it illustrates how the system works.)
Then n = 7×13 = 91 and φ = 6×12 = 72.
We can choose e = 5, since 5 > 2 and gcd(5, 72) = 1. Then d = 29, since 5×29 ≡ 1 (mod 72). The encipher and decipher functions are
E(k) = k5 mod 91.
D(k) = k29 mod 91.
For example, encipher(18) = 185 mod 91 = 1889568 mod 91 = 44.
Then decipher(44) = 4429 mod 91 = 103398262268135618662965386326260402241163444053559142001800343869789787916826452309190192417264131218078348833560221412981442053155592422955707936598553748950499511586893512801517568 mod 91 = 18.
(As you can see, it is crucial that an efficient power algorithm is used, otherwise the numbers become much too large.)
We need to show that the decipher function is the functional inverse of the encipher function. Suppose that 0 < x < n.
Notice that D(E(x)) = (xe)d mod n = xde mod n.
By the Chinese Remainder Theorem, numbers x and y are congruent mod n = pq if and only if x ≡ y (mod p) and x ≡ y (mod q).
So it suffices to show that D(E(x)) ≡ x (mod p) and D(E(x)) ≡ x (mod q) We show that D(E(x)) ≡ x (mod p). The proof that D(E(x)) ≡ x (mod q) is symmetric.
There are two cases.
x is divisible by p. Then x ≡ 0 (mod p), so xed ≡ 0 (mod p), and we see that D(E(x)) ≡ 0 ≡ x (mod p).
x is not divisible by p.
Recall that d is the inverse of e (mod φ); that is, de ≡ 1 (mod φ). So de − 1 ≡ 0 (mod φ), and
| de − 1 | = | kφ |
| = | k(p−1)(q−1) |
| xde | ≡ | x⋅xde−1 | (mod p) |
| ≡ | x⋅xk(p− 1)(q−1) | (mod p) | |
| ≡ | x⋅(xp− 1)k(q−1) | (mod p) |
Fermat's Little Theorem tells us that xp− 1 ≡ 1 (mod p). So
| x⋅(xp− 1)k(q−1) | ≡ | x⋅(1)k(q−1) | (mod p) |
| ≡ | x | (mod p) |
How hard is it to decrypt an RSA cipher? Remember that n and and e are public.
If you can factor n into pq, then you have enough information to compute φ = (p−1)(q−1) and then to compute d, the inverse of e mod φ.
So RSA is no stronger than the factoring problem. But is it as strong as factoring? Is there some way to obtain d without factoring n? Nobody has shown that decrypting RSA requires factoring n, though it looks very difficult to break RSA without factoring n.
You need to use RSA in a sensible way. Do not send short messages such as yes or no. An eavesdropper can guess the message, encipher it, and check if the enciphered message is the same as the one sent.
Typically, you add random bits, called salt, to a message to make it longer and to make it different from messages sent in the past.
RSA is expensive to decipher. But it can be used to set up keys of a private-key cipher, and then to use the private key cipher after that.
For example, if A and B want to communicate, each can choose RSA keys. Each sends his or her encipher keys to the other. Then A and B can communicate securely, A sending messages to B using B's RSA key and B sending messages to A using A's RSA key.